---
_id: '10556'
abstract:
- lang: eng
  text: In this paper, we present the first Asynchronous Distributed Key Generation
    (ADKG) algorithm which is also the first distributed key generation algorithm
    that can generate cryptographic keys with a dual (f,2f+1)-threshold (where f is
    the number of faulty parties). As a result, using our ADKG we remove the trusted
    setup assumption that the most scalable consensus algorithms make. In order to
    create a DKG with a dual (f,2f+1)- threshold we first answer in the affirmative
    the open question posed by Cachin et al. [7] on how to create an Asynchronous
    Verifiable Secret Sharing (AVSS) protocol with a reconstruction threshold of f+1<k
    łe 2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses
    an asymmetric bivariate polynomial to encode the secret. This enables the reconstruction
    of the secret only if a set of k nodes contribute while allowing an honest node
    that did not participate in the sharing phase to recover his share with the help
    of f+1 honest parties. Once we have HAVSS we can use it to bootstrap scalable
    partially synchronous consensus protocols, but the question on how to get a DKG
    in asynchrony remains as we need a way to produce common randomness. The solution
    comes from a novel Eventually Perfect Common Coin (EPCC) abstraction that enables
    the generation of a common coin from n concurrent HAVSS invocations. EPCC's key
    property is that it is eventually reliable, as it might fail to agree at most
    f times (even if invoked a polynomial number of times). Using EPCC we implement
    an Eventually Efficient Asynchronous Binary Agreement (EEABA) which is optimal
    when the EPCC agrees and protects safety when EPCC fails. Finally, using EEABA
    we construct the first ADKG which has the same overhead and expected runtime as
    the best partially-synchronous DKG (O(n4) words, O(f) rounds). As a corollary
    of our ADKG, we can also create the first Validated Asynchronous Byzantine Agreement
    (VABA) that does not need a trusted dealer to setup threshold signatures of degree
    n-f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance,
    after an initial O(n4) words and O(f) time bootstrap via ADKG.
acknowledgement: We would like to thank Ittai Abraham for the discussions and guidance
  during the initial conception of the project, especially for HAVSS. Furthermore,
  we would like to thank the anonymous reviewers for pointing out the relevance of
  this work to MPC protocols.
article_processing_charge: No
author:
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Dahlia
  full_name: Malkhi, Dahlia
  last_name: Malkhi
- first_name: Alexander
  full_name: Spiegelman, Alexander
  last_name: Spiegelman
citation:
  ama: 'Kokoris Kogias E, Malkhi D, Spiegelman A. Asynchronous distributed key generation
    for computationally-secure randomness, consensus, and threshold signatures. In:
    <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications
    Security</i>. Association for Computing Machinery; 2020:1751–1767. doi:<a href="https://doi.org/10.1145/3372297.3423364">10.1145/3372297.3423364</a>'
  apa: 'Kokoris Kogias, E., Malkhi, D., &#38; Spiegelman, A. (2020). Asynchronous
    distributed key generation for computationally-secure randomness, consensus, and
    threshold signatures. In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer
    and Communications Security</i> (pp. 1751–1767). Virtual, United States: Association
    for Computing Machinery. <a href="https://doi.org/10.1145/3372297.3423364">https://doi.org/10.1145/3372297.3423364</a>'
  chicago: Kokoris Kogias, Eleftherios, Dahlia Malkhi, and Alexander Spiegelman. “Asynchronous
    Distributed Key Generation for Computationally-Secure Randomness, Consensus, and
    Threshold Signatures.” In <i>Proceedings of the 2020 ACM SIGSAC Conference on
    Computer and Communications Security</i>, 1751–1767. Association for Computing
    Machinery, 2020. <a href="https://doi.org/10.1145/3372297.3423364">https://doi.org/10.1145/3372297.3423364</a>.
  ieee: E. Kokoris Kogias, D. Malkhi, and A. Spiegelman, “Asynchronous distributed
    key generation for computationally-secure randomness, consensus, and threshold
    signatures,” in <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and
    Communications Security</i>, Virtual, United States, 2020, pp. 1751–1767.
  ista: 'Kokoris Kogias E, Malkhi D, Spiegelman A. 2020. Asynchronous distributed
    key generation for computationally-secure randomness, consensus, and threshold
    signatures. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications
    Security. CCS: Computer and Communications Security, 1751–1767.'
  mla: Kokoris Kogias, Eleftherios, et al. “Asynchronous Distributed Key Generation
    for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” <i>Proceedings
    of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>,
    Association for Computing Machinery, 2020, pp. 1751–1767, doi:<a href="https://doi.org/10.1145/3372297.3423364">10.1145/3372297.3423364</a>.
  short: E. Kokoris Kogias, D. Malkhi, A. Spiegelman, in:, Proceedings of the 2020
    ACM SIGSAC Conference on Computer and Communications Security, Association for
    Computing Machinery, 2020, pp. 1751–1767.
conference:
  end_date: 2020-11-13
  location: Virtual, United States
  name: 'CCS: Computer and Communications Security'
  start_date: 2020-11-09
date_created: 2021-12-16T13:23:27Z
date_published: 2020-10-30T00:00:00Z
date_updated: 2024-02-22T13:10:45Z
day: '30'
department:
- _id: ElKo
doi: 10.1145/3372297.3423364
external_id:
  isi:
  - '000768470400104'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2019/1015
month: '10'
oa: 1
oa_version: Preprint
page: 1751–1767
publication: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications
  Security
publication_identifier:
  isbn:
  - 978-1-4503-7089-9
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Asynchronous distributed key generation for computationally-secure randomness,
  consensus, and threshold signatures
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '10557'
abstract:
- lang: eng
  text: Data storage and retrieval systems, methods, and computer-readable media utilize
    a cryptographically verifiable data structure that facilitates verification of
    a transaction in a decentralized peer-to-peer environment using multi-hop backwards
    and forwards links. Backward links are cryptographic hashes of past records. Forward
    links are cryptographic signatures of future records that are added retroactively
    to records once the target block has been appended to the data structure.
applicant:
- Ecole Polytechnique Federale de Lausanne
application_date: 2017-06-09
article_processing_charge: No
author:
- first_name: Bryan
  full_name: Ford, Bryan
  last_name: Ford
- first_name: Linus
  full_name: Gasse, Linus
  last_name: Gasse
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Philipp
  full_name: Jovanovic, Philipp
  last_name: Jovanovic
citation:
  ama: Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. Cryptographically verifiable
    data structure having multi-hop forward and backwards links and associated systems
    and methods. 2020.
  apa: Ford, B., Gasse, L., Kokoris Kogias, E., &#38; Jovanovic, P. (2020). Cryptographically
    verifiable data structure having multi-hop forward and backwards links and associated
    systems and methods.
  chicago: Ford, Bryan, Linus Gasse, Eleftherios Kokoris Kogias, and Philipp Jovanovic.
    “Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards
    Links and Associated Systems and Methods,” 2020.
  ieee: B. Ford, L. Gasse, E. Kokoris Kogias, and P. Jovanovic, “Cryptographically
    verifiable data structure having multi-hop forward and backwards links and associated
    systems and methods.” 2020.
  ista: Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. 2020. Cryptographically verifiable
    data structure having multi-hop forward and backwards links and associated systems
    and methods.
  mla: Ford, Bryan, et al. <i>Cryptographically Verifiable Data Structure Having Multi-Hop
    Forward and Backwards Links and Associated Systems and Methods</i>. 2020.
  short: B. Ford, L. Gasse, E. Kokoris Kogias, P. Jovanovic, (2020).
date_created: 2021-12-16T13:28:59Z
date_published: 2020-03-03T00:00:00Z
date_updated: 2021-12-21T10:04:50Z
day: '03'
department:
- _id: ElKo
extern: '1'
ipc: ' H04L9/3247 ; G06Q20/29 ; G06Q20/382 ; H04L9/3236'
ipn: '10581613'
main_file_link:
- open_access: '1'
  url: https://patents.google.com/patent/US10581613B2/en
month: '03'
oa: 1
oa_version: Published Version
publication_date: 2020-03-03
related_material:
  link:
  - relation: earlier_version
    url: https://patents.google.com/patent/US20180359096A1/en
status: public
title: Cryptographically verifiable data structure having multi-hop forward and backwards
  links and associated systems and methods
type: patent
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2020'
...