---
_id: '14609'
abstract:
- lang: eng
  text: "Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems
    without a trusted party. DKG is an essential building block to many decentralized
    protocols such as randomness beacons, threshold signatures, Byzantine consensus,
    and multiparty computation. While significant progress has been made recently,
    existing asynchronous DKG constructions are inefficient when the reconstruction
    threshold is larger than one-third of the total nodes. In this paper, we present
    a simple and concretely efficient asynchronous DKG (ADKG) protocol among n = 3t
    + 1 nodes that can tolerate up to t malicious nodes and support any reconstruction
    threshold ℓ ≥ t. Our protocol has an expected O(κn3) communication cost, where
    κ is the security parameter, and only assumes the hardness of the Discrete Logarithm.
    The\r\ncore ingredient of our ADKG protocol is an asynchronous protocol to secret
    share a random polynomial of degree ℓ ≥ t, which has other applications, such
    as asynchronous proactive secret sharing and asynchronous multiparty computation.
    We implement our high-threshold ADKG protocol and evaluate it using a network
    of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold
    ADKG protocol reduces the running time by 90% and bandwidth usage by 80% over
    the state-of-the-art."
acknowledgement: The authors would like to thank Amit Agarwal, Andrew Miller, and
  Tom Yurek for the helpful discussions related to the paper. This work is funded
  in part by a VMware early career faculty grant, a Chainlink Labs Ph.D. fellowship,
  the National Science Foundation, and the Austrian Science Fund (FWF) F8512-N.
article_processing_charge: No
author:
- first_name: Sourav
  full_name: Das, Sourav
  last_name: Das
- first_name: Zhuolun
  full_name: Xiang, Zhuolun
  last_name: Xiang
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Ling
  full_name: Ren, Ling
  last_name: Ren
citation:
  ama: 'Das S, Xiang Z, Kokoris Kogias E, Ren L. Practical asynchronous high-threshold
    distributed key generation and distributed polynomial sampling. In: <i>32nd USENIX
    Security Symposium</i>. Vol 8. Usenix; 2023:5359-5376.'
  apa: 'Das, S., Xiang, Z., Kokoris Kogias, E., &#38; Ren, L. (2023). Practical asynchronous
    high-threshold distributed key generation and distributed polynomial sampling.
    In <i>32nd USENIX Security Symposium</i> (Vol. 8, pp. 5359–5376). Anaheim, CA,
    United States: Usenix.'
  chicago: Das, Sourav, Zhuolun Xiang, Eleftherios Kokoris Kogias, and Ling Ren. “Practical
    Asynchronous High-Threshold Distributed Key Generation and Distributed Polynomial
    Sampling.” In <i>32nd USENIX Security Symposium</i>, 8:5359–76. Usenix, 2023.
  ieee: S. Das, Z. Xiang, E. Kokoris Kogias, and L. Ren, “Practical asynchronous high-threshold
    distributed key generation and distributed polynomial sampling,” in <i>32nd USENIX
    Security Symposium</i>, Anaheim, CA, United States, 2023, vol. 8, pp. 5359–5376.
  ista: Das S, Xiang Z, Kokoris Kogias E, Ren L. 2023. Practical asynchronous high-threshold
    distributed key generation and distributed polynomial sampling. 32nd USENIX Security
    Symposium. USENIX Security Symposium vol. 8, 5359–5376.
  mla: Das, Sourav, et al. “Practical Asynchronous High-Threshold Distributed Key
    Generation and Distributed Polynomial Sampling.” <i>32nd USENIX Security Symposium</i>,
    vol. 8, Usenix, 2023, pp. 5359–76.
  short: S. Das, Z. Xiang, E. Kokoris Kogias, L. Ren, in:, 32nd USENIX Security Symposium,
    Usenix, 2023, pp. 5359–5376.
conference:
  end_date: 2023-08-11
  location: Anaheim, CA, United States
  name: USENIX Security Symposium
  start_date: 2023-08-09
date_created: 2023-11-26T23:00:55Z
date_published: 2023-08-15T00:00:00Z
date_updated: 2023-11-28T09:17:38Z
day: '15'
ddc:
- '000'
department:
- _id: ElKo
file:
- access_level: open_access
  checksum: 1a730765930138e23c6efd2575872641
  content_type: application/pdf
  creator: dernst
  date_created: 2023-11-28T09:14:34Z
  date_updated: 2023-11-28T09:14:34Z
  file_id: '14621'
  file_name: 2023_USENIX_Das.pdf
  file_size: 704331
  relation: main_file
  success: 1
file_date_updated: 2023-11-28T09:14:34Z
has_accepted_license: '1'
intvolume: '         8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2022/1389
month: '08'
oa: 1
oa_version: Published Version
page: 5359-5376
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
  grant_number: F8512
  name: Secure Network and Hardware for Efficient Blockchains
publication: 32nd USENIX Security Symposium
publication_identifier:
  isbn:
  - '9781713879497'
publication_status: published
publisher: Usenix
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical asynchronous high-threshold distributed key generation and distributed
  polynomial sampling
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8
year: '2023'
...