Paper 2026/2909

Kairos: Efficient High-Threshold Asynchronous Distributed Key Generation from Lightweight Cryptography

Xinxin Xing, Beihang University
Yizhong Liu, Beihang University
Zifan Li, Beihang University
Jianwei Liu, Beihang University
Yudi Yang, Beihang University
Yuan Lu, A*STAR IAIC
Song Bian, Beihang University
Zhenyu Guan, Beihang University
Tianwei Zhang, Nanyang Technological University
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
Creative Commons Attribution-NonCommercial
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.