Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling

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.

Download
OA 2023_USENIX_Das.pdf 704.33 KB [Published Version]
Download (ext.)
OA https://eprint.iacr.org/2022/1389 [Published Version]
Conference Paper | Published | English

Scopus indexed
Author
Das, Sourav; Xiang, Zhuolun; Kokoris Kogias, LefterisISTA; Ren, Ling

Corresponding author has ISTA affiliation

Department
Abstract
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 core 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.
Publishing Year
Date Published
2023-08-15
Proceedings Title
32nd USENIX Security Symposium
Publisher
Usenix
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.
Volume
8
Page
5359-5376
Conference
USENIX Security Symposium
Conference Location
Anaheim, CA, United States
Conference Date
2023-08-09 – 2023-08-11
IST-REx-ID

Cite this

Das S, Xiang Z, Kokoris Kogias E, Ren L. Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling. In: 32nd USENIX Security Symposium. Vol 8. Usenix; 2023:5359-5376.
Das, S., Xiang, Z., Kokoris Kogias, E., & Ren, L. (2023). Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling. In 32nd USENIX Security Symposium (Vol. 8, pp. 5359–5376). Anaheim, CA, United States: Usenix.
Das, Sourav, Zhuolun Xiang, Eleftherios Kokoris Kogias, and Ling Ren. “Practical Asynchronous High-Threshold Distributed Key Generation and Distributed Polynomial Sampling.” In 32nd USENIX Security Symposium, 8:5359–76. Usenix, 2023.
S. Das, Z. Xiang, E. Kokoris Kogias, and L. Ren, “Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling,” in 32nd USENIX Security Symposium, Anaheim, CA, United States, 2023, vol. 8, pp. 5359–5376.
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.
Das, Sourav, et al. “Practical Asynchronous High-Threshold Distributed Key Generation and Distributed Polynomial Sampling.” 32nd USENIX Security Symposium, vol. 8, Usenix, 2023, pp. 5359–76.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2023-11-28
MD5 Checksum
1a730765930138e23c6efd2575872641


Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search