Homomorphic encryption with optimized homomorphic operations

Patent metadata

Field	Value
Publication number	US-9900147-B2
Application number	US-201514975528-A
Country	US
Kind code	B2
Filing date	Dec 18, 2015
Priority date	Dec 18, 2015
Publication date	Feb 20, 2018
Grant date	Feb 20, 2018

Abstract

The techniques and/or systems described herein are directed to improvements in homomorphic operations within a homomorphic encryption scheme. The homomorphic operations may be performed on encrypted data received from a client device without decrypting the data at a remote computing device, thereby maintaining the confidentiality of the data. In addition to the operations of addition, subtraction, and multiplication, the homomorphic operations may include an approximate division, a sign testing, a comparison testing, and an equality testing. By combining these operations, a user may perform optimized operations with improved processor and memory requirements.

First claim

What is claimed is:

1. At least one device comprising:
one or more processors; and
memory storing modules that, when executed by the one or more processors, cause the at least one device to perform operations comprising:
determining a plaintext modulus based on at least one homomorphic operation to be performed;
determining a difference between a first encrypted polynomial and a second encrypted polynomial to generate an encrypted polynomial representing at least one number;
receiving the encrypted polynomial, the encrypted polynomial encrypted based at least in part on the plaintext modulus;
dividing the encrypted polynomial by a divisor of the plaintext modulus to generate an encrypted divided polynomial, the dividing performed coefficient-wise on at least one coefficient of the encrypted polynomial, the dividing including rounding the at least one coefficient according to a rounding scheme;
determining a constant coefficient term of the encrypted divided polynomial, wherein the constant coefficient term of the encrypted divided polynomial indicates that a first number encrypted as the first encrypted polynomial is larger than a second number encrypted as the second encrypted polynomial upon decrypting the encrypted divided polynomial; and
transmitting the encrypted divided polynomial to a computing device.

2. The at least one device of claim 1 , wherein the dividing the encrypted polynomial by the divisor of the plaintext modulus avoids a homomorphic multiplication operation, thereby reducing a processing time of the one or more processors when performing the dividing.

3. The at least one device of claim 1 , wherein the operations further comprise constraining the at least one number to a range smaller than the plaintext modulus divided by the divisor.

4. The at least one device of claim 1 , wherein the operations further comprise:
determining a constant coefficient term of the encrypted divided polynomial; and
decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates whether the at least one number is a positive number or a negative number upon decrypting the encrypted divided polynomial.

5. The at least one device of claim 1 , wherein the rounding scheme rounds the at least one coefficient divided by the divisor of the plaintext modulus to a nearest integer.

6. The at least one device of claim 1 , wherein the at least one homomorphic operation includes at least one of an approximate division, a sign testing, a comparison testing, and an equality testing.

7. The at least one device of claim 1 , wherein the plaintext modulus is a plaintext modulus T 2 , wherein the divisor is a divisor T, and wherein the operations further comprise performing a homomorphic operation on the encrypted divided polynomial using a plaintext modulus T.

8. The at least one device of claim 1 , wherein the operations further comprise:
decrypting the constant coefficient term of the encrypted divided polynomial.

9. A computer-implemented method for performing at least one homomorphic encryption operation by at least one processor, the method comprising:
determining a plaintext modulus based on at least one homomorphic operation to be performed;
determining a difference between a first encrypted polynomial and a second encrypted polynomial to generate an encrypted polynomial representing at least one number;
receiving the encrypted polynomial, the encrypted polynomial encrypted based at least in part on the plaintext modulus;
dividing the encrypted polynomial by a divisor of the plaintext modulus to generate an encrypted divided polynomial, the dividing performed coefficient-wise on at least one coefficient of the encrypted polynomial, the dividing including rounding the at least one coefficient according to a rounding scheme;
determining a constant coefficient term of the encrypted divided polynomial, wherein the constant coefficient term of the encrypted divided polynomial indicates that a first number encrypted as the first encrypted polynomial is larger than a second number encrypted as the second encrypted polynomial upon decrypting the encrypted divided polynomial; and
transmitting the encrypted divided polynomial to a computing device.

10. The method of claim 9 , further comprising constraining the at least one number to a range smaller than the plaintext modulus divided by the divisor.

11. The method of claim 9 , further comprising:
decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates whether the at least one number is a positive number or a negative number upon decrypting the encrypted divided polynomial.

12. The method of claim 9 , wherein the rounding scheme rounds the at least one coefficient to a nearest integer.

13. The method of claim 9 , wherein the at least one homomorphic operation includes at least one of an approximate division, a sign testing, a comparison testing, and an equality testing.

14. The method of claim 9 , wherein the plaintext modulus is a plaintext modulus T 2 , wherein the divisor is a divisor T, and wherein the method further comprises performing a homomorphic operation on the encrypted divided polynomial using a plaintext modulus T.

15. The method of claim 9 , further comprising:
decrypting the constant coefficient term of the encrypted divided polynomial.

16. One or more non-transitory computer storage media comprising computer-executable instructions that, when executed by one or more processors, perform operations comprising:
determining a plaintext modulus based on at least one homomorphic operation to be performed;
transmitting the plaintext modulus to a computing device;
determining a difference between a first encrypted polynomial and a second encrypted polynomial to generate an encrypted polynomial representing at least one number;
receiving the encrypted polynomial, the encrypted polynomial encrypted based at least in part on the plaintext modulus;
dividing the encrypted polynomial by a divisor of the plaintext modulus to generate an encrypted divided polynomial, the dividing performed coefficient-wise on at least one coefficient of the encrypted polynomial, the dividing including rounding the at least one coefficient according to a rounding scheme;
determining a constant coefficient term of the encrypted divided polynomial, wherein the constant coefficient term of the encrypted divided polynomial indicates that a first number encrypted as the first encrypted polynomial is larger than a second number encrypted as the second encrypted polynomial upon decrypting the encrypted divided polynomial; and
transmitting the encrypted divided polynomial to the computing device.

17. The one or more non-transitory computer storage media as recited in claim 16 , wherein the operations further comprise constraining the at least one number to a range smaller than the plaintext modulus divided by the divisor.

18. The one or more non-transitory computer storage media as recited in claim 16 , wherein the rounding scheme rounds the at least one coefficient to a nearest integer.

19. The one or more non-transitory computer storage media as recited in claim 16 , wherein the plaintext modulus is a plaintext modulus T 2 , wherein the divisor is a divisor T, and wherein the operations further comprise performing a homomorphic operation on the encrypted divi

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Laine Kim
• Dowlin Nathan P
• GILAD BACHRACH Ran
• Naehrig Michael
• Wernsing John
• Lauter Kristin E

Classifications

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• H04L2209/34

  Encoding or coding, e.g. Huffman coding or error correction · CPC title