Welcome to the resource topic for 2021/1635
Title:
Synchronous Distributed Key Generation without Broadcasts
Authors: Nibesh Shrestha, Adithya Bhat, Aniket Kate, 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.
ePrint: https://eprint.iacr.org/2021/1635
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .