Multi-Party Computation Guarantees and Broadcast Optimization
Explore the concept of Multi-Party Computation (MPC) with guaranteed output delivery, selective abort, unanimous abort, and identifiable abort for enhanced fairness and performance. Learn about minimizing setup in broadcast and achieving relaxed identifiability. Dive into the motivations behind MPC rounds and the use of broadcast in MPC scenarios.
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
Minimizing Setup in Broadcast- Optimal Two Round MPC Ivan Damg rd (Aarhus University), Divya Ravi (Aarhus University), Luisa Siniscalchi (Technical University of Denmark), Sophia Yakoubov (Aarhus University)
Multi-Party Computation Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness ? ?2 ? ?1 ? ? = ?(?1 ,?2 ,?3) ?3
Multi-Party Computation: Guarantees Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness ? ? ?
Multi-Party Computation: Guarantees Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness ? ? ?
Multi-Party Computation: Guarantees Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness Bruce did it! did it! Bruce
Multi-Party Computation: Guarantees Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness ? ?
Multi-Party Computation: Guarantees Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness What about achieving a relaxed version of identifiability? Could be useful to detect malfunctioning machine Better performances ?
Multi-Party Computation: NEW Guarantees Selective Identifiable Abort Guaranteed output delivery Selective Abort Unanimous Abort Identifiable Abort Fairness Bruce did it! Honest parties never accuse other honest parties ? ?
Motivation - #Rounds needed for MPC? At least two (else residual attack) - Broadcast is expensive - Which are the possible guarantees when the broadcast is only used in one round? No rounds? [CGZ20] dishonest majority [DMRSY21] honest majority use of PKI
Our Contribution: Honest Majority Relying only on CRS Corruption Threshold Selective Abort Unanimous Abort Identifiable Abort Fairness Guaranteed Output Delivery ? 3 ? <? ? <? BC BC [GLS15,PR18 [CGZ20] 2 ] BC BC ** [GIKR02] [CGZ20] 3 ? 3 ? <? ? <? P2P P2P [LSP82] [PR18] [CL14] [GLS15,PR18 [CGZ20] 2 ] ** P2P P2P ** [CGZ20] [GIKR02] [DMRSY21 3 ] ? 3 ? <? ? <? BC P2P [CGZ20] [PR18] [GLS15,PR18 2 ] BC P2P ** [CGZ20] [This] [GIKR02] ** 3 ? 3 ? <? ? <? P2P BC [CGZ20] ** [GLS15,PR18 [This] 2 ] P2P BC ** [CGZ20] [This] [GIKR02] 3 ** t > 1 New results *Positive results: No private channels in R1
Our Contributions Whats possible with SIA? ? 3 ? <? ? <? ? < ? 2 3 BC BC CRS [CGZ20] *Observing that [CGZ20] holds also for this setting BC BC PKI P2P P2P CRS ** [This] [This] P2P P2P PKI ** BC-BC (resp. P2P-BC) IA can be transformed into BC-P2P with SIA [This] ** P2P BC CRS [This] * [This] P2P BC PKI [DMRSY21] BC P2P CRS ** [This] [This] BC P2P PKI
P2P-BC IA, CRS ? <? 3 General blueprint of [CGZ20] and [DMRSY21] Show a compiler from BC-BC to P2P-BC Different challenges without PKI
P2P-BC: from BC-BC to P2P-BC R1 messages R1: BC R2 messages R2: BC
P2P-BC: from BC-BC to P2P-BC R1 messages R1: P2P R2 messages R2: BC Problem: R2 messages based on inconsistent R1 messages could reveal too much!
P2P-BC: from BC-BC to P2P-BC b=0 b=1 Bit b R1 messages R1: P2P Mechanism to distribute tokens so that everyone gets the same tokens R2: BC R2 msg Everyone extracts R2 messages and computes output
One-or-Nothing Secret Sharing with Intermediaries b=0 First-level shares b=1 Focus on one share sR How to verifiably and reliably transfer sR? I did not get my share! I need the support of (n - t) intermediaries I have sent sR Receiver R Second-level shares Intermediaries
How to transfer sub-shares without private channels or PKI ? Exchange public keys in the first round R 1 1 1 2 R 2 2 R 3 3 R PK1 , PK2, PK3, PK4 3 4 1 2 4 3 R 4 R 4 Both transfers in a single broadcast round Transfer decryption capability
Thanks! https://eprint.iacr.org/2022/293
Consider n = 4, t = 1 I have support of (n - t) intermediaries = {1,2,3} R 1 1 1 2 R 2 2 R 3 3 R PK1 , PK2, PK3, PK4 3 4 1 2 3 4 R 4 R 4
Consider n = 4, t = 1 I have support of (n - t) intermediaries = {1,2,3} R 1 1 1 2 R 2 2 R 3 3 R PK1 , PK2, PK3, PK4 3 4 1 3 2 4 R 4 R 4
Consider n = 4, t = 1 I have support of (n - t) intermediaries = {1,2,3} I have support of (n - t) intermediaries = {1,2,4} R 1 1 1 2 R 2 2 R 3 3 R PK1 , PK2, PK3, PK4 3 4 1 3 2 4 R 4 R 4
Consider n = 4, t = 1 I have support of (n - t) intermediaries = {1,2,3} I have support of (n - t) intermediaries = {1,2,4} R 1 1 1 2 R 2 2 R 3 3 R PK1 , PK2, PK3, PK4 3 4 sRsuccessfully reconstructed if second-level threshold is t = 1 1 3 2 4 R 4 4 R Takeaway: n > 3t suffices! n - 2t intermediaries are happy with both dealer and receiver second-level threshold < n - 2t t < =
Construction (n > 3t) First-level shares with threshold (n - t - 1) Second-level shares with threshold (n - 2t - 1) >= t b=0 b=1 Vote Share Broadcast relevant key R 1 1 R 1 1 1 1 2 2 R R 2 2 2 2 3 R 3 R 3 3 R R 4 3 4 3 3 1 2 4 R R 4 4 R 4 R 4 3 1 2 4
Correctness: If (n t) parties vote for 0 and no one is identified, 0 token is reconstructed First-level shares with threshold (n - t - 1) Second-level shares with threshold (n - 2t - 1) >= t Vote Share R 1 1 R 1 1 1 1 2 2 R R 2 2 2 2 3 R 3 R 3 3 R R 4 3 4 3 3 1 2 4 R R 4 4 R 4 R 4 3 1 2 4
Correctness: If (n t) parties vote for 0 and no one is identified, 0 token is reconstructed Privacy: If < (n - 2t) honest parties vote for 1, nothing about 1 token is revealed First-level shares with threshold (n - t - 1) Second-level shares with threshold (n - 2t - 1) >= t Adversary has access to < (n - 2t + t) = (n - t) first-level shares Vote Share I voted for 0, sR is reconstructed successfully R 1 1 R 1 1 1 1 2 2 R R 2 2 2 2 3 R R 3 3 3 R R 4 3 4 3 Adversary cannot learn my first-level share 3 1 2 4 R R 4 4 R 4 R 4 3 1 2 4
Correctness: If (n t) parties vote for 0 and no one is identified, 0 token is reconstructed Privacy: If < (n - 2t) honest parties vote for 1, nothing about 1 token is revealed First-level shares with threshold (n - t - 1) Second-level shares with threshold (n - 2t - 1) >= t Implies that at most one secret is reconstructed (as there cannot be two disjoint honest sets of size (n - 2t)) Vote Share R 1 1 R 1 1 1 1 2 2 R R 2 2 2 2 3 R R 3 3 3 R R 4 3 4 3 3 1 2 4 R R 4 4 n - t >= (n - 2t) + (n - 2t) Implies 3t >= n R 4 R 4 3 1 2 4
