FHE for SIMD Arithmetic Logic Units with Amortized O(1) Bootstrapping per Ciphertext¶
Authors: Gao, Zheng
Year: 2026
Venue: CRYPTO 2026
type: scheme collection: schemes status: auto
Links: ePrint 2026/233
Visual lesson: SIMD ALU FHE with O(1) bootstrapping · Scheme table row: SIMD ALU FHE with O(1) bootstrapping
Summary¶
Auto-extracted summary (unreviewed)
Gao and Zheng present a CKKS-style FHE scheme that supports both arithmetic and boolean operations on SIMD slots of machine words (8- to 256-bit). A new triangle encoding lets the inherently iterative arithmetic-to-boolean conversion process many ciphertexts per iteration, giving amortized O(1) bootstrapping per ciphertext, while multiplication refresh needs only two CKKS bootstrappings regardless of bit-width; Discrete CKKS serves as the boolean mode. The OpenFHE prototype gives 1.7-2x higher multiplication throughput than CPL, an estimated 15x/491x over REFHE for multiplication/bitwise ops, and 863x higher 64-bit multiplication throughput than TFHE-rs.
Abstract¶
The evaluation of both arithmetic and logic operations on machine words (e.g., 64-bit registers) in homomorphic settings is an attractive problem due to its close alignment with real-world programming models. Existing FHE schemes require iterative bootstrapping operations with the iteration number scaling with the machine word bitwidth n. Prior approaches incur either quadratic cost for multiplication (DM/CGGI), linear cost for logic operations (REFHE [Eurocrypt’26] and Kim [TCHES’26]), or logarithmic cost for multiplication (CPL [Eurocrypt’26]). We mitigate this inherent barrier by amortizing O(n) iterations across O(n) ciphertexts for scenarios with sufficient machine words. We introduce a triangle encoding such that in its conversion to boolean mode, each iteration on a combined ciphertext processes multiple ciphertexts, resulting in an amortized constant cost per ciphertext. Additionally, the triangle encoding supports several multiplication operations before needing a refreshing that requires only two CKKS bootstrapping operations, regardless of the bit-width n. We reuse discrete CKKS as our boolean mode, which supports lightweight conversion to the triangle encoding. We also introduce a method to induce SIMD structure for the triangle encoding from the RLWE ring. Even when we bootstrap after each multiplication, we show a 1.7× to 2× higher throughput compared with the state-of-the-art CPL scheme. We further estimate 15× and 491× higher throughput for multiplication and bitwise operations, respectively, compared with the REFHE scheme. We make our OpenFHE-based prototype open source for ease of reference.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | triangle encoding giving amortized O(1) bootstrapping per ciphertext for arithmetic-to-boolean conversion | llm | 0.90 |
| contribution | multiplication refresh using only two CKKS bootstrappings independent of bit-width | llm | 0.90 |
| contribution | Discrete CKKS reused as boolean mode with lightweight conversion | llm | 0.90 |
| contribution | method to induce SIMD structure for the triangle encoding from the RLWE ring | llm | 0.90 |
| contribution | open-source OpenFHE-based prototype | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| schemes | Discrete CKKS | llm | 0.90 |
| libraries | OpenFHE | llm | 0.90 |
| libraries | Intel HEXL | llm | 0.90 |
| libraries | TFHE-rs | llm | 0.90 |
| tasks | homomorphic integer arithmetic and bitwise operations on machine words | llm | 0.90 |
| tasks | bootstrapping | llm | 0.90 |
| hardware | AMD Ryzen AI MAX+ 395 CPU, 128 GB RAM, single thread | llm | 0.90 |
| security level | 128-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/tsinghua-ideal/fhe-simd-alu (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/intel/hexl (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/tsinghua-ideal/fhe-simd-alu | llm | 0.90 |
| limitations | worse performance than CPL for conversion to boolean mode in the single-ciphertext setting | llm | 0.90 |
| limitations | amortization requires a sufficient number of machine words (batched setting) | llm | 0.90 |
| limitations | arbitrary plaintext modulus not explored | llm | 0.90 |
| limitations | open problem: O(1)-bootstrapping arithmetic-to-boolean conversion without amortization | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | multiplication throughput vs CPL: 1.7x to 2x higher (bit-width 64 to 256, single thread, L=20) | llm | 0.90 |
| key result | batched arithmetic-to-boolean conversion vs CPL: 4.4x to 5.2x better (batched setting) | llm | 0.90 |
| key result | estimated throughput vs REFHE: 15x (multiplication), 491x (bitwise) (64-bit) | llm | 0.90 |
| key result | throughput vs TFHE-rs: 863x (64-bit mult), 2485x (256-bit mult, 9x lower latency), 27x (bitwise) (single thread with AVX512) | llm | 0.90 |
| key result | bootstrapping time (A2A I): 6.4 s total, 6.3 ms amortized per ciphertext (64-bit, 1024 slots) | llm | 0.90 |
| key result | arithmetic-to-boolean conversion: 80.5 s / 79 ms amortized (single); 128 s / 7.8 ms amortized (batched) (64-bit) | llm | 0.90 |
Scheme card: SIMD ALU FHE with O(1) bootstrapping¶
| Group | 3. Bit-wise / lookup-table FHE (GSW, FHEW, TFHE family) |
| Kind | Scheme |
| Hardness assumption | (R)LWE |
| Plaintext type | Machine words (e.g. 64-bit) with SIMD |
| SIMD packing | Yes |
| Bootstrapping | Yes, amortized O(1) per ciphertext |
| Post-quantum | Yes |
| Status | Active SOTA (emerging) |
| Fit for LLM inference | Brings SIMD to word-level arithmetic and logic, narrowing the TFHE vs CKKS gap. |
| Follow-ups | High-precision homomorphic ALU over arbitrary moduli (2026/1869). |
| Follow-up papers in the archive | High-Precision Homomorphic ALU over Arbitrary Moduli with O (1) Bootstrapping |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 153 [p.1], TFHE 16 [p.1], BFV 6 [p.2], BGV 4 [p.2], LTV 4 [p.14], FHEW 3 [p.33], RSA 2 [p.32], Scheme switching 2 [p.2]
- library: TFHE-rs 8 [p.4], OpenFHE 4 [p.1], Zama 2 [p.30], HElib 1 [p.33], Orion 1 [p.33]
- hardware: GPU 2 [p.2], AVX-512 1 [p.27]
- technique: Bootstrapping 106 [p.1], SIMD packing 50 [p.1], Rotations 31 [p.4], Lookup table 27 [p.2], Rescaling 20 [p.12], Polynomial approximation 6 [p.13], Key switching 5 [p.26], RNS 5 [p.2], Compiler 3 [p.9], Matrix multiplication 2 [p.35]
- assumption: RLWE 92 [p.1], LWE 11 [p.1], IND-CPA-D 5 [p.23], Lattice-based 3 [p.35], 128-bit security 2 [p.5]
- task: Language modeling / generation 13 [p.12]
- topic: Homomorphic encryption 65 [p.1], Open source 5 [p.4]
Related papers¶
- High-Precision Homomorphic ALU over Arbitrary Moduli with O (1) Bootstrapping follow up of this paper — 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-0_fhe-for-simd-arithmetic-logic-units-with-amortized-o-1-boots.pdf |
schemes | 48 | 918.1 KB | db361d68d8b4 |
Database key: fhe-for-simd-arithmetic-logic-units-with-amortized-o-1-bootstrapping · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fhe-for-simd-arithmetic-logic-units-with-amortized-o-1-bootstrapping COLUMN VALUE