Paper 2021/1635

Synchronous Distributed Key Generation without Broadcasts

Nibesh Shrestha, Rochester Institute of Technology
Adithya Bhat, Purdue University West Lafayette
Aniket Kate, Purdue University West Lafayette
Kartik Nayak, Duke University

Distributed key generation (DKG) is an important building block in designing many efficient distributed protocols. In this work, we initiate the study of communication complexity and latency of distributed key generation protocols under a synchronous network in a point-to-point network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with $O(\kappa n^3)$ communication complexity ($\kappa$ denotes a security parameter) that tolerates $t < n/2$ Byzantine faults among $n$ parties. We show two variants of the protocol: a deterministic protocol with $O(t\Delta)$ latency and randomized protocol with $O(\Delta)$ latency in expectation where $\Delta$ denotes the bounded synchronous delay. In the process of achieving our results, we design (1) a gradecast protocol with optimal communication complexity of $O(\kappa n^2)$ for linear-sized inputs and latency of $O(\Delta)$, (2) a primitive called ``recoverable set of shares'' for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with $O(\kappa n^3)$ communication and $O(\Delta)$ latency, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with $O(\kappa n^3)$ communication complexity for linear-sized inputs and $O(\Delta)$ latency in expectation. Each of these primitives may be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Distributed Key GenerationSynchronyThreshold CryptographyBlockchains
Contact author(s)
nxs4564 @ rit edu
2023-10-16: last of 3 revisions
2021-12-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nibesh Shrestha and Adithya Bhat and Aniket Kate and Kartik Nayak},
      title = {Synchronous Distributed Key Generation without Broadcasts},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1635},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.