Homomorphic encryption with optimized encoding
The techniques and/or systems described herein are directed to improvements in homomorphic encryption to improve processing speed and storage requirements. For example, the techniques and/or systems can be used on a client device to encode data to be sent to a remote server, to be operated on while maintaining confidentiality of data. For example, data including a real number can be encoded as a polynomial, with the fractional part of the real number encoded as high-order coefficients in the polynomial. Further, real numbers can be approximated and encoded in a polynomial using a fractional base, and/or the encoding can include slot encoding. Thus, the optimized encodings disclosed herein provide an optimized homomorphic encryption scheme.
1. A computing device comprising:
one or more hardware processors; and
memory storing modules that, when executed by the one or more hardware processors, cause the computing device to perform operations comprising:
receiving a data set including a real number, the real number including an integer portion and a fractional portion; and
encoding the integer portion and the fractional portion in a polynomial, the encoding comprising:
encoding the fractional portion of the real number by setting, for each coefficient of a term of the polynomial with a negative exponent, e, a coefficient of a term of the polynomial with an exponent equal to n+e to the coefficient of the term of the polynomial with the negative exponent, removing all terms with a negative exponent, and keeping the remaining coefficients of all other terms of the polynomial the same, where n is the size of the polynomial; and
encrypting the polynomial as ciphertext; and
transmitting the ciphertext via a network to a server.
2. A computer-implemented method for performing encoding for homomorphic encryption by at least one hardware processor, the method comprising:
receiving, by the hardware processor, a data set including a real number, the real number including an integer portion and a fractional portion; and
encoding, by the hardware processor, the integer portion and the fractional portion in a polynomial, the encoding comprising:
encoding, by the hardware processor, the fractional portion of the real number by setting, for each coefficient of a term of the polynomial with a negative exponent, e, a coefficient of a term of the polynomial with an exponent equal to n+e to the coefficient of the term of the polynomial with the negative exponent, removing all terms with a negative exponent, and keeping the remaining coefficients of all other terms of the polynomial the same, where n is the size of the polynomial; and
encrypting the polynomial as ciphertext; and
transmitting the ciphertext via a network to a server.
3. The method of claim 2 , further comprising:
receiving, from the server, a result of a performance of the at least one homomorphic operation on the ciphertext.
4. The method of claim 2 , wherein the at least one homomorphic operation includes at least one of addition, subtraction, multiplication, or division.
5. The method of claim 2 , further comprising:
determining that the real number can be approximated as an approximate real number; and
determining a fractional base to encode the polynomial, the fractional base based at least partly on the approximate real number.
6. The method of claim 2 , further comprising applying a slot encoding to the polynomial to generate a slot-encoded polynomial to increase a number of homomorphic operations that can be performed on the slot-encoded polynomial.
7. The method of claim 2 , further comprising receiving at least one encoding parameter via a network from a server, wherein the encoding the integer portion and the fractional portion is based at least in part on the at least one encoding parameter.
8. A system comprising:
one or more hardware processors; and
memory storing modules that, when executed by the one or more hardware processors, cause the system to perform operations comprising:
receiving a data set including a real number, the real umber including an integer portion and a fractional portion;
encoding the integer portion and the fractional portion in a polynomial, the encoding comprising:
encoding the fractional portion of the real number by setting, for each coefficient of a term of the polynomial with a negative exponent, e, a coefficient of a term of the polynomial with an exponent equal to n+e to the coefficient of the term of the polynomial with the negative exponent, removing all terms with a negative exponent and keeping the remaining coefficients of all other terms of the polynomial the same, where n is the size of the polynomial; and
encrypting the polynomial as a ciphertext;
transmitting the ciphertext via a network to a server; and
receiving, from the server, a result of a performance of the at least one homomorphic operation on the ciphertext.
9. The system of claim 8 , wherein the real number is encoded in the polynomial as a single polynomial without converting the real number to an integer.
10. The system of claim 8 , wherein the at least one homomorphic operation includes at least one of addition, subtraction, multiplication, or division.
11. The system of claim 8 , further comprising:
determining that the real number can be approximated as an approximate real number; and
determining a fractional base to encode the polynomial, the fractional base based at least partly on the approximate real number.