Transferable multiparty computation
Inventors
Clark, Michael R • Hopkinson, Kenneth M
Assignees
United States Department of the Air Force
Publication Number
US-9813234-B2
Publication Date
2017-11-07
Expiration Date
2035-05-11
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
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.
Core Innovation
The invention presents a method and apparatus for secure multiparty computation that enables transfer of computations among different groups of parties, referred to as transferable multiparty computation (T-MPC). Initially, a set of first parties is selected from a plurality to perform a computation by dividing their inputs into shares and performing the computation using multiparty computation functions such as SHARE, ADD, MULT, and RECOMBINE. Upon a trigger event, these shares are transferred to a second set of parties who continue and complete the computation, followed by recombination of the transferred shares to reveal the output to authorized parties.
The invention addresses the problem of privacy loss in systems that exploit fine-grained data, such as smart grids, where information from consumers can leak unintended information about household activities or identities. Existing methods for privacy preserving computation do not adequately scale or allow dynamic changes in computing parties without compromising privacy. The challenge is to provide a mechanism allowing computations to be securely transferred between different sets of parties without revealing private inputs, while supporting scalable applications.
Embodiments of the invention build on existing multiparty computation protocols by adding a triggering mechanism (TRIGGER) that interrupts an ongoing computation and new functions (TRANSFER and RECOMBINE_TRANSFER) that enable redistribution of secret shares to a new set of parties without revealing secrets. These functions also support both honest-but-curious and malicious adversary models by employing mechanisms such as Shamir secret sharing with Lagrangian interpolation and Reed-Solomon decoding for robust reconstruction, thereby enhancing security and scalability in diverse deployment scenarios.
Claims Coverage
The patent claims cover inventive features related to a method and system for secure multiparty computation with share transfer capabilities involving first and second sets of parties under trigger events, detailing share division, transfer, recombination, and computation completion.
Secure multiparty computation with share transfer upon trigger events
Selecting a set of first parties for computation; dividing their inputs into shares for other first parties; performing computations using multiparty functions; interrupting the computation upon a trigger event and transferring shares to a second set of parties; completing computations by the second parties; and recombining transferred shares to reveal output.
Share transferring via subshare generation and Lagrangian interpolation
Generating subshares of a share to be transferred; sending each subshare to a different party in the second set; and performing Lagrangian interpolation on received subshares by second parties to generate shares for computation.
Share transferring using subshares and Reed-Solomon decoding for robust reconstruction
Generating subshares of a share to be transferred; sending each subshare to a different party in the second set; and performing Reed-Solomon decoding on received subshares by second parties to robustly reconstruct shares for computation.
Trigger events including failure and periodic triggers
Trigger events include failure of a party and periodic trigger events that initiate the transfer of shares between sets of parties.
Overlapping parties in first and second sets
The first and second pluralities of parties, as well as the selected sets, may overlap.
Recursive or multiple share transfers
Support for multiple trigger events allowing shares to be transferred from second to a third set of parties, completing computation and recombining output.
System nodes configured to perform secure multiparty computation and share transfer
First node with processor, memory, network interface, and program code to perform secure multiparty computation, receive shares, and transfer subshares upon trigger events; second node configured to receive transferred subshares and perform recombination and computation.
Second node performing Lagrangian interpolation on received subshares
Second node receives transferred subshares, uses Lagrangian interpolation to generate computation shares, and performs secure multiparty computations on interpolated shares.
Second node performing Reed-Solomon decoder for robust reconstruction
Second node receives transferred subshares, uses Reed-Solomon decoding for robust reconstruction of shares, and performs secure multiparty computations on decoded shares.
The claims collectively cover a method and system enabling secure multiparty computations with dynamic transfer of secret shares between different sets of parties upon trigger events, using subshare generation, interpolation, or robust decoding methods, thus enhancing secure computation flexibility and scalability.
Stated Advantages
Enables scalable systems for privacy-preserving computation by allowing computations to be transferred among different groups of parties without revealing private inputs.
Enhances security by supporting both honest-but-curious and malicious adversary models with robust reconstruction techniques.
Improves efficiency and scalability, enabling larger networks to perform secure multiparty computations in shorter time frames compared to existing protocols.
Supports dynamic and flexible computation transfer triggered by events such as party failure or periodic schedules.
Documented Applications
Application in smart grid systems to securely aggregate fine-grained consumption data while preserving consumer privacy during computation.
Interested in licensing this patent?