Secure computation using a server module

• US 9,521,124 B2
• Filed: 10/19/2015
• Issued: 12/13/2016
• 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:
  US14/887,130
• Publication Number:
  US 20160044003A1
• Time in Patent Office: 421 Days
• Field of Search: 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 serer 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 computing device comprising:

one or more processing devices; and

one or more computer-readable memories or storage devices storing instructions which, when executed by the one or more processing devices, configure the one or more processing devices to;

generate a key using a fully homomorphic encryption technique;

generate a modifier factor;

encrypt a first input using the key to obtain a first ciphertext;

send the first ciphertext and the modifier factor to a server that performs a multi-party computation using the first ciphertext, the modifier factor, and a second ciphertext provided by a second computing device to obtain an encrypted output, the use of the modifier factor not revealing the key to the server;

receive the encrypted output from the server; and

decrypt the encrypted output,

the use of the modifier factor in the multi-party computation influencing a degree of an underlying polynomial function used to decrypt the encrypted output.

2. The computing device of claim 1, wherein the key includes a first component that identifies values for evaluation using the underlying polynomial function and a second component that identifies locations of noise information.

3. The computing device of claim 1, wherein the modifier factor reveals no information regarding the key to the server.

4. The computing device of claim 1, wherein the instructions, when executed by the one or more processing devices, configure the one or more processing devices to:

decrypt the encrypted output by interpolating the underlying polynomial function to recover an unencrypted output of the multi-party computation.

5. The computing device of claim 4, wherein the use of the modifier factor in the multi-party computation prevents the degree of the underlying polynomial function from growing in linear proportion to a number of operations performed in the multi-party computation.

6. A computing device comprising:

one or more processing devices; and

one or more computer-readable memories or storage devices storing instructions which, when executed by the one or more processing devices, configure the one or more processing devices to;

generate a key and a modifier factor;

encrypt a first input using the key to obtain a first ciphertext;

send the first ciphertext and the modifier factor to a server module configured to perform a multi-party computation, the multi-party computation involving an evaluation of an arithmetic circuit on the first ciphertext and a second ciphertext provided by a second computing device, the server module using the modifier factor to perform the multi-party computation without the key being revealed to the server module;

receive an encrypted output from the server module; and

decrypt the encrypted output using the key to derive a polynomial function and use the polynomial function to obtain a result of the evaluation of the arithmetic circuit,

the use of the modifier factor in the multi-party computation affecting a corresponding degree of the polynomial function used to obtain the result.

7. The computing device of claim 6, wherein the instructions further configure the one or more processing devices to:

generate the key using a distributed coin tossing protocol in concert with the second computing device, wherein the second computing device is configured to generate the key, use the key to generate the second ciphertext, and send the second ciphertext to the server module.

8. The computing device of claim 7, wherein the distributed coin tossing protocol results in a random string.

9. The computing device of claim 8, wherein the instructions further configure the one or more processing devices to:

use the random string and a security parameter to generate the key and the modifier factor.

10. The computing device of claim 6, wherein, to encrypt the first input, the instructions further configure the one or more processing devices to:

provide a plurality of location values corresponding to locations along an axis of another polynomial function; and

encrypt the first input by evaluating the another polynomial function at the location values to produce a plurality of polynomial values.

11. The computing device of claim 10, wherein, to encrypt the first input, the instructions further configure the one or more processing devices to:

provide a set of noise indices; and

form the key based at least on a combination of the plurality of location values and the set of noise indices.

12. The computing device of claim 11, wherein the first ciphertext includes noise elements corresponding to noise locations identified by the noise indices and non-noise elements corresponding to the polynomial values.

13. The computing device of claim 10, wherein, to decrypt the encrypted output, the instructions further configure the one or more processing devices to:

generate the another polynomial function such that the first input is obtained by evaluating the another polynomial function at the zero location value on the axis.

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

generating a key and a modifier factor;

concealing a first input using the key to obtain a first ciphertext;

sending the first ciphertext and the modifier factor to another computing device that performs a multi-party computation by evaluating an arithmetic circuit using the first ciphertext, a second ciphertext provided by a second computing device, and the modifier factor, the modifier factor not revealing the key to the another computing device;

receiving a concealed output from the another computing device; and

performing interpolation using the concealed output to derive a polynomial function; and

evaluating the polynomial function to obtain a result of the evaluation of the arithmetic circuit,

the use of the modifier factor in the multi-party computation influencing a number of samples involved in the interpolation used to derive the polynomial function.

15. The method of claim 14, wherein the multi-party computation involves a multiplication operation.

16. The method of claim 14, further comprising:

determining a plurality of noise indices;

determining a plurality of α

values; and

combining the plurality of noise indices and the plurality of α

values to obtain the key.

17. The method of claim 16, wherein the plurality of a values identify corresponding locations on an axis of the polynomial function.

18. The method of claim 17, wherein the polynomial function is a univariate polynomial.

19. The method of claim 18, wherein the arithmetic circuit is a multiplication circuit.

20. The method of claim 19, wherein the interpolation is performed at the plurality of α

values on the axis and the result is obtained by evaluating the polynomial function at zero on the axis.