Secure computation using a server module

• US 9,191,196 B2
• Filed: 04/02/2013
• Issued: 11/17/2015
• Est. Priority Date: 02/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Raykova, Mariana, Kamara, Seny F.
• Primary Examiner(s): SHAW, PETER C
• Application Number:
  US13/855,186
• Publication Number:
  US 20130254532A1
• Time in Patent Office: 959 Days
• Field of Search: 713/153, 713/150
• US Class Current: 1/1
• CPC Class Codes: H04L 2209/50 Oblivious transfer
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A server module evaluates a circuit based on concealed inputs provided by respective participant modules, to provide a concealed output. By virtue of this approach, no party to the transaction (including the sever module) discovers any other party'"'"'s non-concealed inputs. In a first implementation, the server module evaluates a garbled Boolean circuit. This implementation also uses a three-way oblivious transfer technique to provide a concealed input from one of the participant modules to the server module. In a second implementation, the server module evaluates an arithmetic circuit based on ciphertexts that have been produced using a fully homomorphic encryption technique. This implementation modifies multiplication operations that are performed in the evaluation of the arithmetic circuit by a modifier factor; this removes bounds placed on the number of the multiplication operations that can be performed.

Claims

1. A server computer comprising:

a server-participant communication module configured to receive;

a first concealed input from a first participant module, the first concealed input having been generated using a fully homomorphic encryption technique, the first concealed input having multiple first components, and

a second concealed input from a second participant module, the second concealed input having been generated using the fully homomorphic encryption technique, the second concealed input having multiple second components;

an evaluation module configured to evaluate an arithmetic circuit based on the first concealed input and the second concealed input, and to generate a concealed output; and

a processing device configured to execute the server-participant communication module and the evaluation module,

wherein the server-participant communication module is further configured to send the concealed output to the first participant module and the second participant module,

wherein the evaluation module is further configured to perform multiple multiplication operations using the multiple first components of the first concealed input, the multiple second components of the second concealed input, and a modifier factor provided by the first participant module or the second participant module, and

wherein actual values of the first concealed input, the second concealed input, and the concealed output are not revealed to the server computer.

2. The server computer of claim 1, wherein the first concealed input and the second concealed input are generated using a key produced by the fully homomorphic encryption technique.

3. The server computer of claim 2, wherein the key includes a first portion that identifies values for evaluation using a polynomial function, and a second portion that identifies locations of noise information.

4. The server computer of claim 2, wherein the modifier factor is configured so as not to reveal information regarding the key.

5. The server computer of claim 1, wherein the evaluation module is further configured to:

multiply each of the multiple first components by each of the multiple second components to obtain corresponding products; and

multiply each of the corresponding products by the modifier factor.

6. The server computer of claim 1, wherein the modifier factor is configured to enable the evaluation module to perform an unbounded number of multiplication operations.

7. The server computer of claim 1, provided as a resource within a cloud computing system.

8. A system comprising the server computer of claim 1 and a first participant device configured to execute the first participant module, wherein the first participant module is configured to generate the first concealed input and the modifier factor.

9. The system of claim 8, wherein the first participant module is configured to generate the first concealed input using a key that identifies locations of noise values in the first concealed input.

10. The system of claim 9, further comprising a second participant device configured to execute the second participant module, wherein the second participant module is configured to generate the second concealed input using the key, wherein the key also identifies locations of noise values in the second concealed input.

11. The system of claim 10, wherein the first participant module and the second participant module are each configured to decrypt the concealed output by:

using the key, distinguish noise values in the concealed output from non-noise values in the concealed output;

interpolate the non-noise values to derive a polynomial function; and

evaluate the polynomial function to extract a decrypted output.

12. A method performed by a computing device, the method comprising:

receiving a first concealed input from a first participant module, the first concealed input having been generated using a fully homomorphic encryption technique, the first concealed input having multiple first components;

receiving a second concealed input from a second participant module, the second concealed input having been generated using the fully homomorphic encryption technique, the second concealed input having multiple second components;

evaluating an arithmetic circuit based on the first concealed input and the second concealed input to generate a concealed output; and

sending the concealed output to the first participant module and the second participant module,

wherein the evaluating comprises performing multiple multiplication operations using the multiple first components of the first concealed input, the multiple second components of the second concealed input, and a modifier factor provided by the first participant module or the second participant module, and

wherein actual values of the first concealed input, the second concealed input, and the concealed output are not revealed to the computing device.

13. The method of claim 12, wherein the first participant module and the second participant module are located on other computing devices.

14. The method of claim 12, wherein the first concealed input and the second concealed input comprise noise elements and the modifier factor does not disclose locations of the noise elements.

15. The method of claim 12, wherein the first concealed input and the second concealed input are decryptable by interpolating a polynomial having an associated degree, and using the modifier factor in the multiple multiplication operations prevents the polynomial from growing in proportion to a number of multiplications that are performed.

16. A hardware storage device or hardware memory device storing instructions which, when executed by a processing device, cause the processing device to perform acts comprising:

receiving a first concealed input from a first participant module, the first concealed input having been generated using a fully homomorphic encryption technique, the first concealed input having multiple first components;

receiving a second concealed input from a second participant module, the second concealed input having been generated using the fully homomorphic encryption technique, the second concealed input having multiple second components;

evaluating an arithmetic circuit based on the first concealed input and the second concealed input to generate a concealed output; and

sending the concealed output to the first participant module and the second participant module,

wherein the evaluating comprises performing multiple multiplication operations using the multiple first components of the first concealed input, the multiple second components of the second concealed input, and a modifier factor provided by the first participant module or the second participant module, and

wherein actual values of the first concealed input, the second concealed input, and the concealed output are not revealed to the processing device.

17. The hardware storage device or hardware memory device of claim 16, wherein the multiple multiplication operations comprise:

multiplying each of the multiple first components by each of the multiple second components to obtain corresponding products; and

multiplying each of the corresponding products by the modifier factor.