Skip to content

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]

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