UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Reaching consensus for asynchronous distributed key generation

Abraham, Ittai; Jovanovic, Philipp; Maller, Mary; Meiklejohn, Sarah; Stern, Gilad; Tomescu, Alin; (2023) Reaching consensus for asynchronous distributed key generation. Distributed Computing , 36 pp. 219-252. 10.1007/s00446-022-00436-8. Green open access

[thumbnail of Reaching_Consensus_for_Distributed_Key_Generation___Journal.pdf]
Reaching_Consensus_for_Distributed_Key_Generation___Journal.pdf - Submitted Version

Download (680kB) | Preview


We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand f<n3 faulty parties), has a constant expected number of rounds, has O(λn3) expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required Ω(n) expected number of rounds, and Ω(n4) expected communication. Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a nonfaulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.

Type: Article
Title: Reaching consensus for asynchronous distributed key generation
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s00446-022-00436-8
Publisher version: https://doi.org/10.1007/s00446-022-00436-8
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Distributed computing, Distributed key generation, Consensus, Byzantine adversary, Asynchrony
UCL classification: UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
UCL > Provost and Vice Provost Offices > UCL BEAMS
URI: https://discovery.ucl.ac.uk/id/eprint/10157574
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item