Homomorphic encryption with optimized encoding

Patent metadata

Field	Value
Publication number	US-10153894-B2
Application number	US-201514934048-A
Country	US
Kind code	B2
Filing date	Nov 5, 2015
Priority date	Nov 5, 2015
Publication date	Dec 11, 2018
Grant date	Dec 11, 2018

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Laine Kim
• Dowlin Nathan
• Gilad-Bachrach Ran
• Naehrig Michael
• Wernsing John
• Lauter Kristin E

Classifications

• G06F7/483

  Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)} · CPC title

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L2209/125

  Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations · CPC title

• G09C1/00

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title