High-Precision Homomorphic ALU over Arbitrary Moduli with O (1) Bootstrapping¶
Year: 2026
type: technique collection: schemes status: auto
Links: ePrint 2026/1869
Summary¶
Auto-extracted summary (unreviewed)
This work builds a CKKS-based SIMD framework for homomorphic integer computation over arbitrary plaintext moduli that needs only O(1) bootstrapping calls for both arithmetic and non-arithmetic operations, generalizing the triangle encoding of Gao and Zheng. It finds well-conditioned defining polynomials via a CVP-based search (falling back to homomorphic Montgomery multiplication over radix-friendly rings) and introduces an arithmetic-to-digit conversion using O(1) functional bootstraps. Implemented in OpenFHE, modular multiplication for P-384/Curve25519 is 8.67-13.41x faster than CPL26 (up to 35.63x amortized), RSA-1024/2048 multiplication is 4.25x/7.58x faster, and arithmetic-to-Boolean conversion is 3.75-14.17x faster than GZ26.
Abstract¶
Homomorphic computation on large integers requires both arithmetic and non-arithmetic (e.g., Boolean) operations. The radix-based method by Cha et al. (EUROCRYPT’26) supports both operation types over arbitrary n-bit integers with a complexity of O(log n) and O(1) bootstrapping, respectively. Meanwhile, the triangle encoding method by Gao and Zheng (CRYPTO’26) has a complexity of O(1) bootstrapping in arithmetic mode, but is restricted to power-of-two integers. Its arithmeticto-Boolean (A2B) conversions also needs O(n) bootstrapping and is only O(1) in the amortized sense. This work improves both methods by supporting computation over arbitrary moduli with O(1) bootstrapping for both operation types, and is a generalization of Gao and Zheng’s approach. Our first contribution is a framework for efficient homomorphic arithmetic over arbitrary plaintext moduli. It supports flexible radix representations and uses a CVP-based method to find defining polynomials with wellconditioned canonical embeddings and small norm growth under ring operations. When the method fails to find suitable defining polynomials, we use homomorphic Montgomery multiplication over radix-friendly plaintext rings, where each Montgomery reduction requires only O(1) bootstrapping calls. Our second contribution is an efficient arithmetic-todigit (A2D) conversion using O(1) bootstrapping calls, independent of the radix used by the arithmetic representation. We implemented our method in OpenFHE. For P-384 and Curve25519, our arithmetic multiplication achieves 8.67 ∼10.26× and 12.57 ∼13.41× lower latency than CPL26’s LazyMult and ExactMult, respectively. The speedups increase to 17.47 ∼27.24× and 25.35 ∼35.63× in the amortized setting. For RSA-1024 and RSA-2048, our arbitrary-modulus multiplication achieves 4.25× and 7.58× lower latency and 16.74× and 29.85× lower amortized time than CPL26’s ExactMult, respectively. For 64-, 128-, and 256-bit messages, our A2B conversion is 3.75×, 6.40×, and 14.17× faster than GZ26, respectively.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | framework for efficient homomorphic arithmetic over arbitrary plaintext moduli with flexible radix representations | llm | 0.85 |
| contribution | CVP-based method for finding defining polynomials with well-conditioned canonical embeddings and small norm growth | llm | 0.85 |
| contribution | homomorphic Montgomery multiplication with O(1) bootstrapping per reduction for general moduli | llm | 0.85 |
| contribution | arithmetic-to-digit (A2D/A2B) conversion using O(1) functional bootstrapping calls | llm | 0.85 |
| contribution | OpenFHE implementation and benchmarks against CPL26 and GZ26 | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| schemes | functional bootstrapping | llm | 0.85 |
| libraries | OpenFHE | llm | 0.85 |
| tasks | high-precision homomorphic integer arithmetic (P-384, Curve25519, RSA-1024, RSA-2048 moduli) | llm | 0.85 |
| tasks | arithmetic-to-Boolean conversion | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/zama-ai/tfhe-rs (URL found in the full text) | regex | 0.50 |
| llm relevance | low | llm | 0.85 |
| key result | arithmetic multiplication latency speed-up: 8.67-10.26x vs CPL26 LazyMult; 12.57-13.41x vs CPL26 ExactMult (P-384 and Curve25519 moduli) | llm | 0.85 |
| key result | amortized arithmetic multiplication speed-up: 17.47-27.24x (LazyMult), 25.35-35.63x (ExactMult) (P-384 and Curve25519 moduli) | llm | 0.85 |
| key result | arbitrary-modulus multiplication speed-up: 4.25x (RSA-1024) and 7.58x (RSA-2048) latency; 16.74x and 29.85x amortized (vs CPL26 ExactMult) | llm | 0.85 |
| key result | A2B conversion speed-up: 3.75x, 6.40x, 14.17x (64-, 128-, 256-bit messages vs GZ26) | llm | 0.85 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 76 [p.2], RSA 9 [p.1], TFHE 7 [p.2], BFV 4 [p.2], FHEW 4 [p.2], BGV 3 [p.2]
- library: OpenFHE 4 [p.1], TFHE-rs 4 [p.26], Zama 1 [p.31]
- hardware: Intel Xeon 1 [p.26]
- technique: Bootstrapping 61 [p.1], SIMD packing 21 [p.2], Rotations 15 [p.8], Functional bootstrapping 9 [p.9], Rescaling 6 [p.8]
- assumption: Lattice-based 14 [p.5], RLWE 5 [p.7]
- topic: Homomorphic encryption 17 [p.1], Open source 2 [p.28]
Related papers¶
- this paper follow up of FHE for SIMD Arithmetic Logic Units with Amortized O(1) Bootstrapping per Ciphertext — follow-up listed for scheme "SIMD ALU FHE with O(1) bootstrapping"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s25-1_eprint-2026-1869.pdf |
schemes | 40 | 781.7 KB | 7e6bb063104e |
Database key: high-precision-homomorphic-alu-over-arbitrary-moduli-with-o-1 · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set high-precision-homomorphic-alu-over-arbitrary-moduli-with-o-1 COLUMN VALUE