Skip to content

Ajax: Fast Threshold Fully Homomorphic Encryption without Noise Flooding

Year: 2025

type: technique collection: schemes status: auto

Links: ePrint 2025/1834

Summary

Auto-extracted summary (unreviewed)

Ajax is a threshold FHE scheme for FHEW/TFHE-like cryptosystems that replaces noise flooding in threshold decryption with a 'mask-then-open' technique built on random double sharings over different rings, keeping the small parameters of FHEW-like schemes, and gives a threshold key-generation protocol whose noise growth drops from n times to max(0.038n, 2) times in the honest-majority setting. Implemented with Primus-FHE and EMP-toolkit on AWS instances, it generates keys in 17.6 s and decrypts a ciphertext in 0.9 ms for 3 parties (91.9 s and 4.4 ms for 21 parties) on a 1 Gbps / 1 ms network, improving end-to-end threshold decryption over the prior implementation by 5.7x to 283.6x.

Abstract

Threshold fully homomorphic encryption (ThFHE) enables multiple parties to perform arbitrary computation over encrypted data, while the secret key is distributed across the parties. The main task of designing ThFHE is to construct threshold key-generation and decryption protocols for FHE schemes. Among existing FHE schemes, FHEW-like cryptosystems enjoy the advantage of fast bootstrapping and small parameters. However, known ThFHE solutions use the “noise-flooding” technique to realize threshold decryption, which requires either large parameters or switching to a scheme with large parameters via bootstrapping, leading to a slow decryption process. Besides, for key generation, existing ThFHE schemes either assume a generic MPC or a trusted setup, or incur noise growth that is linear in the number n of parties. In this paper, we propose a fast ThFHE scheme Ajax, by designing threshold key-generation and decryption protocols for FHEW-like cryptosystems. In particular, for threshold decryption, we eliminate the need for noise flooding, and instead present a new technique called “mask-then-open” based on random double sharings over different rings, while keeping the advantage of small parameters. For threshold key generation, we show a simple approach to reduce the noise growth from n times to max(0.038n, 2) times in the honest-majority setting, where at most t = ⌊(n −1)/2⌋parties are corrupted. Our end-toend implementation reports the running time 17.6 s and 0.9 ms (resp., 91.9 s and 4.4 ms) of generating a set of keys and decrypting a single ciphertext respectively, for n = 3 (resp., n = 21) parties under the network of 1 Gbps bandwidth and 1 ms ping time. Compared to the state-of-the-art implementation, our protocol improves the end-to-end performance of the threshold decryption protocol by a factor of at least 5.7× ∼283.6× across different network latencies from t = 1 to t = 13. Our approaches can also be applied in other types of FHE schemes like BGV, BFV, and CKKS.
Source: pdf

Extracted details

Field Value Source Confidence
contribution threshold FHE scheme Ajax for FHEW-like cryptosystems llm 0.90
contribution mask-then-open threshold decryption without noise flooding, based on random double sharings llm 0.90
contribution threshold key generation with noise growth reduced from n to max(0.038n, 2) in the honest-majority setting llm 0.90
contribution end-to-end implementation and evaluation under LAN/WAN conditions llm 0.90
contribution techniques applicable to BGV, BFV and CKKS llm 0.90
schemes FHEW llm 0.90
schemes TFHE llm 0.90
schemes threshold FHE llm 0.90
schemes secret sharing llm 0.90
libraries Primus-FHE llm 0.90
libraries EMP-toolkit llm 0.90
tasks threshold key generation llm 0.90
tasks threshold decryption llm 0.90
tasks multi-party computation over encrypted data llm 0.90
hardware AWS c6i.2xlarge instances (8 vCPUs, 16 GiB RAM) per party llm 0.90
security level 128-bit computational (131-bit per LWE estimator), 30-bit statistical llm 0.90
threat model semi-honest; honest-majority t = floor((n-1)/2) for key generation, up to t = n-1 for decryption llm 0.90
interaction interactive (HE+MPC) llm 0.90
code url https://github.com/primus-labs/Ajax/3By (URL found in the full text) regex 0.50
code url https://github.com/primus-labs/primus-fhe (URL found in the full text) regex 0.50
code url https://github.com/zama-ai/tfhe-rs (URL found in the full text) regex 0.50
code url https://github.com/primus-labs/Ajax/ llm 0.90
limitations performance is limited when scaling up the number of parties despite multi-threading llm 0.90
limitations decryption protocol is semi-honest only, so the comparison with the malicious-secure prior work is not security-equivalent llm 0.90
limitations bootstrapping key generation accounts for about 99% of key-generation communication llm 0.90
llm relevance low llm 0.90
key result threshold key generation time: 17.6 s (n = 3 parties, 1 Gbps, 1 ms RTT) llm 0.90
key result threshold decryption time: 0.9 ms per ciphertext (n = 3 parties, 1 Gbps, 1 ms RTT) llm 0.90
key result threshold key generation time: 91.9 s (n = 21 parties, 1 Gbps, 1 ms RTT) llm 0.90
key result threshold decryption time: 4.4 ms per ciphertext (n = 21 parties, 1 Gbps, 1 ms RTT) llm 0.90
key result threshold decryption speed-up: 5.7x to 283.6x (vs prior implementation [DDEK+23], t = 1 to 13, various network latencies) llm 0.90
key result end-to-end decryption time: 0.855 ms total (vs 242.44 ms) (t = 1, LAN, vs [DDEK+23]) llm 0.90

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Secret sharing 72 [p.2], Threshold HE 37 [p.1], MPC 35 [p.1], FHEW 24 [p.1], TFHE 17 [p.1], BFV 6 [p.1], BGV 6 [p.1], CKKS 5 [p.1], Zero-knowledge proofs 4 [p.27], Hybrid HE / transciphering 3 [p.2], RSA 2 [p.24], Multiparty HE 2 [p.26], Oblivious transfer 2 [p.9], Leveled / somewhat HE 2 [p.9]
  • library: OpenFHE 2 [p.21], TFHE-rs 2 [p.28], Zama 1 [p.28], MP-SPDZ 1 [p.27]
  • technique: Bootstrapping 45 [p.1], Semi-honest model 35 [p.3], Modulus switching 20 [p.5], Key switching 15 [p.13], Noise flooding 15 [p.1], Malicious model 15 [p.5], Rotations 4 [p.17], Non-interactive 3 [p.21]
  • assumption: LWE 75 [p.2], RLWE 39 [p.2], Lattice-based 7 [p.11], 128-bit security 2 [p.12]
  • topic: Homomorphic encryption 66 [p.1], Open source 5 [p.3]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s36-3_eprint-2025-1834.pdf schemes 51 683.0 KB 945802ad7400

Database key: ajax-fast-threshold-fully-homomorphic-encryption-without-noise-flooding · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set ajax-fast-threshold-fully-homomorphic-encryption-without-noise-flooding COLUMN VALUE