Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused¶
Authors: Youngjin Bae; Jung Hee Cheon; Guillaume Hanrot; Jai Hyun Park; Damien Stehlé
Year: 2024
Venue: CRYPTO 2024
type: technique collection: catalogue status: auto
Links: DOI · ePrint 2024/1284 · Semantic Scholar
Summary¶
Auto-extracted summary (unreviewed)
Proposes RLWE-based algorithms for plaintext-ciphertext matrix multiplication (PC-MM), the core operation of private transformer evaluation, that reduce the work to plaintext-plaintext matrix multiplications plus cheap pre/post-processing; with precomputation a PC-MM costs a single floating-point PP-MM that can run on BLAS. The algorithms use a multi-secret RLWE format with conversions to and from standard ciphertexts, which also speeds up the SlotsToCoeffs/CoeffsToSlots steps of batched CKKS bootstrapping and yields MaMBo, a bootstrapping that performs a PC-MM for limited extra cost. Single-thread HEaaN experiments show d x d PC-MM in 0.31 s for d=256 up to 347 s for d=16384, with the floating-point optimization saving a factor of 2 to 4.
Abstract¶
Homomorphically multiplying a plaintext matrix with a ciphertext matrix (PC-MM) is a central task for the private evaluation of transformers, commonly used for large language models. We provide several RLWE-based algorithms for PC-MM that consist of multiplications of plaintext matrices (PP-MM) and comparatively cheap pre-processing and post-processing steps: for small and large dimensions compared to the RLWE ring degree, and with and without precomputation. For the algorithms with precomputation, we show how to perform a PC-MM with a single floating-point PP-MM of the same dimensions. This is particularly meaningful for practical purposes as a floating-point PP-MM can be implemented using high-performance BLAS libraries. The algorithms rely on the multi-secret variant of RLWE, which allows to represent multiple ciphertexts more compactly. We give algorithms to convert from usual shared-secret RLWE ciphertexts to multi-secret ciphertexts and back. Further, we show that this format is compatible with homomorphic addition, plaintext-ciphertext multiplication, and key-switching. This in turn allows us to accelerate the slots-to-coeffs and coeffs-to-slots steps of CKKS bootstrapping when several ciphertexts are bootstrapped at once. Combining batch-bootstrapping with efficient PC- MM results in MaMBo(Matrix Multiplication Bootstrapping), a bootstrapping algorithm that can perform a PC-MM for a limited overhead.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | RLWE-based PC-MM algorithms reducing to plaintext matrix multiplications for small and large dimensions | llm | 0.85 |
| contribution | PC-MM with precomputation as a single floating-point PP-MM (BLAS-friendly) | llm | 0.85 |
| contribution | Multi-secret RLWE ciphertext format with conversion algorithms and compatibility with addition, plaintext multiplication and key-switching | llm | 0.85 |
| contribution | Accelerated batched CKKS bootstrapping (SlotsToCoeffs/CoeffsToSlots) | llm | 0.85 |
| contribution | MaMBo: fused matrix-multiplication bootstrapping | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| schemes | RLWE | llm | 0.85 |
| schemes | multi-secret RLWE (MLWE) | llm | 0.85 |
| libraries | HEaaN | llm | 0.85 |
| libraries | OpenBLAS | llm | 0.85 |
| tasks | plaintext-ciphertext matrix multiplication | llm | 0.85 |
| tasks | CKKS bootstrapping | llm | 0.85 |
| tasks | private transformer/LLM inference (motivation) | llm | 0.85 |
| hardware | Intel Xeon Gold 6242 CPU 2.80GHz (single thread, AVX512) | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/malb/lattice-estimator (URL found in the full text) | regex | 0.50 |
| llm relevance | medium | llm | 0.85 |
| key result | PC-MM latency: 0.309 s (256 x 256 matrices, N=2^13, single thread, floating-point PP-MM optimization) | llm | 0.85 |
| key result | PC-MM latency: 17.1 s (4096 x 4096 matrices, single thread, floating-point PP-MM optimization) | llm | 0.85 |
| key result | PC-MM latency: 347 s (625 s without fp optimization) (16384 x 16384 matrices, Alg. 1, single thread) | llm | 0.85 |
| key result | speed-up from floating-point PP-MM: constant factor 2 to 4 (versus modular PP-MM) | llm | 0.85 |
| key result | relative precision: about 19 bits (modular) / about 13 bits (floating-point) (random matrices in [-1,1], log d from 8 to 14) | llm | 0.85 |
System card: Fused plaintext-ciphertext matmul and bootstrapping¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping + matmul |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Active SOTA |
| Relation to the SoK | Folds matrix multiplication into bootstrapping transforms. |
| Note | Related to the operation fusion used by SecretVoice in the SoK. |
| Systems page | Fused plaintext-ciphertext matmul and bootstrapping |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 22 [p.1], BGV 4 [p.2], BFV 3 [p.2]
- library: HEaaN (library) 9 [p.4], HElib 1 [p.34]
- model: LLaMA 3 [p.2], BERT 2 [p.1], GPT 2 [p.1]
- hardware: Intel Xeon 2 [p.2], AVX-512 1 [p.29]
- technique: Bootstrapping 72 [p.1], Matrix multiplication 21 [p.1], Rescaling 19 [p.7], Key switching 18 [p.1], Rotations 6 [p.4], Programmable bootstrapping 3 [p.4]
- assumption: RLWE 135 [p.1], Module-LWE 55 [p.3], LWE 7 [p.2], Lattice-based 7 [p.4], 128-bit security 3 [p.3]
- topic: Homomorphic encryption 15 [p.1], Large language models 11 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-040_plaintext-ciphertext-matrix-multiplication-and-fhe-bootstrap.pdf |
catalogue | 40 | 789.3 KB | 61bb2d8630b9 |
Database key: plaintext-ciphertext-matrix-multiplication-and-fhe-bootstrapping-fast · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set plaintext-ciphertext-matrix-multiplication-and-fhe-bootstrapping-fast COLUMN VALUE