Introduction
We show that transcripts in a DKG protocol can be aggregated, which reduces communication and makes the protocol publicly-verifiable.
Abstract
In this paper, we introduce a distributed key generation
(DKG) protocol with aggregatable and publicly-verifiable transcripts.
Compared with prior publicly-verifiable approaches, our DKG reduces
the size of the final transcript and the time to verify it from O(n^2)
to O(n log n), where n denotes the number of parties. As compared
with prior non-publicly-verifiable approaches, our DKG leverages gossip
rather than all-to-all communication to reduce verification and communication complexity. We also revisit existing DKG security definitions,
which are quite strong, and propose new and natural relaxations. As a
result, we can prove the security of our aggregatable DKG as well as
that of several existing DKGs, including the popular Pedersen variant.
We show that, under these new definitions, these existing DKGs can be
used to yield secure threshold variants of popular cryptosystems such as
El-Gamal encryption and BLS signatures. We also prove that our DKG
can be securely combined with a new efficient verifiable unpredictable
function (VUF), whose security we prove in the random oracle model.
Finally, we experimentally evaluate our DKG and show that the per party overheads scale linearly and are practical. For 64 parties, it takes
71 ms to share and 359 ms to verify the overall transcript, while for 8192
parties, it takes 8 s and 42.2 s respectively.