Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic
 
conference paper

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

Belorgey, M. G.
•
Carpov, S.
•
Gama, N.
Show more
Chung, Kai-Min
•
Sasaki, Yu
2025
Advances in Cryptology – ASIACRYPT 2024. 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part I
30th Annual International Conference on the Theory and Application of Cryptology and Information Security

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 XN+1. 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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-981-96-0875-1_6
Scopus ID

2-s2.0-85213383642

Author(s)
Belorgey, M. G.

Tune Insight SA

Carpov, S.

Arcium

Gama, N.

SandboxAQ

Guasch, S.

SandboxAQ

Jetchev, D.  

Arcium

Editors
Chung, Kai-Min
•
Sasaki, Yu
Date Issued

2025

Publisher

Springer

Publisher place

Singapore

Published in
Advances in Cryptology – ASIACRYPT 2024. 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part I
DOI of the book
https://doi.org/10.1007/978-981-96-0875-1
ISBN of the book

978-981-96-0875-1

Series title/Series vol.

Lecture Notes in Computer Science; 15484

ISSN (of the series)

1611-3349

0302-9743

Start page

176

End page

207

Subjects

bivariate representation

•

bootstrapping

•

gadget decomposition

•

homomorphic encryption

•

key switching

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
TAN  
Event nameEvent acronymEvent placeEvent date
30th Annual International Conference on the Theory and Application of Cryptology and Information Security

ASIACRYPT 2024

Kolkata, India

2024-12-09 - 2024-12-13

Available on Infoscience
January 10, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/242704
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés