Skip to content

Efficient Bootstrapping in Fully Homomorphic Encryption for Matrix Arithmetic

Authors: Eric Crockett; Craig Gentry; Hyojun Kim; Yeongmin Lee; Yongwoo Lee
Year: 2026
Venue: IACR ePrint 2026/956

type: scheme collection: catalogue, schemes status: auto

Links: DOI · ePrint 2026/956 · Semantic Scholar

Summary

Auto-extracted summary (unreviewed)

The paper designs a bootstrapping procedure for the Gentry-Lee (GL) FHE scheme for matrix arithmetic. By expressing the coefficient-to-slot and slot-to-coefficient transforms as ciphertext-plaintext matrix multiplications native to GL, the number of key-switching operations per step drops to a small constant, and the scheme is generalized to non-power-of-two matrix dimensions via a generalized trace over commutative rings. In a proof-of-concept Lattigo-based implementation at 128-bit security, linear transformations take 20.1% of bootstrapping time (versus 54.9-71.7% in prior CKKS bootstrapping) and the amortized CtS is about 3x faster than Lattigo's optimized CKKS implementation.

Abstract

Recently, Gentry and Lee (GL) proposed a fully homomorphic encryption (FHE) scheme optimized for matrix arithmetic. In this paper, we propose an efficient bootstrapping technique for the GL scheme. Our core idea leverages the linearity of the slot–coefficient transformations, namely CtS and StC: we formulate these operations as ciphertext– plaintext matrix multiplications, which are natively supported by the GL scheme. As a result, the proposed method reduces the number of key-switching operations per step to a small constant. To enable this, we first generalize the GL scheme to matrices of non-power-of-two dimensions by introducing a generalized definition of the trace over commutative rings and proving that it commutes with decryption. Our bootstrapping adopts the CKKS paradigm: ModRaise, CtS, EvalMod, and StC. Typically, CtS/StC and EvalMod dominate runtime and depth, respectively; our optimization shifts the bottleneck to EvalMod for both. A proof-of-concept implementation shows that linear transformations account for 20.1% of the total bootstrapping time, compared to 54.9–71.7% in prior CKKS bootstrapping, and that, despite lacking low-level optimizations, our amortized CtS runtime is still about 3× faster than the well-optimized library (Lattigo).
Source: pdf

Extracted details

Field Value Source Confidence
contribution bootstrapping for the GL matrix-arithmetic FHE scheme following the CKKS paradigm (ModRaise, CtS, EvalMod, StC) llm 0.85
contribution CtS/StC formulated as ciphertext-plaintext matrix multiplications with O(1) key switchings llm 0.85
contribution generalization of the GL scheme to non-power-of-two dimensions via a generalized trace over commutative rings that commutes with decryption llm 0.85
contribution optimizations: reduced key switchings (four to three), sparse-secret encapsulation, lazy key-switching, ModRaise to QP llm 0.85
contribution proof-of-concept implementation and comparison with Lattigo llm 0.85
schemes Gentry-Lee matrix FHE llm 0.85
schemes CKKS llm 0.85
libraries Lattigo llm 0.85
tasks FHE bootstrapping llm 0.85
tasks encrypted matrix arithmetic llm 0.85
security level 128-bit llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/tuneinsight/lattigo (URL found in the full text) regex 0.50
limitations proof-of-concept implementation lacks low-level optimizations llm 0.85
limitations EvalMod becomes the bottleneck in both runtime and depth llm 0.85
llm relevance low llm 0.85
key result share of bootstrapping time in linear transformations: 20.1% (vs 54.9-71.7% in prior CKKS bootstrapping) llm 0.85
key result amortized CtS runtime vs Lattigo CKKS: ~3x faster (proof-of-concept without low-level optimizations; 2x64x64x256 coefficients, log2 Q = 748, ~64 batched CKKS ciphertexts with log2 N = 15) llm 0.85
key result key switchings in CtS: reduced from 4 to 3 (X-axis partitioning optimization) llm 0.85

System card: Efficient bootstrapping for GL matrix FHE

Group 4. Alternative FHE schemes
Family GL scheme bootstrapping
Arithmetic Approximate real matrices
Interaction Non-interactive
Model scale -
Status Active SOTA (emerging)
Relation to the SoK Bootstrapping for the matrix-native GL scheme.
Note Expresses CoeffToSlot and SlotToCoeff as native matrix products, so key switches per step are a small constant.
Systems page Efficient bootstrapping for GL matrix FHE

Keyword mentions

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

  • scheme: Matrix-native FHE 41 [p.1], CKKS 30 [p.1], BFV 7 [p.1], BGV 6 [p.1], FHEW 2 [p.32]
  • library: Lattigo 6 [p.1], HElib 1 [p.32]
  • technique: Matrix multiplication 68 [p.1], Bootstrapping 62 [p.1], Key switching 46 [p.1], NTT 15 [p.16], Rotations 14 [p.5], Rescaling 13 [p.5], SIMD packing 7 [p.1], Modulus switching 2 [p.10]
  • assumption: RLWE 19 [p.1], LWE 2 [p.33], Lattice-based 2 [p.32]
  • task: Language modeling / generation 18 [p.2]
  • topic: Homomorphic encryption 31 [p.1], Open source 2 [p.28]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/4-132_efficient-bootstrapping-in-fully-homomorphic-encryption-for.pdf catalogue 43 692.4 KB 64e51625fd52
references/schemes/s26-1_eprint-2026-956.pdf schemes 43 692.4 KB 64e51625fd52 byte-identical to references/catalogue/4-132_efficient-bootstrapping-in-fully-homomorphic-encryption-for.pdf

Database key: efficient-bootstrapping-in-fully-homomorphic-encryption-for-matrix · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-bootstrapping-in-fully-homomorphic-encryption-for-matrix COLUMN VALUE