I am excited to say that myself and my coauthors Benedikt Bünz and Kevin Choi have recently released a new paper: Golden, Lightweight Non-Interactive Distributed Key Generation.
This research began by a conversation with an engineer who had worked on FROST, and was disappointed with the complexity of managing multi-round distributed key generation (DKG). The challenge of moving from multi-round DKGs to non-interactive (one-round) DKGs is ensuring public verifiability in an efficient manner. In other words, after only one round of communication, participants in the DKG must both send and receive secret key material to all other participants to generate distributed (Shamir) shares and public keys, while also convincing all partcipants that the material they distributed is correct (without revealing that information in the clear). The general blueprint to do so is for each participant to act as a Shamir secret sharing dealer, and then use public-key encryption to encrypt shares to their intended participants, while generating a zero-knowledge proof that this encryption is correct.
Before our work, Groth's DKG was the best we know how to do for non-interactive (single-round) DKGs in the discrete logarithm setting, without introducing new assumptions (such as Paillier or class groups). Under the hood, Groth's DKG uses ElGamal encryption and zero-knowledge proofs, to distribute Shamir shares to participants in a private way while guaranteeing to all other participants that the shares are valid. However, to allow for efficient decryption, the bandwidth overhead of this approach is extensive.
With Golden, we take a different approach altogether. The main innovation of our work is showing how non-interactive DKG can be done without using public-key encryption schemes such as ElGamal, Pallier, or class groups.
I will refer to the paper for full technical details, but in short, we are able to achieve a a more lightweight approach to public verifiability, by employing a Non-Interactive Key Exchange (NIKE) scheme in a pairwise manner among all participants. The NIKE allows participants to derive pairwise one-time pads among themselves (without interacting). Participants then use these one-time pads to encrypt shares to their intended recipeints in a lightweight and verifiable manner. We then show how to define a zero-knowledge proof that the one-time pads are generated correctly, which ensures honest participants can be sure Golden completed successfully (again, without interaction).
I am very excited about this innovation within Golden, and I believe this core technique—deriving NIKE keys and proving correctness using a zero-knowledge proof—can be used elsewhere, outside of the context of DKGs. I am also sure that it is possible to optimize our results; we used Bulletproofs for the zero-knowledge proof system, and I'm sure it is possible to optimize the proof size and computation even more.
Overall, it was a pleasure to work with my co-authors Benedikt Bünz and Kevin Choi - we made a great team and I am very proud of this work with them. I am also very happy with the name Golden—it was suggested to me by a close friend with the tagline "silence is golden," which indeed is perfect for our intended goal of minimizing overhead of a non-interactive DKG. However, Golden is also one of the hit songs from KPop Demon Hunters, my (current) favorite movie. If you haven't watched it, I highly recommend it!
I can't wait to see how Golden can be useful in practice and bring a new perspective to achieving public verifiability for multi-party computation protocols!
