Homomorphic encryption with optimized parameter selection

Patent metadata

Field	Value
Publication number	US-10075289-B2
Application number	US-201514934039-A
Country	US
Kind code	B2
Filing date	Nov 5, 2015
Priority date	Nov 5, 2015
Publication date	Sep 11, 2018
Grant date	Sep 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. The encoding scheme can be optimized by automatically selecting one or more parameters using an error growth simulator based on an actual program that operates on the encoded data. For example, the simulator can be used iteratively to determine an optimized parameter set which allows for improved homomorphic operations while maintaining security and confidentiality of a user's data.

First claim

What is claimed is:

1. A system comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the system to perform operations comprising:
receiving a sequence of operations including one or more homomorphic operations to be performed on at least one ciphertext;
running a simulation on the sequence of operations to determine an expected error in the at least one ciphertext;
determining at least one encoding parameter for encoding input data into at least one plaintext polynomial;
generating at least one encrypting parameter based on a result of the simulation, the at least one encrypting parameter for encrypting at least one plaintext polynomial into at least one ciphertext;
transmitting, to a computing device over a network, the at least one encoding parameter and the at least one encrypting parameter;
receiving, from the computing device over the network, at least one ciphertext, the at least one ciphertext based at least in part on the at least one encoding parameter and the at least one encrypting parameter; and
performing the sequence of operations including the one or more homomorphic operations on the at least one ciphertext.

2. The system of claim 1 , wherein the operations further comprise:
determining that the expected error in the at least one ciphertext is above a threshold; and
generating at least one updated encrypting parameter based on the expected error.

3. The system of claim 1 , wherein the operations further comprise automatically selecting the at least one encoding parameter and the at least one encrypting parameter to reduce a processing time or to reduce a memory requirement when the sequence of operations is implemented on homomorphically encrypted data.

4. The system of claim 1 , wherein the at least one encrypting parameter comprises a length N of a polynomial.

5. The system of claim 1 , wherein the at least one encrypting parameter comprises a plaintext modulus T.

6. The system of claim 1 , wherein the plurality of homomorphic operations include at least one of addition, subtraction, multiplication, or division.

7. The system of claim 1 , wherein the at least one ciphertext is a first ciphertext, and wherein the operations further comprise receiving a second ciphertext via the network from the computing device, the second ciphertext including data having been encoded using the at least one encoding parameter and the second ciphertext having been encrypted using the at least one encrypting parameter.

8. The system of claim 1 , wherein:
the at least one encrypting parameter comprises a length N of a polynomial that is selected as a lower-bound length and
a decomposition bit count W that is selected as an upper-bound size, wherein the running the simulation on the sequence of operations to determine the expected error in the at least one ciphertext includes using the length N of the polynomial and the decomposition bit count W; and
the operations further comprise:
determining that the expected error is above an error threshold; and
determining an updated decomposition bit count W′, wherein the updated decomposition bit count W′ is smaller than the decomposition bit count W.

9. The system of claim 8 , wherein the operations further comprise running an updated simulation using the length N of the polynomial and the updated decomposition bit count W′ to determine an updated expected error of the at least one ciphertext.

10. At least one device comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the at least one device to perform operations comprising:
receiving a sequence of operations including one or more homomorphic operations to be performed on at least one ciphertext;
running a simulation on the sequence of operations to determine an expected error in the at least one ciphertext, wherein the simulation is run iteratively to determine one or more encrypting parameters for encrypting at least one plaintext polynomial into at least one ciphertext;

determining at least one encoding parameter for encoding input data into at least one plaintext polynomial;
transmitting, to a computing device over a network, the at least one encoding parameter and the at least one encrypting parameter;
receiving, from the computing device over the network, at least one ciphertext, the at least one ciphertext based at least in part on the at least one encoding parameter and the at least one encrypting parameter;
performing the sequence of operations including the one or more homomorphic operations on the at least one ciphertext;
determining a result based at least in part on the sequence of operations; and
transmitting, to the computing device over the network, the result.

11. The at least one device of claim 10 , wherein the operations further comprise:
determining that the expected error in the at least one ciphertext is above a threshold; and
generating at least one updated encrypting parameter based on the expected error.

12. The at least one device of claim 10 , wherein the operations further comprise automatically selecting the at least one encoding parameter and the at least one encrypting parameter to reduce a processing time or to reduce a memory requirement when the sequence of operations is implemented on homomorphically encrypted data.

13. The at least one device of claim 10 , wherein:
the at least one encrypting parameter comprises:
a length N of a polynomial, wherein the length N of the polynomial is selected as a lower-bound length; and
a decomposition bit count W, wherein the decomposition bit count W is selected as an upper-bound size, wherein running the simulation on the sequence of operations to determine the expected error in the at least one ciphertext includes simulating an encrypting using the length N of the polynomial and the decomposition bit count W.

14. The at least one device of claim 10 , wherein the at least one encrypting parameter comprises a length N of a polynomial and a modulus Q as a predetermined {N, Q} pair.

15. A computer-implemented method for simulating homomorphic operations to generate operating parameters, the computer-implemented method performed by at least one processor, and the computer-implemented method comprising:
receiving a sequence of operations including one or more homomorphic operations to be performed on at least one ciphertext;
running a simulation on the sequence of operations to determine an expected error in the at least one ciphertext;
generating at least one encrypting parameter based on a result of the simulation, the at least one encrypting parameter to encrypt an encoded plaintext polynomial into at least one ciphertext;
transmitting, to a computing device over a network, the at least one encrypting parameter;
receiving, over the network, at least one ciphertext, the at least one ciphertext based at least in part on at least one encoding parameter and the at least one encrypting parameter; and
performing the sequence of operations including the one or more homomorphic operations on the at least one ciphertext.

16. The computer-implemented method of claim 15 , further comprising:
determining that the expected error in the at least one ciphertext is above a threshold; and
generating at least one updated encrypting parameter based on the expected error.

17. The computer-implemented method of claim 15 , wherein the operations further comprise determining a length N of a polynomial for encrypting input data as an encoded

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• H04L9/3073

  involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing · CPC title

• 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

• 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

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L63/0428

  wherein the data content is protected, e.g. by encrypting or encapsulating the payload · CPC title