Secure computation using a server module

• US 10,033,708 B2
• Filed: 10/31/2016
• Issued: 07/24/2018
• 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:
  US15/339,502
• Publication Number:
  US 20170048208A1
• Time in Patent Office: 631 Days
• Field of Search: 713150
• 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 configured to participate in a multi-party computation over a network, the computing device comprising:

one or more processing devices configured via computer readable instructions to;

designate a first input wire key to represent a first value for an input wire of a circuit;

designate a second input wire key to represent a second value for the input wire of the circuit;

designate a first output wire key to represent the first value for an output wire of the circuit and a second output wire key to represent the second value for the output wire of the circuit;

determine a concealed input by mapping an input bit of an actual input that has the first value to the first input wire key;

receive, over the network from a second computing device, a first public key and a second public key, the first public key corresponding to the first value and the second public key corresponding to the second value;

encrypt the first input wire key with the first public key to provide a first ciphertext;

encrypt the second input wire key with the second public key to provide a second ciphertext;

provide the concealed input, the first ciphertext, and the second ciphertext over the network to a third computing device, the third computing device using the circuit to compute a computation output, the first input wire key allowing the third computing device to recover a computed output wire key representing an output bit of the computation output;

receive the computation output over the network from the third computing device; and

in an instance when the computed output wire key matches the first output wire key, determine that the output bit of the computation output has the first value.

2. The computing device of claim 1, the first value being 0 and the second value being 1.

3. The computing device of claim 2, wherein the one or more processing devices are configured via the computer readable instructions to:

designate another first input wire key to represent the first value for another input wire of the circuit and another second input wire key to represent the second value for the another input wire of the circuit; and

determine the concealed input by mapping another input bit of the actual input that has the second value to the another second input wire key, the concealed input comprising the first input wire key and the another second input wire key.

4. The computing device of claim 3, wherein the one or more processing devices are configured via the computer readable instructions to:

receive, over the network from the second computing device, another first public key and another second public key, the another first public key corresponding to the first value and the another second public key corresponding to the second value;

encrypt the another first input wire key with the another first public key to provide another first ciphertext;

encrypt the another second input wire key with the another second public key to provide another second ciphertext; and

provide the another first ciphertext and the another second ciphertext to the third computing device over the network before the third computing device computes the computed output.

5. The computing device of claim 4, wherein the one or more processing devices are configured via the computer readable instructions to:

provide the circuit to the third computing device over the network in garbled form.

6. The computing device of claim 5, wherein the one or more processing devices are configured via the computer readable instructions to:

garble the circuit.

7. The computing device of claim 6, wherein the circuit is configured to perform a Boolean operation.

8. A method performed by a first computing device to participate in a multi-party computation over a network, the method comprising:

by the first computing device;

designating different input wire keys to represent different values for different input wires of a circuit;

designating different output wire keys to represent the different values for different output wires of the circuit;

determining a concealed input by mapping an actual input to selected input wire keys, the concealed input comprising the selected input wire keys;

receiving, over the network from a second computing device, different public keys for the different input wire keys, individual public keys received from the second computing device representing individual values for corresponding input wires of the circuit;

encrypting the different input wire keys with associated public keys received from the second computing device to obtain ciphertexts;

providing the concealed input and the ciphertexts to a third computing device over the network, the third computing device using the circuit, the ciphertexts, and the selected input wire keys of the concealed input to recover a garbled computation output comprising computed output wire keys;

receiving the garbled computation output from the third computing device over the network; and

recovering a plaintext computation output from the garbled computation output by mapping the computed output wire keys to respective output bit values represented by the computed output wire keys.

9. The method of claim 8, wherein designating the different input wire keys includes designating at least two first input wire keys representing the different values for a first input wire of the circuit, the first input wire being an input to a particular gate of the circuit.

10. The method of claim 9, wherein designating the different input wire keys includes designating at least two second input wire keys representing the different values for a second input wire that is also an input to the particular gate of the circuit.

11. The method of claim 10, wherein designating the different output wire keys includes designating at least two output wire keys representing the different values for an output wire of the particular gate of the circuit.

12. The method of claim 11, further comprising:

by the first computing device, garbling the circuit and providing the circuit over the network to the third computing device in garbled form.

13. The method of claim 12, wherein garbling the circuit comprises encrypting the different output wire keys with the at least two second input wire keys to obtain intermediate results.

14. The method of claim 13, wherein garbling the circuit comprises encrypting the intermediate results with the at least two first input wire keys to obtain final results, the garbled circuit comprising the final results.

15. The method of claim 14, wherein the particular gate is a Boolean AND gate.

16. The method of claim 15, further comprising:

by the first computing device;

encrypting a zero-value output wire key with a zero-value second input wire key to provide a first intermediate result and encrypting the first intermediate result with a zero-value first input wire key to obtain a first final result;

encrypting the zero-value output wire key with a one-value second input wire key to provide a second intermediate result and encrypting the second intermediate result with the zero-value first input wire key to obtain a second final result;

encrypting the zero-value output wire key with the zero-value second input wire key to provide a third intermediate result and encrypting the third intermediate result with a one-value first input wire key to obtain a third final result; and

encrypting a one-value output wire key with the one-value second input wire key to provide a fourth intermediate result and encrypting the fourth intermediate result with the one-value first input wire key to obtain a fourth final result,

the garbled circuit comprising the first final result, the second final result, the third final result, and the fourth final result.

17. A computing device for participating in a multi-party computation over a network, the computing device comprising:

one or more processing devices configured via computer readable instructions to;

designate different input wire keys to represent different values for different input wires of a circuit;

designate different output wire keys to represent the different values for different output wires of the circuit;

determine a concealed input by mapping input bits of an actual input to selected input wire keys, the concealed input comprising the selected input wire keys;

receive, over the network from a second computing device, different public keys for the different input wire keys, individual public keys received from the second computing device representing individual values for corresponding input wires of the circuit;

encrypt the different input wire keys with associated public keys received from the second computing device to obtain ciphertexts;

provide the concealed input and the ciphertexts over the network to a third computing device, the third computing device using the circuit, the ciphertexts, and the selected input wire keys of the concealed input to recover a garbled computation output comprising computed output wire keys;

receive the garbled computation output over the network from the third computing device; and

recover a plaintext computation output from the garbled computation output by mapping the computed output wire keys to respective output bit values represented by the computed output wire keys.

18. The computing device of claim 17, wherein the computer readable instructions configure the one or more processing devices to:

designate at least two first input wire keys representing the different values for a first input wire of the circuit, the first input wire being an input to a particular gate of the circuit;

designate at least two second input wire keys representing the different values for a second input wire that is also an input to the particular gate of the circuit; and

designate at least two output wire keys representing the different values for an individual output wire of the particular gate of the circuit.

19. The computing device of claim 18, the at least two output wire keys comprising designated input wire keys for another gate of the circuit that uses output of the particular gate as input.

20. A system comprising the computing device of claim 17, the second computing device, and the third computing device.