Efficient Multiparty Protocols via Log-Depth Threshold Formulae
Secure Multiparty Computation (MPC) allows multiple players to jointly perform computational tasks securely. Feasibility results show perfect security in specific scenarios. This work proposes a novel approach using player emulation to design efficient MPC protocols, simplifying existing complex protocols. Applications include new proofs of classical MPC results and feasibility in various settings. Player emulation enables constructing more secure protocols efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Efficient Multiparty Protocols via Log-Depth Threshold Formulae Ron Rothblum Joint work with Gil Cohen, Ivan Damgard, Yuval Ishai, Jonas Kolker, Peter Miltersen and Ran Raz
Secure Multiparty Computation (MPC) [Yao86,Goldreich-Micali-Wigderson87] ? players wish to jointly perform some computational task securely. An adversary that controls a (limited) subset of the players learns nothing more than inputs and outputs of players it controls.
Feasibility Results: Perfect Security [BenOr-Goldwasser-Wigderson88,Chaum-Crepeau-Damgard88] Assume synchronous network with private channels and computationally unbounded adversary. Passive security: Every functionality ? can be computed securely if adversary passively controls at most ? < ?/2 of players. Active security: Every functionality ? can be computed securely if adversary actively controls at most ? < ?/3 of the players.
Our Contribution Huge body of work on secure MPC but protocols are fairly complicated. We suggest a conceptually appealing and flexible approach to designing efficient multiparty protocols. Polynomial complexity Technique: player emulation. Builds on [Hirt- Maurer00] but with a different motivation and obtain efficient protocols.
Applications 1. Give new and conceptually simple proofs of classical MPC results in the information theoretic setting. 2. New results on feasibility of MPC in a variety of settings, e.g., secure MPC over algebraic structures such as non-Abelian groups. 3. Distributed computing broadcast/Byzantine agreement.
MPC via Player Emulation A player in a protocol is just running some computational task it can be emulated by other players. Minimal number of players needed for security against one passive player Reduce the construction of ?-party protocols to the construction of constant-party protocols. For simplicity, first consider passive security - reduce ?-player protocol to 3-player protocol.
MPC via Player Emulation Assume: 3 player MPC with security against 1 passive player. Goal: Construct MPC protocol for ? players (with passive security against ? < ?/2 players).
3PC MPC Consider the trivial ?-party protocol that includes a trusted player ?.
3PC MPC Consider the trivial ?-party protocol that includes a trusted player ?. 1 ?1 ?1, ,?5= ? ?1, ,?5 2 ?2 ? ?3 3 ?4 ?5 4 5
3PC MPC Can emulate ? by three virtual players ?1,?2,?3. 1 ?1 ?1, ,?5= ? ?1, ,?5 2 ?2 ? ?3 3 ?4 ?5 4 5
3PC MPC Players send inputs to the virtual party ? which is emulated by ?1,?2,?3. ? 1 ?1 ?1 2 ?2 ?3 3 ?2 ?4 ?3 ?5 4 5
3PC MPC ?1,?2,?3 emulate ? s functionality. ? 1 ?1 2 3 ?2 ?3 4 5
3PC MPC The output is sent back to the players. ? 1 ?1 ?1 2 ?2 ?3 3 ?2 ?4 ?3 ?5 4 5
3PC MPC The initial protocol was secure as long as the adversary did not control the trusted party. The new protocol is secure as long as the adversary does not control a majority of ?1,?2,?3! Proceed by emulating ?1 by 3 more virtual players ?1,?2,?3.
3PC MPC ? Players send input to virtual player ?. ?1 ?1 1 ?3 ?2 2 3 ?2 ?3 4 5
3PC MPC ? ?1,?2,?3 emulate ?. ?1 ?1 1 ?3 ?2 2 3 ?2 ?3 4 5
3PC MPC ? ?1,?2,?3emulate ?1. ?1 ?1 1 ?3 ?2 2 3 ?2 ?3 4 5
3PC MPC ? ?1,?2,?3emulate ?1. ?1 ?1 1 ?3 ?2 2 3 ?2 ?3 4 5
3PC MPC ? "? sends back output to players. ?1 ?1 1 ?3 ?2 2 3 ?2 ?3 4 5
3PC MPC The protocol is secure even if the adversary controls: 1. One of ?2,?3 and one of ?1,?2,?3; or 2. ?1,?2,?3. Consider the formula: ? Associate wires with players and place 1 on input wires that the adversary controls. ???3 ?1 If output is 0 then the protocol is secure against this adversary. ?3 ?2 ???3 ?2 ?1 ?3
3PC MPC Suppose we have a formula that computes the majority function using only ???3 gates. ???3 ???3 ???3 ???3 ???3 ???3 ???3 ???3 ???3 ?2 ?1 ??
3PC MPC The formula tells us how to emulate players. ???3 ???3 ???3 ???3 ???3 ???3 ???3 ???3 ???3 ?2 ?1 ??
3PC MPC View root as the trusted party and every other gate as a virtual player. Leaves are real players. ? ?2 ?1 ??
MPC via Player Emulation Every virtual player is emulated by the 3 players beneath it. ? ?2 ?1 ??
MPC via Player Emulation Place 1 on players controlled by the adversary and 0 on other players. ? ?2 1 ?1 0 ?? 1
MPC via Player Emulation Place 1 on players controlled by the adversary and 0 on other players. 0 ? 1 0 0 0 0 1 1 1 ?2 1 ?1 0 ?? 1
MPC via Player Emulation The protocol is secure as long as the output wire ? has a value of 0. Since the formula computes majority - secure as long as adversary does not control majority of players. Complexity: Every atomic operation is emulated by a constant number of operations protocol complexity grows exponentially in the depth of the formula.
Efficient MPC via Player Emulation Still need two ingredients: 1. A secure 3-party protocol. 2. A logarithmic depth formula that computes majority using only ???3 gates.
Efficient MPC via Player Emulation Still need two ingredients: 1. A secure 3-party protocol. 2. A logarithmic depth formula that computes majority using only ???3 gates.
3-Party Protocols Can use BGW restricted to 3 players or better yet use the MPC made simple protocol of [Maurer02]. Maurer s protocol is simple and elegant but exponential in the number of players. For 3 players not an issue!
Efficient MPC via Player Emulation Still need two ingredients: 1. A secure 3-party protocol. 2. A logarithmic depth formula that computes majority using only ???3 gates.
Majority from Majorities 1. A randomized construction of majority-from- majorities [Valiant84]. A randomized protocol with statistical security. ???? ? = | ?(?)/? 1/2| 2. A deterministic but only close to optimal construction that outputs the majority value, if the input has a bias of at least 1/2log ?. ? 2 A weaker assumption suffices: EXP does not have subexponential- size circuits 1 1 2log ??. 3. If exponentially strong OWF exist a construction that can handle any bias. Conditional result.
Minimal number of players to obtain security against one active player Active Security Follow the same paradigm except that now we reduce ?-player protocols to 4-player protocols. Emulate virtual players by 4 virtual players out of which 1 can be malicious. Proceed as before but need a log-depth threshold ?/3-out-of-? formula composed of 2-out-of-4 threshold gates.
Summary 1. New approach to designing MPC protocols. 2. Improved protocols in a variety of settings: blackbox rings and Abelian groups. 3. Complexity theoretic question: Majority- from-majorities and threshold-from- threshold formulae.
