Paper 2023/292

A Formal Treatment of Distributed Key Generation, and New Constructions

Chelsea Komlo, University of Waterloo
Ian Goldberg, University of Waterloo
Douglas Stebila, University of Waterloo

In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is flexibility; i.e., any aggregatable VSS and NIKE scheme can be employed, and the construction will remain secure. To prove the security of our generic construction, we introduce formalized game based notions of security for DKGs, building upon existing notions in the literature. However, these prior security notions either were presented informally, omitted important requirements, or assumed certain algebraic structure of the underlying scheme. Our security notions make no such assumption of underlying algebraic structure, and explicitly consider details such as participant consistency, communication patterns, and key validity. Further, our security notions imply simulatability with respect to a target key generation scheme without rewinding. Hence, any construction that is proven secure using our security notions additionally imply UC security. We then present STORM, a concrete instantiation of our generic construction that is secure in the discrete logarithm setting in the random oracle model. STORM is more efficient than related DKG schemes in the literature. Because of its simple design and composability, it is a practical choice for real world settings and standardization efforts.

Available format(s)
Public-key cryptography
Publication info
threshold cryptographykey generationformal methods
Contact author(s)
ckomlo @ uwaterloo ca
iang @ uwaterloo ca
dstebila @ uwaterloo ca
2023-02-27: revised
2023-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chelsea Komlo and Ian Goldberg and Douglas Stebila},
      title = {A Formal Treatment of Distributed Key Generation, and New Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/292},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.