SERVER-AIDED MULTI-PARTY PROTOCOLS

• US 20120233460A1
• Filed: 03/09/2011
• Published: 09/13/2012
• Est. Priority Date: 03/09/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kamara, Seny F., Mohassel, Payman
• Granted Patent: US 9,077,539 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• 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 computer-implemented multi-party computation system, comprising:

a computational resources component that provides computational resources to parties of secure multi-party communications, the computational resources include functionality sought by the parties for evaluation;

a first party component of the parties that sends one or more first concealed inputs to the computational resources component, and receives a first output derived from the functionality;

a second party component of the parties that sends a second concealed input to the computational resources component, and receives a second output derived from the functionality;

a protocol component via which the parties perform secure communications with the computational resources component to access the functionality, input the first and second concealed inputs to the computational resources component, and receive the first and second outputs from the computational resources component, the protocol component performs secure constant-round communications using garbled circuit technology to prevent the computation resources component from providing input to computation of the functionality and receiving output from the computation of the functionality; and

a processor that executes computer-executable instructions associated with at least one of the computational resources component or the protocol component.

2. The system of claim 1, wherein the computational resource component is part of one or more servers of a cloud computing framework that provides the computational resources for server-aided secure multi-party communications.

3. The system of claim 1, wherein the protocol component employs a garbled circuit created by the first party component and used by the computational resources component to evaluate the first and second concealed inputs and provide the first and second outputs, the protocol component is secure in the presence of non-colluding parties, and either a malicious server or a malicious second party.

4. The system of claim 1, wherein the protocol component employs multiple garbled circuits and multiple concealed inputs created by the first party component, the computational resources component selects a subset of the garbled circuits, verifies correct generation of the subset by the first party component and, continues evaluation the first and second concealed inputs and provides the first and second outputs based on the correct generation, the protocol component is secure in the presence of non-colluding parties and, at least one of a malicious server, a malicious first party, or a malicious second party.

5. The system of claim 1, wherein the protocol component employs a first garbled circuit created by the first party component and a second garbled circuit created by the second party component, the computational resources component compares the first and second garbled circuits, and continues evaluation based on favorable comparison of the first and second garbled circuits to provide the first and second outputs, the protocol component is secure in the presence of a semi-honest server and at most one malicious party.

6. The system of claim 1, wherein the protocol component employs keys generated at the first party component and second party component based on execution of a cryptographic protocol, the first party component creates ciphertexts using multiple keys generated from one of the keys and sends the ciphertexts, permuted in a random order, to the computational resources component where the ciphertexts are decrypted using one key of the multiple keys, the one key sent to the second party component to derive an output at the second party component based on the one key.

7. A computer-implemented protocol method for secure multi-party computation, comprising acts of:

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

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

sending the garbled circuit and first concealed input to a server, the server includes functionality that can be applied over inputs of the multiple parties;

generating, by the second party, a second concealed input and a second output table;

sending the second concealed input by the second party to the server;

evaluating the functionality at the server based on evaluation of garbling of the garbled circuit;

returning to the first party a first garbled output and to the second party a second garbled output for recovery of corresponding results by the first and second parties; and

utilizing a processor that executes instructions stored in memory to perform at least one of the acts associated with generating, sending, evaluating, or returning.

8. The method of claim 7, wherein the first party, the second party, and the server are non-colluding parties and the server is malicious.

9. The method of claim 7, wherein the first party, the second party, and the server are non-colluding parties and the second party is malicious.

10. The method of claim 7, wherein the server is part of a cloud computing system and the other parties are remote from the cloud computing system.

11. The method of claim 7, further comprising:

recovering a first result at the first party based on the first garbled output and the first output table; and

recovering a second result at the second party based on the second garbled output and the second output table.

12. A computer-implemented protocol method for secure multi-party computation, comprising acts of:

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

generating garbled circuits and first concealed inputs;

sending the garbled circuits and first concealed inputs to a server, the server includes functionality that can be applied over inputs of the multiple parties;

selecting a subset of the garbled circuits by the server;

opening the selected subset of garbled circuits by the first party by sending to the server secrets used to create the selected subset of garbled circuits;

verifying correct generation of the opened subset;

sending concealed inputs from the first and second parties to the server;

evaluating an unselected garbled circuit;

returning a first concealed output to the first party and a second concealed output to the second party; and

utilizing a processor that executes instructions stored in memory to perform at least one of the acts associated with generating, sending, selecting, opening, verifying, evaluating, or returning.

13. The method of claim 12, further comprising aborting computation at the server if the verification fails.

14. The method of claim 12, wherein the first party, the second party, and the server are non-colluding parties and the server is malicious.

15. The method of claim 12, wherein the first party, the second party, and the server are non-colluding parties and, the first party is malicious.

16. The method of claim 12, wherein the server is part of a cloud computing system and the other parties are remote from the cloud computing system.

17. A computer-implemented protocol method for secure multi-party computation, comprising acts of:

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

generating a first garbled circuit and a first concealed input;

sending the first garbled circuit and first concealed input to a server, the server includes functionality that can be applied over inputs of the multiple parties;

generating a second garbled circuit and a second concealed input;

sending the second garbled circuit and second concealed input to the server;

evaluating the garbled circuits at the server;

returning to the first party a first garbled output and to the second party a second garbled output; and

utilizing a processor that executes instructions stored in memory to perform at least one of the acts associated with generating, sending, evaluating, or returning.

18. The method of claim 17, further comprising aborting the computation at the server if the first garbled circuit does not compare favorably to the second garbled circuit.

19. The method of claim 17, wherein the server is semi-honest and at most one of the first party or the second party is malicious.

20. The method of claim 17, wherein the server is part of a cloud computing system and the other parties are remote from the cloud computing system.

21. A computer-implemented protocol method for secure multi-party computation, comprising acts of:

generating keys at a first party and a second party based on execution of a cryptographic protocol;

creating ciphertexts at the first party using multiple keys based on the first and second keys;

sending the ciphertexts, permuted in a random order, to a server;

decrypting the ciphertexts using one key of the multiple keys;

sending the one key to the second party;

deriving an output at the second party based on the one key; and

utilizing a processor that executes instructions stored in memory to perform at least one of the acts associated with generating, creating, sending, decrypting, or deriving.

22. The method of claim 21, further comprising computing at the second party second keys based on the multiple keys and sending the second keys to the server.

23. The method of claim 21, further comprising employing an authenticated private-key encryption scheme, a private-encryption scheme with verifiable range, and a pseudo-random function.