Skip to content

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]

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