Abraham, I;
Jovanovic, P;
Maller, M;
Meiklejohn, S;
Stern, G;
Tomescu, A;
(2021)
Reaching Consensus for Asynchronous Distributed Key Generation.
In: Miller, A and Censor-Hillel, K and Korhonen, JH, (eds.)
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing.
(pp. pp. 363-373).
ACM
Preview |
Text
2102.09041v3.pdf - Accepted Version Download (555kB) | Preview |
Abstract
We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand f < n over 3 faulty parties), has a constant expected number of rounds, has Õ (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 validproposal 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: | Proceedings paper |
|---|---|
| Title: | Reaching Consensus for Asynchronous Distributed Key Generation |
| Event: | PODC'21: 2021 ACM Symposium on Principles of Distributed Computing |
| ISBN-13: | 978-1-4503-8548-0 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3465084.3467914 |
| Publisher version: | https://doi.org/10.1145/3465084.3467914 |
| 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. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS 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 |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10133255 |
Archive Staff Only
 |
View Item |
