Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation

Ittai Abraham; Philipp Jovanovic; Mary Maller; Sarah Meiklejohn; Gilad Stern

Paper 2022/1759

Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation

Ittai Abraham, Intel Labs

Philipp Jovanovic, University College London

Mary Maller, Ethereum Foundation, PQShield

Sarah Meiklejohn, University College London, Google

Gilad Stern, Hebrew University of Jerusalem

Abstract

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 with a total communication complexity of words, where is the security parameter and is the number of parties. Using Bingo, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses expected words and constant expected time, which we in turn use to construct an adaptively secure high-threshold asynchronous distributed key generation (ADKG) protocol that uses expected words and constant expected time. To the best of our knowledge, our ADKG is the first to allow for an adaptive adversary while matching the asymptotic complexity of the best known static ADKGs.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: AVSS packed secret sharing Byzantine faults asynchrony DKG adaptive adversary
Contact author(s): Ittai abraham @ intel com
p jovanovic @ ucl ac uk
mary maller @ ethereum org
s meiklejohn @ ucl ac uk
gilad stern @ mail huji ac il
History: 2023-06-08: revised; 2022-12-22: received; See all versions
Short URL: https://ia.cr/2022/1759
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1759,
      author = {Ittai Abraham and Philipp Jovanovic and Mary Maller and Sarah Meiklejohn and Gilad Stern},
      title = {Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1759},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1759}
}