Cryptology ePrint Archive: Report 2021/1635

Synchronous Distributed Key Generation without Broadcasts

Nibesh Shrestha and Adithya Bhat and Aniket Kate and Kartik Nayak

Abstract: 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.

Category / Keywords: cryptographic protocols / Distributed Key Generation; Synchrony; Threshold Cryptography; Blockchains

Date: received 14 Dec 2021, last revised 14 Dec 2021

Contact author: nxs4564 at rit edu, bhat24 at purdue edu, aniket at purdue edu, kartik at cs duke edu

Available format(s): PDF | BibTeX Citation

Version: 20211217:142344 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]