Asynchronous Agreement on a Core Set
Efficient asynchronous VSS and MPC protocols for achieving agreement on a core set in constant time. Dive into network and adversary models, challenges, and optimal resilience strategies. Delve into asynchronous multiparty computation and the state-of-the-art advancements in agreement protocols. Discover the intricacies of packed AVSS, perfect AMPC expected complexity, and improvements in protocol efficiency.
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
Asynchronous Agreement on a Core Set in Constant Time and More Efficient Asynchronous VSS and MPC Ittai Abraham Gilad Asharov Arpita Patra Gilad Stern
Network and Adversary Model Fully connected network, ? parties Asynchrony Stronger adversarial model Network-speed Challenges: how long do we wait? Adaptive malicious adversary Optimal resilience (? > 3? for consensus, ? > 4? for AVSS) Perfect security Analyzed in the UC framework
Asynchronous Multiparty Computation ?1 {1,2,3} ?(?1, ,?4) ?1 ?2 {1,2,4} ?4 ? {1,3,4} ?(?1, ,?4) ?2 ?(?1, ,?4) ?4 ?(?1, ,?4) ?3 ?3 3
Agreement on a Core Set State-of-the-art: BCG 93 and BKR 94 ? ? binary agreements (?7log?) expected bits ?(log?) expected rounds Our work: 1 multivalued agreement ?(?4log?) expected bits ?(1) expected rounds ?3 log?
Packed AVSS Intuition Share ?1, ,?? Dealer Done ?1, ,?? Done Share Done Done
Packed AVSS Intuition - Reconstruct ?? Rec k ?? Rec k ?? ?? ?? Rec ?? Rec k ?? Rec k ??
Packed AVSS Improvements State-of-the-art:Choudhury and Patra 22 ?(?4log?) bits for sharing ?(?) secrets Our work: ? ?3log? bits for sharing ? ? secrets Can reconstruct sums/batches
Perfect AMPC Expected Complexity ?(??6+ ???)[BCG 93] ?(??5+ ???) [Srinathan, Rangen 00] ?(??3+ ???)[BH 07] ?(??2+ ???)[Patra, Choudhury, Rangan 10] ?(?? + ???) [Abraham, Asharov, Patil, Patra 24] All works with (? + log?) rounds * ?=num of mult., D=depth of circuit
AMPC Expected Complexity Best prior [AAPP 24]: expected? ?? + ??2+ ?7log? bits, ?(? + log?) rounds Our work: expected? ?? + ??2+ ?4log? bits, ?(? + 1) rounds State-of-the-art synchronous MPC [AAPP23]: expected? ?? + ??2+ ?4log? bits, ?(?) rounds SotA Synchronous = SotA Asynchronous! * ?=num of mult., D=depth of circuit
Asynchronously Validated Asynchronous Byzantine Agreement (AVABA) Multivalued consensus Based on No Waitin Hotstuff [AJMMS 23] Asynchronous external validity Information-theoretic parallel of external validity Similar to BKR s dynamic predicate Secure when ? > 3? given leader- election
