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]
Related papers¶
- this paper follow up of Fully Homomorphic Encryption for Matrix Arithmetic — follow-up listed for scheme "Gentry–Lee (GL) matrix FHE"
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