Efficient Fully Malicious Multiparty Computation Protocol

Dishonest Majority Constant Dishonest Majority Constant- -Round MPC with Linear Communication MPC with Linear Communication from DDH from DDH Round Ankit Kumar Misra Junru Li Vipul Goyal University of California, Los Angeles Tsinghua University NTT Research Carnegie Mellon University Chenkai Weng Yifan Song Rafail Ostrovsky Arizona State University Tsinghua University University of California, Los Angeles Shanghai Qi Zhi Institute

Multiparty Computation Multiparty Computation Setting ? parties ? corrupted Complete network of bilateral channels

Multiparty Multiparty Computation Computation Setting ?1 ? parties ?6 ?2 ? corrupted Complete network of bilateral channels Goal ?5 ?3 ?4 Compute function ? ?1, ,?? ?

Multiparty Multiparty Computation Computation Setting ? ? parties ? ? ? corrupted Complete network of bilateral channels Goal ? ? ? Compute function ? ?1, ,?? ? Privacy: Adversary does not learn anything beyond the computed output

Multiparty Computation Multiparty Computation Setting Synchronous Network Maximum Corruption ? = ? 1 Fully Malicious Adversary (Security with Abort)

Known Results from Literature Known Results from Literature Communication-Efficient but Non-Constant Round MPC SPDZ protocol [DPSZ12] and its follow-ups [DKL+13, LOS14, KOS16, KPR18, BCS19, BNO19, EGP+23]. Communication: [RS22] achieves ?( ? ?) communication relying on PCG [BCG+19, BCG+20, WYKW21] Round Complexity: Linear in the circuit depth Constant Round but Communication-Heavy MPC BMR protocol [BMR90, DI05] and its follow-ups [LPSY15, BLO16, BLO17, HSS17, WRK17, HOSS18a/b, YWZ20, BCO+21]. Communication: State-of-the-art requires ?( ? ?2) communication Round Complexity: Constant

Our Question Our Question Can we construct a fully malicious MPC protocol in the dishonest majority setting that achieves the best in both worlds, i.e., with constant rounds and linear communication complexity?

Our Result Our Result Theorem. Assuming DDH, LPN, and random oracles, there is a computationally secure constant-round MPC protocol against a fully malicious adversary controlling up to ? 1 parties with communication of ?( ? ? ?) bits, where ? is the computational security parameter. Remarks. 1. LPN assumption Instantiation of SPDZ protocol [RS22]. 2. Random oracle Concrete efficiency. Can be replaced by PRG

Our Techniques Our Techniques Main Difficulty in Previous Solutions: Construct Gate Tables Following the BMR template, all parties need to jointly compute a symmetric-key encryption algorithm where both the key ? and the message ? are secretly shared. Our Ideas 1. Use a public-key encryption scheme. Public key can be learnt by all parties. Only message is secretly shared. 2. Use a key-homomorphic PKE to prepare public-private key pairs efficiently. Can be instantiated assuming DDH. 3. Message m to be encrypted is secret shared: each party directly encrypts his share locally. All ? cipher-texts together can be viewed as a cipher-text of ?.

Limitations of Our Result Limitations of Our Result Free XOR: Do not support the freeXOR technique. Our construction is based on DDH, which works over a large prime field. The freeXOR technique requires to use a binary-extension field. Computational Complexity: PKE operations are less efficient than symmetric-key operations. (But can be local) Garbled Circuit Size: Scale linearly with the number of parties. As a result, the evaluation also scales with ?

Outline Outline 1. Review of Yao s Garbled Circuits and BMR Template 2. Our Solution 3. Experiment and Comparison

Yaos Garbled Circuit Yao s Garbled Circuit ?(0), ?(1) ?? ? ?(0), ?(1) ? AND ?? ?(0), ?(1) ?? ? Idea: For each wire ?, prepare a random mask bit ?? and two random wire labels ( ?(0), ?1 ) The evaluator always learns the masked wire value ??+ ?? (?? = value on the wire). Also learns the label ?(??+ ??) but not the other one.

Yaos Garbled Circuit Yao s Garbled Circuit ?(0), ?(1) ?? ? ?(0), ?(1) ? AND Garbler ?? ?(0), ?(1) ?? ? ??+ ??= 0 ??+ ??= 1 ?(0) ?(1) For wires a,b, say evaluator learns ? = ??+ ??,? = ??+ ?? Need to learn masked value on output wire: ??+ ??= 0 Enc ?? 0,0 ,? 0,0 Enc ?? 1,0 ,? 1,0 ?(0) ? ?,? = ? + ?? ? + ?? + ?? ??+ ??= 0 Enc ?? 0,1 ,? 0,1 Enc ?? 1,1 ,? 1,1 ?(1) Idea: Garbler computes four cipher-texts, corresponding to the 4 possible cases of (? = ??+ ??,? = ??+ ??) Evaluator with ?(??+ ??) and ?(??+ ??) can only decrypt ?(??+ ??)

BMR Template BMR Template Idea: All parties jointly emulate the garbler and compute the four cipher-texts. 1. Jointly Sample Mask Bits and Wire Labels Each party samples random values as his additive shares of ??, ?0 , ?(1) 2. For every (?,?), compute ? ?,? and ?? ?,? Can be done by any dishonest majority MPC such as SPDZ 3. *Jointly compute the cipher-text* Encrypt ?? ?,? ,?(?,?) by ?(?) and ?(?)

BMR Template BMR Template Idea: All parties jointly emulate the garbler and compute the four cipher-texts. 1. Jointly Sample Mask Bits and Wire Labels Main Difficulty Each party samples random values as his additive shares Computing the cipher-text securely where both key of ??, ?0 , ?(1) and message are secretly shared. 2. For every (?,?), compute ? ?,? and ?? ?,? Need to use the underlying encryption scheme in a Can be done by any dishonest majority MPC such as SPDZ non-black-box way. 3. Jointly compute the cipher-text Encrypt ?? ?,? ,?(?,?) by ?(?) and ?(?)

Previous Attempts Previous Attempts Use Separate Wire Labels for Different Parties [DI05, LPSY15, HSS17, WRK17, YWZ20] Benefit: Use the underlying PRG of the encryption scheme in a black-box way. Downside: Increase the garbled circuit size and the communication complexity by a factor of ?. Known solutions require ?( ? ?2) communication Targeting for Sub-optimal Corruption Threshold [HOSS18a/b, BGH+23] Benefit: Can shave a factor of ? in the communication and achieve ?( ? ?) communication Downside: Do not work for the optimal corruption setting Use MPC-Friendly Encryption Schemes [BLO17, BCO+21, GYKW24] Benefit: Can potentially achieve linear communication Downside: Not concretely efficient, may incur a large constant multiplicative overhead or even not constant-round.

Outline Outline 1. Review of Yao s Garbled Circuits and BMR Template 2. Our Solution 3. Experiment and Comparison

Starting Point Starting Point One entry of the garble table sk Input Wire Label (or two) Encpk(?) Encryption ? Output Wire Label Main Difficulty Computing the cipher-text securely where both key and message are secretly shared.

Starting Point Starting Point pk can be learnt by all parties in clear One entry of the garble table sk ,pk Input Wire Label Encpk(?) Encryption ? Output Wire Label Idea: Use Public-key Encryption Only the message is secretly shared

Starting Point Starting Point pk can be learnt by all parties in clear One entry of the garble table sk ,pk Input Wire Label Encpk(?) Encryption ? Output Wire Label Remaining Difficulties: 1. How to prepare sk ,pkefficiently? Need 2 pairs for each wire as wire labels. 2. How to efficiently compute Encpk(?)?

Solving Difficulty 1 Solving Difficulty 1 Goal: Prepare sk ,pk Idea: Use a PKE that is linearly homomorphic for public keys. sk1,pk1, sk2,pk2 sk1+ sk2,pk1 + pk2 1. Sample Individual key pairs. Each party ?? samples sk?,pk? Linear Communication Per Wire/Gate 2. Aggregating public keys ? The first party ?1 collects pk? and computes pk = ?=1 Parties get sk = sk1, ,sk?,pk pk?. Then broadcast pk. 3.

Solving Difficulty 2 Solving Difficulty 2 Goal: Compute Encpk(?) from pk, ? Seems like we still need to compute the encryption algorithm in a non-black-box way Main Observation The cipher-text is to allow the evaluator to decrypt ?. No need to keep the original compact form!

Solving Difficulty 2 Solving Difficulty 2 Goal: Compute Encpk(?) from pk, ? Seems like we still need to compute the encryption algorithm in a non-black-box way 1. Encrypting each share individually. Each party ?? locally computes ct?= Encpk(??) of his message share ?? Linear Communication Per Gate 2. Send Encpk? = (ct1, ,ct?) to the evaluator Each party sends one cipher-text to the evaluator ? During Evaluation: Evaluator decrypts ?? from ?? and reconstructs ? = ?=1 ??

Summary of Our Idea Summary of Our Idea Each party locally encrypts his share. Sufficient for evaluator. Relying on PKE with homomorphism in public keys Encpk(?1) Encpk(?2) sk ,pk Input Wire Label Encryption ? Encpk(??) Output Wire Label Our Ideas 1. Use a key-homomorphic public-key encryption scheme to prepare sk ,pk. 2. Instead of having a single cipher-text of ?, each party directly encrypts his message share. All ? cipher-texts together can be viewed as a cipher-text of ?.

Instantiation of PKE Instantiation of PKE Goal: Only Linear Homomorphism in keys but not messages A natural choice: El-Gamal Encryption based on DDH Gen : sk,pk = ?sk Key-Homomorphism: ??1,??1, ??2,??2 ??1+ ??2,??1 ??2 Enc ?,pk :(??,pk? ?) El-Gamal Encryption is also multiplicatively homomorphic in messages, but we do not need this property.

Instantiation of PKE Instantiation of PKE Goal: Only Linear Homomorphism in keys but not messages A natural choice: El-Gamal Encryption based on DDH Gen : sk,pk = ?sk Key-Homomorphism: Enc ?,pk :(??,pk? ?) ??1,??1, ??2,??2 ??1+ ??2,??1 ??2 pk?is indistinguishable from a random group element, but not a random string A Small Issue The message space of the El-Gamal Encryption is the group associated with the DDH assumption. The message we need to encrypt in the construction is an additive share, which is in {0,1, ,? 1}

Instantiation of PKE Instantiation of PKE Goal: Only Linear Homomorphism in keys but not messages A natural choice: El-Gamal Encryption based on DDH Solution 1: Extractor + PRG Gen : sk,pk = ?sk View pk? as a random source 1. Has enough (pseudo)entropy Enc ?,pk :(??,pk? ?) Apply a strong seeded extractor on pk? to obtain 2. a pseudo-random string. pk?is indistinguishable from a random group element, but not a random string 3. Apply a PRG to stretch the pseudo-random string and use the result as the OTP key.

Instantiation of PKE Instantiation of PKE Goal: Only Linear Homomorphism in keys but not messages A natural choice: El-Gamal Encryption based on DDH Solution 2: Random Oracle Gen : sk,pk = ?sk View pk? as a random source 1. Enc ?,pk :(??,pk? ?) Has enough (pseudo)entropy Apply RO on pk? and use the result as the OTP key. 2. pk?is indistinguishable from a random group element, but not a random string

Towards Malicious Security Towards Malicious Security Use a maliciously secure SPDZ protocol with linear communication [RS22] Recall Our Ideas 1. Parties send shares of pk to a single party who then reconstructs and announces. The king may compute and distribute an incorrect pk. 2. Instead of having a single cipher-text of ?, each party directly encrypts his message share. A corrupted party may encrypt an incorrect share.

Towards Malicious Security Towards Malicious Security Use a maliciously secure SPDZ protocol with linear communication [RS22] Recall Our Ideas 1. Parties send shares of pk to a single party who then reconstructs and announces. The king may compute and distribute an incorrect pk. Solution: Use IT-MAC 1. Generate a random authenticated sharing sk = sk , , sk The reconstruction result sk can be verified by the MAC key and the MAC sk 2. Prepare pk from sk as above Linearly Homomorphic ? 3. Check a random linear combination of all key pairs sk?,pk? ?=1 If any pair is incorrect, their random linear combination is also incorrect w.h.p.

Towards Malicious Security Towards Malicious Security Use a maliciously secure SPDZ protocol with linear communication [RS22] Recall Our Ideas 2. Instead of having a single cipher-text of ?, each party directly encrypts his message share. A corrupted party may encrypt an incorrect share. Solution: Check Consistency with pk Recall that ? is the secret key associated with the output wire. Evaluator can verify ? by checking its consistency with pk.

Optimization Optimization ?1 , ?0 are secret keys Use the same for: The difference between every pair of wire labels: = ?1 ?0 The MAC key of the underlying SPDZ protocol: ? = ? , , ? Benefit: Only need to prepare ? and pk?(0) = ? ?(0). The other public key can be locally computed: pk?1 = ? pk?(0) Simplify the computation of ?

Outline Outline 1. Review of Yao s Garbled Circuits and BMR Template 2. Our Solution 3. Experiment and Comparison

Communication Complexity Communication Complexity We compare with the following three works for communication complexity. [WRK17,YWZ20] follows the technique in [DI05]: Use cryptographic primitives in a black- box way but require quadratic communication. [BCO+21] considers a concrete instantiation of the symmetric-key encryption scheme based on LPN. Can potentially achieve linear communication when using [RS22] for the underlying SPDZ. All three works support free XOR. Have taken into consideration in the comparison.

Communication Complexity Communication Complexity Comparison with [BCO+21]: 10x less communication for AES. 20x less communication for circuits with #AND = #XOR. Comparison with [WRK17,YWZ20]: Less communication when having 16 parties for AES, and 8 parties for circuits with #AND = #XOR.

Limitations and Future Directions Limitations and Future Directions Free XOR: Do not support the freeXOR technique. Our construction is based on DDH, which works over a large prime field. The freeXOR technique requires to use a binary-extension field. Computation Complexity: PKE operations are less efficient than symmetric-key operations. Garbled Circuit Size: Scale linearly with the number of parties. As a result, the evaluation also scales with ? Future Direction: Achieve constant-round MPC based on symmetric-key primitives with Free XOR and garbled circuit size that is independent of ?.

Thanks! Thanks!

Running Time Running Time We assume random authenticated sharings and triples used for SPDZ have been prepared (Garbling Time, Sending Garbled Tables) per AND gate in ?? ? seconds Garbling time depends on both communication and computation. (See next page) Second term only depends on the communication complexity.

Running Time Running Time We assume random authenticated sharings and triples used for SPDZ have been prepared sk ,pk SPDZ Protocol Local Encryption PKE operation spends most of time for large bandwidth, and accounts 50% for small bandwidth.

Running Time Running Time We assume random authenticated sharings and triples used for SPDZ have been prepared Evaluation Time per AND gate in ?? ? seconds Evaluator s running time scales linearly with ?. Second line considers a powerful evaluator with multiple threads (up to 16 threads) Third line considers evaluating ? instances (up to 16 instances) and each party acts as the evaluator for 1 instance.

Optimization Optimization ?1 , ?0 are secret keys Use the same for: The difference between every pair of wire labels: = ?1 ?0 The MAC key of the underlying SPDZ protocol: ? = ? , , ? Remarks about Free XOR: The wire labels are in a prime field since they are encryption keys of the El Gamal Encryption Scheme. Not compatible with Free XOR technique, which relies on a binary extension field. Remark about RO: This optimization only works assuming RO due to circular encryption.