Fully Homomorphic Encryption for Matrix Arithmetic¶
Authors: C. Gentry; Y. Lee
Year: 2025
Venue: IACR ePrint 2025/1935
type: scheme collection: catalogue, schemes, sok-references status: auto
Links: ePrint 2025/1935
Visual lesson: Gentry–Lee (GL) matrix FHE · Scheme table row: Gentry–Lee (GL) matrix FHE
Summary¶
Auto-extracted summary (unreviewed)
Gentry and Lee propose an RLWE-based FHE scheme whose slot encoding natively represents batched matrices, so that ciphertext-ciphertext matrix multiplication reduces to four matrix multiplications of ciphertext coefficients plus a key switching that costs only 2-4x that of a Hadamard multiplication, with no slot-to-coefficient conversion or ring switching. The scheme also supports transposition, inter- and intra-matrix rotations, integer matrices, and existing bootstrapping; in an implementation using FLINT, key switching for 16 complex 256x256 matrices takes 3.32 s for matrix multiplication versus 1.17 s for Hadamard multiplication, leaving the plain matrix multiplication as the dominant cost.
Abstract¶
We propose an efficient fully homomorphic encryption (FHE) scheme tailored for matrix arithmetic based on the Ring-Learning with Errors (RLWE) problem. The proposed scheme naturally supports matrix multiplication, addition, and Hadamard multiplication for batched matrices of various sizes over both complex numbers and integers. Encrypted matrix multiplication is reduced to four matrix multiplications of ciphertext elements, without the need for expensive operations such as slot-to-coefficient conversion or ring switching. In addition, the scheme efficiently supports matrix transformations, including general and conjugate transpositions, as well as matrix rotations: inter-matrix rotations across batched matrices and intra-matrix rotations within rows and columns. Moreover, the proposed FHE scheme can be directly combined with existing bootstrapping algorithms. By eliminating the need for expensive operations such as repeated slot rotations and conversion between slot- and coefficient-encoding, the proposed construction achieves significant performance improvements. In our construction, encrypted multiplications of n×n matrices under slot encoding are decomposed into two parts: (1) matrix multiplication — four n × n matrix multiplications of ciphertext coefficients, and (2) key switching — with a total cost approximately 2–4 times that of Hadamard multiplication. We implemented the proposed scheme and utilized the FLINT library for the matrix multiplication component. Experimental results demonstrate that, even when leveraging highly optimized implementations, matrix multiplication remains the major cost, indicating that our construction substantially reduces auxiliary overheads and achieves strong overall efficiency.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | RLWE-based FHE scheme with matrix-structured slot encoding supporting batched matrix addition, multiplication and Hadamard product | llm | 0.85 |
| contribution | Encrypted matrix multiplication reduced to four coefficient-matrix multiplications plus a key switching costing 2-4x a Hadamard multiplication | llm | 0.85 |
| contribution | Support for general and conjugate transposition and inter-/intra-matrix rotations | llm | 0.85 |
| contribution | Generalization to integer matrices | llm | 0.85 |
| contribution | Compatibility with existing bootstrapping algorithms | llm | 0.85 |
| contribution | Implementation using FLINT for the matrix multiplication component with optimized multiplication in M_n(Z_q[i]) | llm | 0.85 |
| schemes | RLWE-based FHE | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| schemes | BFV | llm | 0.85 |
| schemes | BGV | llm | 0.85 |
| libraries | FLINT | llm | 0.85 |
| libraries | OpenFHE | llm | 0.85 |
| tasks | encrypted matrix multiplication | llm | 0.85 |
| tasks | privacy-preserving LLM attention (motivation) | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| limitations | Even with highly optimized libraries, the four ciphertext-coefficient matrix multiplications remain the dominant cost | llm | 0.85 |
| llm relevance | medium | llm | 0.85 |
| key result | key-switching time for matrix multiplication: 3.32 s (16 complex matrices of size 256x256, 128-bit security) | llm | 0.85 |
| key result | key-switching time for Hadamard multiplication: 1.17 s (16 complex matrices of size 256x256) | llm | 0.85 |
| key result | amortized key-switching cost: 1.11 us (this work) vs 0.82 us (OpenFHE) (Hadamard multiplication, per slot) | llm | 0.85 |
| key result | key-switching overhead of matrix multiplication: typically 2-3x, at most 4x that of Hadamard multiplication (slot-encoded n x n matrices) | llm | 0.85 |
Scheme card: Gentry–Lee (GL) matrix FHE¶
| Group | 4. Matrix-native FHE |
| Kind | Scheme |
| Hardness assumption | RLWE-style (matrix rings) |
| Plaintext type | Approximate real matrices (CKKS-like) |
| SIMD packing | Native matrices |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Active SOTA (emerging) |
| Fit for LLM inference | Strongest candidate successor to CKKS for LLMs. Matrix products need few rotations and few keys. The SoK expects its findings to transfer. |
| Follow-ups | Efficient GL bootstrapping (2026/956); low-depth bootstrapping (2026/811); Trace-Factored BigSwitch keys (2026/2058); first GPU Transformer on GL: Terrazzo (2026/1870). |
| Follow-up papers in the archive | Terrazzo: Memory-Aware GPU Framework for Private Transformer Inference Efficient Bootstrapping in Fully Homomorphic Encryption for Matrix Arithmetic Low-Depth Bootstrapping for Matrix-Native FHE Trace-Factored BigSwitch for Matrix-Friendly FHE |
System card: Gentry-Lee matrix FHE (GL scheme)¶
| Group | 4. Alternative FHE schemes |
| Family | New lattice FHE, native matrices |
| Arithmetic | Approximate real matrices |
| Interaction | Non-interactive |
| Model scale | None yet |
| Status | Active SOTA (emerging) |
| Relation to the SoK | Same arithmetic as CKKS but natively on matrices. |
| Note | Removes most rotations and rotation keys in linear algebra. The SoK expects its CKKS recommendations to transfer directly. 2026 follow-ups now cover GL bootstrapping, key size and a first GPU Transformer framework (Terrazzo). |
| Systems page | Gentry-Lee matrix FHE (GL scheme) |
SoK reference [107]¶
C. Gentry and Y. Lee, “Fully homomorphic encryption for matrix arithmetic,” Cryptology ePrint Archive, Paper 2025/1935, 2025. [Online]. Available: https://eprint.iacr.org/2025/1935
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 16 [p.3], BGV 11 [p.3], BFV 7 [p.3], FHEW 2 [p.25]
- library: OpenFHE 4 [p.3], HElib 2 [p.26]
- hardware: GPU 1 [p.24]
- technique: Matrix multiplication 103 [p.1], Key switching 58 [p.1], Rotations 28 [p.1], Bootstrapping 22 [p.1], NTT 17 [p.6], Modulus switching 8 [p.8], Relinearization 7 [p.2], Rescaling 7 [p.8], SIMD packing 5 [p.3]
- assumption: RLWE 45 [p.1], LWE 3 [p.2], Lattice-based 2 [p.25], 128-bit security 2 [p.22]
- task: Language modeling / generation 4 [p.7]
- topic: Homomorphic encryption 44 [p.1], Large language models 2 [p.3]
Related papers¶
- Efficient Bootstrapping in Fully Homomorphic Encryption for Matrix Arithmetic follow up of this paper — follow-up listed for scheme "Gentry–Lee (GL) matrix FHE"
- Low-Depth Bootstrapping for Matrix-Native FHE follow up of this paper — follow-up listed for scheme "Gentry–Lee (GL) matrix FHE"
- Trace-Factored BigSwitch for Matrix-Friendly FHE follow up of this paper — follow-up listed for scheme "Gentry–Lee (GL) matrix FHE"
- Terrazzo: Memory-Aware GPU Framework for Private Transformer Inference follow up of this paper — follow-up listed for scheme "Gentry–Lee (GL) matrix FHE"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-032_fully-homomorphic-encryption-for-matrix-arithmetic.pdf |
catalogue | 27 | 654.3 KB | 985173da6bc4 |
|
references/schemes/s26-0_fully-homomorphic-encryption-for-matrix-arithmetic.pdf |
schemes | 27 | 654.3 KB | 985173da6bc4 |
byte-identical to references/catalogue/4-032_fully-homomorphic-encryption-for-matrix-arithmetic.pdf |
references/sok-references/107_fully-homomorphic-encryption-for-matrix-arithmetic.pdf |
sok-references | 27 | 654.3 KB | 985173da6bc4 |
byte-identical to references/catalogue/4-032_fully-homomorphic-encryption-for-matrix-arithmetic.pdf |
Database key: fully-homomorphic-encryption-for-matrix-arithmetic · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fully-homomorphic-encryption-for-matrix-arithmetic COLUMN VALUE