Paper 2025/2057

Distributed Key Generation for Efficient Threshold-CKKS

Seonhong Min, Seoul National University
Guillaume Hanrot, CryptoLab Inc.
Jai Hyun Park, CryptoLab Inc.
Alain Passelègue, CryptoLab Inc.
Damien Stehlé, CryptoLab Inc.
Abstract

Threshold fully homomorphic encryption provides efficient multi-party computation with low round-complexity. Among fully homomorphic encryption schemes, CKKS (Cheon-Kim-Kim-Song) enables high-throughput computations on both approximate and exact data. As most interesting applications involve deep computations, they require bootstrapping, the most efficient variants of which rely on sparse ternary secret keys. Unfortunately, so far, key generation protocols for threshold-CKKS either assume a trusted dealer, or lead to dense and non-ternary secret keys that severely damage computational throughput. In the latter case, the impact is so large that one often considers off-loading bootstrapping to an interactive protocol [Mouchet et al., PETS'21]. We introduce a novel Distributed Key Generation (DKG) protocol for threshold-CKKS. At a high level, it consists in running the existing distributed key generation algorithm from Mouchet et al. resulting in large secret keys, and using it to homomorphically evaluate the sparse-secret key generation algorithm. At the end, the parties obtain additive shares of a sparse secret key. The main technical challenge is to obtain an algorithm for sampling sparse ternary vectors of prescribed Hamming weight that can be CKKS-evaluated in an efficient manner. In the process, we design a new sampler of one-hot vectors that outperforms the one from~[Boneh et al., AFT'20]. We also design a rejection-sampling algorithm to map several one-hot vectors into a vector of prescribed Hamming weight. The whole process can be performed with only two CKKS bootstraps, even for a significant number of users. We present several variants of the DKG protocol, with~2 to~4 communication rounds, as well as an extension to key generation delegation. We implemented the 4-round protocol; its computational components run in~under 2s on GPU (RTX4090) for up to 1024 parties.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACM CCS 2026
DOI
10.1145/3830454.3846715
Keywords
Threshold Fully Homomorphic EncryptionBootstrappingCKKS
Contact author(s)
minsh @ snu ac kr
guillaume hanrot @ cryptolab co kr
jaihyunp @ gmail com
alain passelegue @ cryptolab co kr
damien stehle @ gmail com
History
2026-11-17: last of 2 revisions
2025-11-07: received
See all versions
Short URL
https://ia.cr/2025/2057
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2025/2057,
      author = {Seonhong Min and Guillaume Hanrot and Jai Hyun Park and Alain Passelègue and Damien Stehlé},
      title = {Distributed Key Generation for Efficient Threshold-{CKKS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2057},
      year = {2025},
      doi = {10.1145/3830454.3846715},
      url = {https://eprint.iacr.org/2025/2057}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.