Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic

Mariya Georgieva Belorgey; Sergiu Carpov; Nicolas Gama; Sandra Guasch; Dimitar Jetchev

Paper 2023/771

Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic

Mariya Georgieva Belorgey, Tune Insight, Lausanne, Switzerland

Sergiu Carpov, Arcium, Baar, Switzerland

Nicolas Gama, SandboxAQ, Palo Alto, USA

Sandra Guasch, SandboxAQ, Palo Alto,, USA

Dimitar Jetchev, IOG, Colorado, Costa Rica, EPFL, Lausanne, Switzerland

Abstract

Ring-LWE based homomorphic encryption computations in large depth use a combination of two techniques: 1) decomposition of big numbers into small limbs/digits, and 2) efficient cyclotomic multiplications modulo . It was long believed that the two mechanisms had to be strongly related, like in the full-RNS setting that uses a CRT decomposition of big numbers over an NTT-friendly family of prime numbers, and NTT over the same primes for multiplications. However, in this setting, NTT was the bottleneck of all large-depth FHE computations. A breakthrough result from Kim et al. (Crypto’2023) managed to overcome this limitation by introducing a second gadget decomposition and showing that it indeed shifts the bottleneck and renders the cost of NTT computations negligible compared to the rest of the computation. In this paper, we extend this result (far) beyond the Full-RNS settings and show that we can completely decouple the big number decomposition from the cyclotomic arithmetic aspects. As a result, we get modulus switching/rescaling for free. We verify both in theory and in practice that the performance of key-switching, external and internal products and automorphisms using our representation are faster than the one achieved by Kim et al., and we discuss the high impact of these results for low-level or hardware optimizations as well as the benefits of the new parametrizations for FHE compilers. We even manage to lower the running time of the gate bootstrapping of TFHE by eliminating one eighth of the FFTs and one sixth of the linear operations, which lowers the running time below 5.5ms on recent CPUs.

Note: Full version of the paper.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2024
Keywords: homomorphic encryption gadget decomposition key switching bivariate representation
Contact author(s): maria georgievabs @ gmail com
sergiu @ inpher io
nicolas gama @ sandboxquantum com
sandra guasch @ sandboxaq com
dimitar @ inpher io
History: 2024-09-20: last of 3 revisions; 2023-05-26: received; See all versions
Short URL: https://ia.cr/2023/771
License: CC BY

BibTeX

@misc{cryptoeprint:2023/771,
      author = {Mariya Georgieva Belorgey and Sergiu Carpov and Nicolas Gama and Sandra Guasch and Dimitar Jetchev},
      title = {Revisiting Key Decomposition Techniques for {FHE}: Simpler, Faster and More Generic},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/771},
      year = {2023},
      url = {https://eprint.iacr.org/2023/771}
}