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]
Related papers¶
- this paper follow up of Multiparty Homomorphic Encryption from Ring-Learning-with-Errors — follow-up listed for scheme "Multiparty HE (MHE) for BFV/CKKS"
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