Paper 2025/084

Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity

Yijia Chang, Hong Kong University of Science and Technology (Guangzhou)
Songze Li, Southeast University
Abstract

Threshold fully homomorphic encryption (ThFHE) enables multiple parties to compute functions over their sensitive data without leaking data privacy. Most of existing ThFHE schemes are restricted to full threshold and require the participation of all parties to output computing results. Compared with these full-threshold schemes, arbitrary threshold (ATh)-FHE schemes are robust to non-participants and can be a promising solution to many real-world applications. However, existing AThFHE schemes are either inefficient to be applied with a large number of parties $N$ and a large data size $K$, or insufficient to tolerate all types of non-participants. In this paper, we propose an AThFHE scheme to handle all types of non-participants with lower complexity over existing schemes. At the core of our scheme is the reduction from AThFHE construction to the design of a new primitive called approximate secret sharing (ApproxSS). Particularly, we formulate ApproxSS and prove the correctness and security of AThFHE on top of arbitrary-threshold (ATh)-ApproxSS's properties. Such a reduction reveals that existing AThFHE schemes implicitly design ATh-ApproxSS following a similar idea called ``noisy share''. Nonetheless, their ATh-ApproxSS design has high complexity and become the performance bottleneck. By developing ATASSES, an ATh-ApproxSS scheme based on a novel ``encrypted share'' idea, we reduce the computation (resp. communication) complexity from $\mathcal{O}(N^2K)$ to $\mathcal{O}(N^2+K)$ (resp. from $\mathcal{O}(NK)$ to $\mathcal{O}(N+K)$). We not only theoretically prove the (approximate) correctness and security of ATASSES, but also empirically evaluate its efficiency against existing baselines. Particularly, when applying to a system with one thousand parties, ATASSES achieves a speedup of $3.83\times$ -- $15.4\times$ over baselines.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2025
Keywords
Threshold Fully Homomorphic EncryptionApproximate Secret SharingSecure Multi-Party Computation
Contact author(s)
ychang847 @ connect hkust-gz edu cn
songzeli8824 @ outlook com
History
2025-01-21: approved
2025-01-20: received
See all versions
Short URL
https://ia.cr/2025/084
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2025/084,
      author = {Yijia Chang and Songze Li},
      title = {Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/084},
      year = {2025},
      url = {https://eprint.iacr.org/2025/084}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.