Score:0

Distributed key generation when all parties need to participate

cn flag

Suppose $n$ parties where $t$ are honest want to perform a distributed key generation protocol. There are many existing schemes. In the simpler setting where all $n$ parties must be online, otherwise the protocol aborts, does the following simplified scheme suffice?

  1. Each party $i$ samples $x_i \gets \mathbb{Z}_p$
  2. Compute $X_i \gets g^{x_i}$
  3. Create a zero-knowledge proof for discrete logarithm relation on $(x_i, X_i)$, call this proof $\sigma_i$
  4. Broadcast $(X_i, \sigma_i)$
  5. Upon receiving $n$ messages, verify the proof and compute the public key as $pk \gets \sum_i X_i$

Encryption is performed using ElGamal. Then, to do distributed decryption for a ciphertext $c$, parties just broadcast the result of ElGamal decryption and then aggregate the result to obtain the final plaintext. Clearly the adversary could stop the honest parties from learning the plaintext by not sending his part of the decryption. But other than that, would this be a secure DKG protocol if I don't want to support an arbitrary threshold?

Aman Grewal avatar
gb flag
My initial thought is that you'd want to broadcast $\sigma_i$ before revealing $X_i$ otherwise the last person can perform Wagner's generalized birthday attack. If I can formalize and verify this, I'll post it as an answer.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.