Synchronous Distributed Key Generation without Broadcasts

Synchronous Distributed Key Generation without Broadcasts

2024-06-03 | Nibesh Shrestha, Adithya Bhat, Aniket Kate and Kartik Nayak
This paper introduces a novel approach to synchronous distributed key generation (DKG) without the need for broadcasts, focusing on discrete log-based cryptosystems. The key contributions include: 1. **Optimal Weak Graecast Protocol**: A communication-efficient weak graecast protocol with $O(n\ell + \kappa n^2)$ communication complexity, where $\ell$ is the input size and $\kappa$ is the security parameter. This protocol tolerates up to $t < n/2$ Byzantine faults. 2. **Recoverable-Set-of-Shares Protocol**: A protocol that ensures the recovery of shared secrets with $O(\kappa n^3)$ communication and constant rounds. Each party outputs a set of at least $n - t$ trusted parties, and verifiable proofs are provided to confirm the correctness of these sets. 3. **Oblivious Leader Election Protocol**: A communication-efficient oblivious leader election protocol with $O(\kappa n^3)$ communication and constant rounds. This protocol uses weaker VSS instances and a non-interactive threshold signature scheme. 4. **Multi-Valued Validated Byzantine Agreement Protocol**: A protocol that tolerates $t < n/2$ Byzantine faults with expected $O(n^2\ell + \kappa n^3)$ communication and expected 36 rounds. This protocol relies on the oblivious leader election protocol. The paper also presents a secure DKG protocol that reduces the number of broadcast rounds to two, improving upon previous protocols. The protocol uses an improved error-correcting code (iVSS) scheme, which requires only two broadcast rounds, reducing latency and communication overhead. The overall goal is to achieve efficient DKG protocols with low communication complexity, good latency, and optimal resilience to Byzantine faults in a synchronous network setting.This paper introduces a novel approach to synchronous distributed key generation (DKG) without the need for broadcasts, focusing on discrete log-based cryptosystems. The key contributions include: 1. **Optimal Weak Graecast Protocol**: A communication-efficient weak graecast protocol with $O(n\ell + \kappa n^2)$ communication complexity, where $\ell$ is the input size and $\kappa$ is the security parameter. This protocol tolerates up to $t < n/2$ Byzantine faults. 2. **Recoverable-Set-of-Shares Protocol**: A protocol that ensures the recovery of shared secrets with $O(\kappa n^3)$ communication and constant rounds. Each party outputs a set of at least $n - t$ trusted parties, and verifiable proofs are provided to confirm the correctness of these sets. 3. **Oblivious Leader Election Protocol**: A communication-efficient oblivious leader election protocol with $O(\kappa n^3)$ communication and constant rounds. This protocol uses weaker VSS instances and a non-interactive threshold signature scheme. 4. **Multi-Valued Validated Byzantine Agreement Protocol**: A protocol that tolerates $t < n/2$ Byzantine faults with expected $O(n^2\ell + \kappa n^3)$ communication and expected 36 rounds. This protocol relies on the oblivious leader election protocol. The paper also presents a secure DKG protocol that reduces the number of broadcast rounds to two, improving upon previous protocols. The protocol uses an improved error-correcting code (iVSS) scheme, which requires only two broadcast rounds, reducing latency and communication overhead. The overall goal is to achieve efficient DKG protocols with low communication complexity, good latency, and optimal resilience to Byzantine faults in a synchronous network setting.
Reach us at info@study.space
[slides and audio] Synchronous Distributed Key Generation without Broadcasts