CryptoDB
Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption~(FHE), has relied on *cyclotomic* number fields and rings. This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on "packed" plaintexts, automorphisms, and ring-switching. However, selecting a suitable cyclotomic that has the desired number and type of plaintext "slots," while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency. This work provides a suite of tools for instantiating ring-based lattice cryptography to work over *subfields* of cyclotomics, which provide more flexibility and better-fitting parameters for applications. A particular focus is on realizing FHE with *optimal plaintext packing* and homomorphic SIMD parallelism for *any* plaintext characteristic, along with efficient *packed bootstrapping* that fully exploits this parallelism. Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory: * For sampling and decoding errors in encryption and decryption (respectively), we construct *geometrically short, structured bases* for the number rings of arbitrary subfields of prime-power cyclotomics (and hence their composites as well). * For fast ring arithmetic, we define and establish analogous structural properties for Chinese Remainder Theorem~(CRT) bases in *abelian* number rings, and give *specialized fast transforms* that map between CRT bases and any similarly structured bases. * For packed bootstrapping and homomorphic linear algebra, we give a general framework for *homomorphic evaluation of structured linear transforms* in abelian number rings, and show that CRT transforms can be evaluated using relatively few homomorphic operations. |
BibTeX
@inproceedings{tcc-2025-36274,
title={Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE},
publisher={Springer-Verlag},
author={Chris Peikert and Zachary Pepin},
year=2025
}