Transferable multiparty computation

• US 9,813,234 B2
• Filed: 05/11/2015
• Issued: 11/07/2017
• Est. Priority Date: 05/11/2015
• Status: Active Grant

• Current Assignee: US Department of The Air Force (U.S. Department Of Defense)
• Original Assignee: The United States of America As Represented By The Secretary of Agriculture
• Inventors: Clark, Michael R, Hopkinson, Kenneth M
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): Tran, Tongoc
• Application Number:
  US14/708,532
• Publication Number:
  US 20160335440A1
• Time in Patent Office: 911 Days
• Field of Search: 726 26, 380255
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A method and apparatus are provided for secure multiparty computation. A set of first parties is selected from a plurality of first parties for computation. Inputs for computation associated with each party in the set of first parties are divided into shares to be sent to other parties in the set of first parties. The computation on the shares is performed by the set of first parties using multiparty computation functions. In response to a trigger event, shares of the set of first parties are transferred to a set of second parties selected from a plurality of second parties. The computation is completed by the set of second parties using the transferred shares. Finally, the transferred shares are recombined to reveal an output of the computation.

Claims

1. A method of secure multiparty computation, the method comprising:

selecting a set of first parties from a plurality of first parties for computation;

dividing inputs for the computation associated with each party in the set of first parties into shares to be sent to other parties in the set of first parties;

performing the computation on the shares by the set of first parties using multiparty computation functions selected from a group consisting of;

SHARE, ADD, MULT, RECOMBINE, and combinations thereof;

in response to a trigger event, interrupting the computation on the set of first parties and transferring shares of the set of first parties to a set of second parties selected from a plurality of second parties;

completing the computation by the set of second parties using the transferred shares; and

recombining the transferred shares to reveal an output of the computation.

2. The method of claim 1, wherein transferring shares comprises:

generating subshares of a share that is being transferred;

sending one subshare of the generated subshares to each party in the set of second parties; and

performing a Lagrangian interpolation on subshares received by each of the parties in the second set of parties to generate a share for computation.

3. The method of claim 1, wherein transferring shares comprises:

generating subshares of a share that is being transferred;

sending one subshare of the generated subshares to each party in the set of second parties; and

performing a Reed-Solomon decoder for robust reconstruction on subshares received by each of the parties in the second set of parties to generate a share for computation.

4. The method of claim 1, wherein the trigger event includes a failure of a party.

5. The method of claim 1, wherein a trigger event is generated periodically.

6. The method of claim 1, wherein parties in the first plurality of parties overlap with parties in the second plurality of parties.

7. The method of claim 6, wherein parties in the set of first parties overlap with parties in the set of second parties.

8. The method of claim 1, wherein the trigger event is a first trigger event, the method further comprising:

in response to a second trigger event, transferring shares of the set of second parties to a set of third parties selected from a plurality of third parties;

completing the computation by the set of third parties using the transferred shares; and

recombining the transferred shares to reveal an output of the computation.

9. A system comprising:

a first node including;

a first processor;

a first memory;

a first network interface;

first program code resident in the first memory and configured to be executed by the first processor, the first program code configured to perform secure multiparty computation, the first program code further configured to receive shares for computation via the network interface and perform the computation on the received shares using multiparty computation functions selected from a group consisting of;

SHARE, ADD, MULT, RECOMBINE, and combinations thereof; and

in response to a trigger event, the first program code further configured to interrupt the computation and transfer a share of the received shares by;

generating sub shares of a share that is being transferred;

sending at least one subshare of the generated subshares to a second node.

10. The system of claim 9, further comprising:

the second node including;

a second processor;

a second memory;

a second network interface; and

second program code resident in the second memory and configured to be executed by the second processor, the second program code configured to perform secure multiparty computation, the second program code further configured to receive transferred subshares for computation via the network interface, perform a Lagrangian interpolation on the received transferred subshares to generate a share for computation, and perform the computation on interpolated shares using multiparty computation functions selected from a group consisting of;

SHARE, ADD, MULT, RECOMBINE, and combinations thereof.

11. The system of claim 9, further comprising:

the second node including;

a second processor;

a second memory;

a second network interface; and

second program code resident in the second memory and configured to be executed by the second processor, the second program code configured to perform secure multiparty computation, the second program code further configured to receive transferred subshares for computation via the network interface, perform a Reed-Solomon decoder for robust reconstruction on the received transferred subshares to generate a share for computation, and perform the computation on decoded shares using multiparty computation functions selected from a group consisting of;

SHARE, ADD, MULT, RECOMBINE, and combinations thereof.