Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing
The innovative concepts of adaptivity and asynchrony in verifiable secret sharing and distributed key generation by Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, and Gilad Stern. Dive into the main results, key assumptions, and the packed AVSS protocol in this groundbreaking research.
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
Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn and Gilad Stern
Background AVSS and DKG Many schemes and protocols rely on setup for structured randomness E.g. threshold signature schemes require correlated keys Without trusted party, parties need to perform setup (DKG) AVSS is an important building block for many interactive protocols Coin flipping Leader Election MPC Asynchrony and adaptive security important for resilience
Main Results Bingo: Packed AVSS protocol Optimal corruption threshold of ? > 3? Adaptively secure ?(??2) words for sharing ?(?) secrets, ?(??2) per reconstruction Can batch-reconstruct and reconstruct sums of secrets Shares secrets along a high-degree polynomial (up to degree 2?) ADKG: Adaptively secure ADKG for BLS threshold signatures High-threshold setup Expected ?(??3) words and ?(1) rounds
Main Results Bingo assumptions: KZG setup, q-SDH, AGM for an additional property of KZG DKG assumptions: Previous assumptions for Bingo, in addition to OMDL assumption [BL22]
Packed AVSS Intuition Share ?0, ,?? Dealer ?0, ,?? Done Done Share Done Done
Packed AVSS Intuition - Reconstruct ?? ?? Rec k ?? ?? Rec k ?? Rec ?? Rec k ?? Rec k ??
Tool Bivariate PCS Bivariate polynomial commitment based on univariate KZG In order to commit to a polynomial ?(?,?) of degree 2? in ? and ? in ?, commit to ?(?,?) for ? ? + 1 KZG has homomorphic commitments, allows to interpolate other commitments Use a hiding variant of KZG
Classic VSS Approach Dealer gets (single) secret ?0, samples ?(?,?) of degree ? ? such that ? 0,0 = ?0 Party ?receives a row ?(?,?)and column ? ?,? Each row and column intersect Parties can check that intersecting values are consistent Parties can help parties that didn t get row/col by sending shared points ? 0,0 ? 0,1 ? 1,0 ? 1,1 ?(?,0) ?(?,1) ?(?,?) ? 0,? ? 1,?
Bingo Dealer gets ?0, ,?? and samples a polynomial ?(?,?) of degree 2? in ? and ? in ? such that ? ?,0 = ?? (asymmetric degree in [PCR15, ]) Long rows, short columns Broadcast commitment and send row/col Parties send each other intersecting points Before terminating, make sure that ? + 1 honest parties have their row/col To reconstruct ?? send values along ( ?) th column
Bingo Proof Intuition Consistency guaranteed by commitment Binding: Once ? + 1 honest parties have rows, they completely define all (short) columns, and thus the polynomial Termination uses cascading effect: If ? + 1 honest parties have rows, all honest parties will get enough points for columns If every honest party gets columns, everybody gets rows
ADKG BLS (and other schemes) require secret keys ?? to lie on a polynomial ?, with corresponding public keys ??? Standard approach for random polynomial: Each party shares a random polynomial (Bingo) Choose ? + 1 dealers who complete ? ??? (consensus [AJM+21], use Bingo for internal randomness) Define ? to be the sum of their polynomials Reconstruct ??? using adapted KZG openings
Conclusion Bingo: Packed AVSS protocol Adaptively secure ?(??2) words for sharing ?(?) secrets, ?(??2) per reconstruction ADKG: Adaptively secure DKG for BLS threshold signatures High-threshold setup Expected ?(??3) words and ?(1) rounds
