CryptoDB
Adithya Bhat
Publications
Year
Venue
Title
2024
CIC
Synchronous Distributed Key Generation without Broadcasts
Abstract
<p> 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(κn3) communication complexity (κ 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(κn3) communication and O(t) rounds, and (ii) a protocol with expected O(κn3) 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(κn2) 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(κn3) communication and constant rounds, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with O(κn3) communication complexity for linear-sized inputs and expected constant rounds. Each of these primitives is of independent interest. </p>
Coauthors
- Adithya Bhat (1)
- Aniket Kate (1)
- Kartik Nayak (1)
- Nibesh Shrestha (1)