Paper 2022/1759

Bingo: Adaptively Secure Packed Asynchronous Verifiable Secret Sharing and Asynchronous Distributed Key Generation

Ittai Abraham, VMware Research
Philipp Jovanovic, University College London
Mary Maller, Ethereum Foundation
Sarah Meiklejohn, University College London, Google
Gilad Stern, Hebrew University of Jerusalem
Abstract

In this work we present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets or one high threshold secret with a total communication complexity of just $O(\lambda n^2)$ words. Bingo requires a public key infrastructure and a powers-of-tau setup. Using Bingo's packed secret sharing, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time. Using this agreement protocol in combination with Bingo, we obtain an adaptively secure high threshold asynchronous distributed key generation (ADKG) of standard field element secrets that uses $O(\lambda n^3)$ expected words and constant expected time. To the best of our knowledge, Bingo is the first ADKG to have an adaptive security proof and have the same asymptotic complexity of the best known ADKG's that only have non-adaptive security proofs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
AVSSpacked secret sharingByzantine faultsasynchronyDKGadaptive adversary
Contact author(s)
iabraham @ vmware com
p jovanovic @ ucl ac uk
mary maller @ ethereum org
s meiklejohn @ ucl ac uk
gilad stern @ mail huji ac il
History
2022-12-27: approved
2022-12-22: received
See all versions
Short URL
https://ia.cr/2022/1759
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1759,
      author = {Ittai Abraham and Philipp Jovanovic and Mary Maller and Sarah Meiklejohn and Gilad Stern},
      title = {Bingo:  Adaptively Secure Packed Asynchronous Verifiable Secret Sharing and Asynchronous Distributed Key Generation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1759},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1759}},
      url = {https://eprint.iacr.org/2022/1759}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.