Skip to content

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