Server-aided multi-party protocols

• US 9,077,539 B2
• Filed: 03/09/2011
• Issued: 07/07/2015
• Est. Priority Date: 03/09/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kamara, Seny F., Mohassel, Payman
• Primary Examiner(s): Nguyen, Dustin
• Application Number:
  US13/043,468
• Publication Number:
  US 20120233460A1
• Time in Patent Office: 1,581 Days
• Field of Search: 713/153, 713/171, 713/193, 713/176, 380/28, 380/255, 380/282, 708/200
• US Class Current: 1/1
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

The disclosed architecture employs techniques that make secure multi-party computation (MPC) practical and scalable. In support of utilizing cloud computing, for example, for evaluating functionality, a third party server can be employed which does not have any input to the computation and does not receive any output from the computation, yet has a vast amount of computational resources. Accordingly, the secure MPC architecture can outsource as much as possible of the computation and communications burden of the parties without the server(s) learning any information about the party inputs.

Claims

1. A server system comprising:

at least one processing unit; and

at least one storage device or volatile or non-volatile memory device storing computer-executable instructions that, when executed by the at least one processing unit, cause the at least one processing unit to;

obtain a first concealed input from a first party,

obtain an entirety of a garbled circuit from the first party,

obtain a second concealed input from a second party,

provide the first concealed input and the second concealed input to computational resources,

obtain a first garbled output and a second garbled output from the computational resources,

send the first garbled output to the first party, and

send the second garbled output to the second party.

2. The server system of claim 1, embodied as a single computing device.

3. The server system of claim 1, wherein the computer-executable instructions cause the at least one processing unit to:

perform constant-round communications with the first party and the second party.

4. The server system of claim 1, further comprising the computational resources.

5. A method performed by a first party using at least one computer processing unit, the method comprising:

generating, by the first party, a seed based on execution of a cryptographic protocol by multiple parties that include the first party and a second party;

generating, by the first party, an entirety of a garbled circuit, a first concealed input, and a first output table;

sending the entirety of the garbled circuit and the first concealed input from the first party to a server configured to apply functionality over inputs of the multiple parties, the inputs including at least the first concealed input and a second concealed input provided to the server by the second party; and

obtaining, by the first party, a first garbled output from the server, wherein a first corresponding result is recoverable from the first garbled output using the first output table.

6. The method of claim 5, further comprising:

executing, by the first party, a coin tossing protocol with the second party to generate the seed.

7. The method of claim 5, wherein the first output table is generated based on the seed.

8. The method of claim 5, wherein the server is part of a cloud computing system and at least the first party is remote from the cloud computing system.

9. The method of claim 5, further comprising:

recovering the first corresponding result at the first party based on the first garbled output and the first output table.

10. A server system comprising:

at least one processing unit; and

at least one storage device or volatile or non-volatile memory device storing computer-executable instructions that, when executed by the at least one processing unit, cause the at least one processing unit to;

in a first instance;

obtain garbled circuits and a first concealed input from a first party;

select a subset of the garbled circuits;

obtain secrets usable to open the selected subset of garbled circuits;

open the subset of the garbled circuits using the secrets to obtain an opened subset of circuits while leaving an individual garbled circuit unopened;

verify correct generation of the opened subset of circuits;

obtain a second concealed input from a second party;

perform a computation on the first concealed input and the second concealed input using the individual garbled circuit that is left unopened to obtain a first concealed output and a second concealed output; and

send the first concealed output to the first party and the second concealed output to the second party.

11. The server system of claim 10, wherein the computer-executable instructions cause the at least one processing unit to:

in a second instance;

obtain other garbled circuits and another first concealed input from another first party for performing another computation;

select another subset of the other garbled circuits;

obtain other secrets;

attempt to open the another subset of the other garbled circuits;

make another determination that the another subset was incorrectly generated; and

abort the another computation responsive to the another determination.

12. The server system of claim 10, wherein the subset of garbled circuits is selected randomly by the server system.

13. The server system of claim 10, wherein the secrets comprise input tables.

14. The server system of claim 13, wherein the computer-executable instructions cause the at least one processing unit to:

request the input tables from the first party.

15. A server system comprising:

at least one processing unit; and

at least one storage device or volatile or non-volatile memory device storing computer-executable instructions that, when executed by the at least one processing unit, cause the at least one processing unit to;

in a first instance;

obtain, from a first party, a first garbled circuit and a first concealed input,

obtain, from a second party, a second garbled circuit and a second concealed input,

perform a comparison of the first garbled circuit to the second garbled circuit to determine whether to perform a computation using at least one of the first garbled circuit or the second garbled circuit, and

abort the computation based on the comparison.

16. The server system of claim 15, wherein the computer-executable instructions cause the at least one processing unit to:

in a second instance;

obtain, from another first party, another first garbled circuit and another first concealed input,

obtain, from another second party, another second garbled circuit and another second concealed input,

perform another comparison of the another first garbled circuit to the another second garbled circuit to determine whether to perform another computation,

based on the another comparison, perform the another computation using at least one of the another first garbled circuit and the another second garbled circuit to obtain a first garbled output and a second garbled output,

return, to the first party, the first garbled output, and

return, to the second party, the second garbled output.

17. The server system of claim 16, wherein:

the comparison indicates the first garbled circuit is not equivalent to the second garbled circuit, and

the another comparison indicates the another first garbled circuit is equivalent to the another second garbled circuit.

18. The server system of claim 15, wherein the server is part of a cloud computing system and the first party and the second party are remote from the cloud computing system.

19. A method performed by at least one computer processing unit, the method comprising:

in a first instance;

obtaining garbled circuits and a first concealed input from a first party;

selecting a subset of the garbled circuits to open;

obtaining secrets usable to open the selected subset of garbled circuits;

opening the subset of the garbled circuits using the secrets to obtain an opened subset of circuits while leaving an individual garbled circuit unopened;

verifying correct generation of the opened subset of circuits;

obtaining a second concealed input from a second party;

perform a computation on the first concealed input and the second concealed input using the individual garbled circuit that is left unopened to obtain a first concealed output and a second concealed output; and

sending the first concealed output to the first party and the second concealed output to the second party.

20. The method of claim 19, further comprising:

in a second instance;

obtaining other garbled circuits and another first concealed input from another first party for performing another computation;

selecting another subset of the other garbled circuits;

obtaining other secrets;

attempting to open the another subset of the other garbled circuits using the other secrets;

making another determination that the another subset was incorrectly generated; and

aborting the another computation responsive to the another determination.

21. The method of claim 20, further comprising selecting the selected subset of the garbled circuits and the another subset of the other garbled circuits randomly.

22. The method of claim 19, wherein the secrets comprise input tables.

23. The method of claim 22, further comprising:

requesting the input tables from the first party.