Paper 2026/2909
Kairos: Efficient High-Threshold Asynchronous Distributed Key Generation from Lightweight Cryptography
Abstract
Asynchronous distributed key generation (ADKG) bootstraps threshold cryptosystems by robustly generating threshold public and private key pairs. This primitive is a fundamental building block for distributed algorithms such as random beacons, threshold signatures, threshold decryption, and general distributed key management services (DKM). While significant progress has been made, ADKG constructions still exhibit computation inefficiency, especially in high-threshold reconstruction, due to their tight coupling to homomorphic-commitment-based verifiable secret sharing. We fill in this research gap by presenting Kairos, a concretely and asymptotically efficient ADKG protocol. For efficiency, Kairos avoids homomorphic commitments by deriving dLog-based public-private key sharings from the lightweight hash-based asynchronous complete secret sharing (ACSS), with an asymptotically optimal, quadratic per-key communication. For secrecy, Kairos tolerates up to $f$ malicious nodes among $n=3f+1$ parties, and produces unbiased public key shares with a high reconstruction threshold of $t\geq f$. The core techniques in Kairos are a non-interactive threshold lifting for private key shares, and a lightweight high-threshold verification script aggregator for public key shares under a lock-then-verify paradigm, which may be of independent interest and applied in asynchronous dynamic proactive secret sharing (ADPSS) or multi-party computation. Evaluations conducted on distributed AWS EC2 servers demonstrate that Kairos reduces 63.7-99.4\% runtime compared to the baselines DXKR23 (Usenix Security'23) and HARTS (ASIACRYPT'24) under $t=2f$, achieving a throughput of 3k keys/min at $n=16$. When applied in ADPSS, our solution reduces 91.0-98.7\% runtime compared to LongLive (Usenix Security'23) at $t=2f$, resharing 2.3k secrets/min across 16-node committees.
Note: This is the full version of the published paper and includes the complete security proofs.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. ACM CCS 2026
- DOI
- https://doi.org/10.1145/3830454.3832655
- Contact author(s)
- xxxshixiannva @ buaa edu cn
- History
- 2026-11-21: approved
- 2026-11-16: received
- See all versions
- Short URL
- https://ia.cr/2026/2909
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2026/2909,
author = {Xinxin Xing and Yizhong Liu and Zifan Li and Jianwei Liu and Yudi Yang and Yuan Lu and Song Bian and Zhenyu Guan and Tianwei Zhang},
title = {Kairos: Efficient High-Threshold Asynchronous Distributed Key Generation from Lightweight Cryptography},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2909},
year = {2026},
doi = {https://doi.org/10.1145/3830454.3832655},
url = {https://eprint.iacr.org/2026/2909}
}