Synchronous Distributed Key Generation without Broadcasts
Authors
Abstract
Distributed key generation (DKG) is a key building block in developing many efficient threshold cryptosystems. This work initiates the study of communication complexity and round complexity of DKG protocols over a point-to-point (bounded) synchronous 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 any $t < n/2$ Byzantine faults among $n$ parties. We present two variants of the protocol: (i) a protocol with worst-case $O(\kappa n^3)$ communication and $O(t)$ rounds, and (ii) a protocol with expected $O(\kappa n^3)$ communication and expected constant rounds. In the process of achieving our results, we design (1) a novel weak gradecast protocol with a communication complexity of $O(\kappa n^2)$ for linear-sized inputs and constant rounds, (2) a protocol called “recoverable-set-of-shares” for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with $O(\kappa n^3)$ communication and constant rounds, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with $O(\kappa n^3)$ communication complexity for linear-sized inputs and expected constant rounds. Each of these primitives is of independent interest.
References
How to cite
Nibesh Shrestha, Adithya Bhat, Aniket Kate, and Kartik Nayak, "Synchronous Distributed Key Generation without Broadcasts," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ayfhsgvtw.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.