Managed secure computations on encrypted data

Patent metadata

Field	Value
Publication number	US-9306738-B2
Application number	US-201213723879-A
Country	US
Kind code	B2
Filing date	Dec 21, 2012
Priority date	Dec 21, 2012
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

The subject disclosure is directed towards secure computations of encrypted data over a network. In response to user desired security settings with respect to the encrypted data, software/hardware library components automatically select parameter data for configuring a fully homomorphic encryption scheme to secure the encrypted data items while executing a set of computational operations. A client initiates the set of computational operations via the library components and if requested, receives secure computation results in return.

First claim

What is claimed is:

1. A system, comprising:
a network resource to provide secure computations on a data set using at least one processor, to configure a leveled homomorphic encryption scheme for the secure computations based upon a noise estimate corresponding to at least one homomorphic function for execution on the data set, to generate a set of cryptographic keys from a truncated polynomial ring representing the leveled homomorphic encryption scheme, wherein the leveled homomorphic encryption scheme defines a single polynomial ring element for each data item in the data set, and to provide access to the at least one homomorphic function wherein the network resource partitions an encrypted data item into a plurality of portions, executes the at least one homomorphic function on each portion, and combines each portion to form a new encrypted data item.

2. The system of claim 1 , wherein the network resource is further configured to partition an encrypted data item into a plurality of fixed-sized portions or a plurality of variable-sized portions, execute the at least one homomorphic function on each portion and combine each resulting partition into a resulting encrypted data item.

3. The system of claim 2 , wherein the network resource is further configured to transform a set of computational operations into a structure comprising homomorphic function calls, wherein the computation module uses the structure to evaluate an encryption circuit.

4. The system of claim 3 , wherein the network resource is further configured to select the encryption circuit based upon user input comprising a security parameter.

5. The system of claim 4 , wherein the network resource is further configured to automatically generate parameter data to evaluate the encryption circuit with respect to executing the set of computational operations.

6. The system of claim 1 , wherein the network resource is further configured to encode a data item as a set of values using a set of co-prime moduli.

7. The system of claim 6 , wherein the network resource is further configured to build another homomorphic function using the at least one homomorphic function.

8. The system of claim 1 , wherein the network resource is further configured to reduce a ciphertext size by a modulus factor.

9. The system of claim 1 , wherein the network resource is further to restrict a cryptographic key space by sampling invertible elements from the truncated polynomial ring.

10. The system of claim 1 , wherein the encryption mechanism is further configured to implement the leveled homomorphic encryption scheme based upon decisional ring learning with errors (RLWE) problem and decisional small polynomial ratio (DSPR) problem, wherein the encryption mechanism performs a quantum reduction in ideal lattices.

11. Computer-readable hardware media having computer-executable instructions, which when executed by a system, cause the system to perform steps comprising:
configuring a leveled homomorphic encryption scheme for executing secure computations based upon a noise estimate corresponding to at least one homomorphic function for execution on a data set;
generating a set of cryptographic keys from a truncated polynomial ring representing the leveled homomorphic encryption scheme, wherein the leveled homomorphic encryption scheme defines a single polynomial ring element for each data item in the data set; and
providing access to the at least one homomorphic function by partitioning an encrypted data item into a plurality of portions, executing the at least one homomorphic function on each portion, and combining each portion to form a new encrypted data item.

12. The computer-readable hardware of claim 11 having further computer-executable instructions comprising:
partitioning an encrypted data item into a plurality of fixed-sized portions or a plurality of variable-sized portions;
executing the at least one homomorphic function on each portion; and
combining each resulting partition into a resulting encrypted data item.

13. The computer-readable hardware of claim 11 having further computer-executable instructions comprising: restricting a cryptographic key space by sampling invertible elements from the truncated polynomial ring.

14. A method, comprising:
configuring a leveled homomorphic encryption scheme to perform secure computations on a data set using at least one processor, the leveled homomorphic encryption scheme based upon a noise estimate corresponding to at least one homomorphic function for execution on the data set;
generating a set of cryptographic keys from a truncated polynomial ring that represents the leveled homomorphic encryption scheme, wherein the leveled homomorphic encryption scheme defines a single polynomial ring element for each data item in the data set;
partitioning an encrypted data item into a plurality of portions;
executing the at least one homomorphic function on each portion; and
combining each portion to form a new encrypted data item.

15. The method of claim 14 further comprising partitioning an encrypted data item into a plurality of fixed-sized portions or a plurality of variable-sized portions, execute the at least one homomorphic function on each portion and combine each resulting partition into a resulting encrypted data item.

16. The method of claim 14 further comprising transforming a set of computational operations into a structure comprising homomorphic function calls and using the structure to evaluate an encryption circuit.

17. The method of claim 16 further comprising selecting the encryption circuit based upon user input comprising a security parameter.

18. The method of claim 17 further comprising automatically generating parameter data to evaluate the encryption circuit with respect to executing the set of computational operations.

19. The method of claim 14 further comprising encoding a data item as a set of values using a set of co-prime moduli.

20. The method of claim 14 further comprising restricting a cryptographic key space by sampling invertible elements from the truncated polynomial ring.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Loftus Jacob J
• Naehrig Michael
• Bos Joppe Willem
• Lauter Kristin Estella

Classifications

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/0852 Primary

  Quantum cryptography (transmission systems employing electromagnetic waves other than radio waves, e.g. light, infrared H04B10/00; wavelength-division multiplex systems H04J14/02; WDM arrangements H04J14/03) · CPC title

• H04L9/08

  Key distribution {or management, e.g. generation, sharing or updating, of cryptographic keys or passwords (network architectures or network communication protocols for supporting key management in a packet data network H04L63/06)} · CPC title

• H04L9/3093

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

• G06F21/602

  Providing cryptographic facilities or services · CPC title