Secure Multiparty Computation with Sublinear Preprocessing
Secure Multiparty Computation with sublinear preprocessing allows parties to jointly compute arithmetic circuits over private inputs with malicious security in a dishonest majority setting. The online execution involves the dealer generating correlated randomness, preprocessing, and cryptographic outputs. Beaver triples play a key role in achieving semi-honest security with minimal communication and overhead costs.
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
Secure Multiparty Computation Secure Multiparty Computation with Sublinear Preprocessing with Sublinear Preprocessing Elette Boyle Niv Gilboa Yuval Ishai Ariel Nof Reichman University Ben-Gurion University Technion Technion Eurocrypt 2022
Our Setting Our Setting ? parties jointly compute an arithmetic circuit over their private inputs Circuit defined over a finite field or the ring ?2? Addition and multiplication gates Malicious security Dishonest majority
MPC in the Preprocessing Model MPC in the Preprocessing Model Online execution Preprocessing ?1 Correlated Randomness ?5 ?2 ?(??, ,??) ?4 ?3
MPC in the Preprocessing Model MPC in the Preprocessing Model Online execution The Dealer ?1 Correlated Randomness ?5 ?2 ?(??, ,??) ?4 ?3
MPC in the Preprocessing Model: MPC in the Preprocessing Model: Dishonest Majority Setting Dishonest Majority Setting Inputs Correlated Randomness Preprocessing (The Dealer ) Online execution Outputs Cryptographic Expensive Information-theoretic Cheap
MPC in the Preprocessing Model: MPC in the Preprocessing Model: Dishonest Majority Setting Dishonest Majority Setting Inputs Correlated Randomness Preprocessing (The Dealer ) Online execution Outputs Two main metrics: Online/offline communication cost Size of correlated randomness
MPC in the Preprocessing Model: MPC in the Preprocessing Model: Dishonest Majority Setting Dishonest Majority Setting Semi-honest security Beaver triples [Bea91] a random multiplication triple ? , ? , ? ? is used to multiply shared [x] and [y]. Preprocessing Communication per multiplication Correlated randomness per multiplication 4 sent elements per party Circuit-independent [Bea91] 3 elements per party O(1) per party O(1) per party 2 sent elements per party Circuit-dependent [DNNR16, BGI19, BNO19] 2 elements per party With a PRG, can be compressed into 1 element per gate (to a single party)
The Overhead of Achieving Malicious Security The Overhead of Achieving Malicious Security SPDZ approach: authenticated Beaver triples [BDOZ11, DPSZ12, ] ? , ? , ? ? , ? , ? , ?? Semi-honest correlated randomness Malicious correlated randomness Online Communication cost: |semi-honest| Correlated randomness: Large fields: |semi-honest|X2 Small fields: |semi-honest|X ?(=statistical security parameter) Offline cost: expensive [DPSZ12,KOS15,KPR18, .] Other approaches: MiniMac[DZ13, ], Tiny Table [DNNR17, ], MPC-in-the-head [IPS08, ] The main bottleneck!
The Dream Goal: Silent Preprocessing (via PCGs) The Dream Goal: Silent Preprocessing (via PCGs) The dealer gives each party a short correlated seed Each party locally expands it to receive shares of authenticated triples Online cost: |Semi-honest| Correlated randomness: sublinear Offline cost: sublinear
But Concretely efficient PCGs exist for: Un-authenticated triples Authenticated triples for 2-party computation over large fields [BCG+20].
Our Approach Our Approach [?1],[?1],[?1?1] . . Seeds for generating un-authenticated Beaver triples Semi-honest computation [??],[??],[????] Sublinear amount of correlated randomness correlated randomness for verification Light verification step outputs
Our Approach Our Approach [?1],[?1],[?1?1] . . Seeds for generating un-authenticated Beaver triples un-authenticated triples Sublinear protocol for generating Semi-honest computation [??],[??],[????] MPC with sublinear communication cost Sublinear amount of correlated randomness correlated randomness for verification Light verification step outputs
Our Result Our Result A protocol in the preprocessing model to compute any arithmetic circuit ? : Sublinear offline communication cost: ?( ? ?) ring elements Sublinear correlated randomness: ?( Non-cryptographic online phase: ? ? elements sent per party ? ?) ring elements Security of the protocol is based on: Any sublinear-communication protocol for generating pseudorandom (un- authenticated) multiplication triples (e.g., implied by LPN). AHE (Additively-homomorphic encryption)
Comparison to Previous Work Comparison to Previous Work SPDZ approach [BGIN21] This work Online |SH|+constant |SH|+log(|C|) ? |SH|+ communication Correlated randomness ? ? log ? ? ? ? Offline ? ? ? ? ? ? communication ?=statistical security parameter |SH| = cost of the semi-honest protocol
Main Building Block Main Building Block: ZK Fully Linear Proof Systems : ZK Fully Linear Proof Systems [BBCGI19] [BBCGI19] Accept/ reject Prover Verifier ? ? ? ?? ? ? ? = ? The verifier is allowed to run linear queries on the proof + input Completeness, soundness, zero-knowledge
From Fully Linear Proof Systems to Distributed ZK From Fully Linear Proof Systems to Distributed ZK [BBCGI [BBCGI19 19] ] ?1 ?1 = ?1 If ? and ? are shared via a linear secret sharing scheme, then the verifiers can query independently and exchange their answers V1 Prover ? ?1 ?2 ? ?? ?2 ?2 V2 = ?2 ? If: ? is robustly shared across the parties The statement to be proven is a degree-2 polynomial over x Then: There exists a distributed ZK proof with sublinear communication in ? and with soundness against any collusion between the prover and a subset of verifiers
Malicious Security in MPC via Distributed ZK Proofs Malicious Security in MPC via Distributed ZK Proofs Prove correctness of multiplications with sublinear communication The statement for proving multiplications correctness can be represented by a degree-2 polynomial over inputs that are shared across the parties Honest majority [BBCGI19,BGIN19,BGIN20,BBGHIN20]: The secret sharing is inherently robust Dishonest majority: How to achieve robustness (without increasing the correlated randomness)?
The Two Main Technical Ideas The Two Main Technical Ideas [BGIN [BGIN21 21] ] 1. Define a robust secret sharing scheme using the dealer ``star secret sharing 2. Maintain the secret sharing scheme throughout the verification process Use the dealer as a verifier in the distributed zk proof!
``Star ``Star Secret Sharing: Robustness in the Secret Sharing: Robustness in the Dishonest Majority Setting Dishonest Majority Setting Maintain the following secret sharing over multiplication gate s inputs and outputs: Let ? be the secret on the wire Each party ?? holds ? = ? ? and ??, such that r = ?=1 The dealer knows ?1, ,?? ?1 ?5 ?2 ? ?? Dealer ?4 ?3 This is a robust secret sharing: It can be reconstructed by an honest party and the dealer This scheme is implicitly used in natural semi-honest protocols
Verifying Correctness of Multiplications Verifying Correctness of Multiplications The parties want to verify that ? ? ? = 0 This is equivalent to checking that ? + rz ? + ?? ? + ?? = 0 Given ? multiplication triples ?1,?1,?1, ,(??,??,??), the parties wish to verify that: ? ?? ( ??+ rk,z ??+ ??,? ??+ ??,?) = 0 ?=1
Verifying Correctness of Multiplications Verifying Correctness of Multiplications ? ?? ( ??+ ??,? ??+ ??,? ??+ ??,?) = ? ?=? Known by all parties Known by the dealer (and shared to the parties) ? ? = 0 Known by all parties Known by the dealer (and shared to the parties)
Verifying Correctness of Multiplications Verifying Correctness of Multiplications ? ? = 0 Known by all parties Known by the dealer (and shared by the parties) 2-degree polynomial Input is shared in a robust way Can prove the statement using Distributed ZK with sublinear communication (in the size of the input)
The Verification Protocol The Verification Protocol ? ? = 0 ? ? = ? ? Prover ? parties The input and the proof are additively shared between each party and the dealer ? Star-sharing of the answer s dealer Robustness of the secret sharing soundness of the proof How to emulate the prover?
The Verification Protocol: Emulating the prover The Verification Protocol: Emulating the prover ? ? = 0 Known by all parties Known by the dealer (and shared by the parties) Each party ?? computes its share ?? of the proof Each party ?? star shares its share: Broadcast ??= ?? ?? The parties locally compute ? = ?=1 ? ??
Using the Dealer as a Verifier Using the Dealer as a Verifier Each piece of information is known by an honest participant Robustness Soundness The statement to be proven is a 2-degree polynomial Sublinear communication Communication is sublinear in the input size The amount of correlated randomness is also sublinear The dealer performs computations only over random data Can preprocess the computation
Concrete Costs of the Verification Step Concrete Costs of the Verification Step Communication: 22 Correlated Randomness: ? ? ring elements ? ? ring elements ? = statistical security parameter
What does the Dealer Compute? What does the Dealer Compute? ?? ? ? ? ?? ??(?) = ?2 ??? = Beaver triples . . . . . . ? ? ?? = ? ? polynomials of degree ?
Distributing the Dealer Distributing the Dealer ? Small MPC to generate ciphertexts AHE= Additively homomorphic encryption Encrypted Encrypted Encrypted ?? ? ? ? ?? ??(?) = Sublinear protocol for generating shares of unauthenticated Secure ??? Decryption of Cipher texts ?2 = Shares of Beaver triples Beaver triples ? . . . . . . ? ? ?? = ? ? polynomials of degree ?
Distributing the Dealer with Sublinear Communication: Distributing the Dealer with Sublinear Communication: Security and Efficiency Security and Efficiency Semi-honest security: previous slide Covert security: Generate N executions (commit to seeds) and open N-1 To verify an execution: just open the PCG seeds and the point ? Malicious security: Feasibility: use generic communication-preserving compiler [NN01] Efficiency: Problem: What happens if a corrupted party use incorrect Beaver shares? Solution for large fields: Succinctly commit and prove Requires Linear-only assumption on the AH encryption scheme
Thank you! Thank you!
