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.

Preview

Text Reaching_Consensus_for_Distributed_Key_Generation___Journal.pdf - Submitted Version Download (680kB) | Preview

Abstract

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.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as XMLJSONCSV

Archive Staff Only

View Item