Welcome to the resource topic for 2025/1760
Title:
Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE
Authors: Chris Peikert, Zachary Pepin
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.
ePrint: https://eprint.iacr.org/2025/1760
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .