Paper 2024/634

NTRU-based FHE for Larger Key and Message Space

Robin Jadoul, COSIC, KU Leuven
Axel Mertens, COSIC, KU Leuven
Jeongeun Park, Norwegian University of Science and Technology (NTNU)
Hilder V. L. Pereira, Universidade Estadual de Campina

The NTRU problem has proven a useful building block for efficient bootstrapping in Fully Homomorphic Encryption (FHE) schemes, and different such schemes have been proposed. FINAL (ASIACRYPT 2022) first constructed FHE using homomorphic multiplexer (CMux) gates for the blind rotation operation. Later, XZD+23 (CRYPTO 2023) gave an asymptotic optimization by changing the ciphertext format to enable ring automorphism evaluations. In this work, we examine an adaptation to FINAL to evaluate CMux gates of higher arity and the resulting tradeoff to running times and bootstrapping key sizes. In this setting, we can compare the time and space efficiency of both bootstrapping protocols with larger key space against each other and the state of the art.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACISP 2024
Fully Homomorphic EncryptionNTRUBootstrappingFINAL
Contact author(s)
robin jadoul @ esat kuleuven be
axel mertens @ esat kuleuven be
jeongeun park @ ntnu no
hilder @ unicamp br
2024-04-26: approved
2024-04-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Robin Jadoul and Axel Mertens and Jeongeun Park and Hilder V. L. Pereira},
      title = {{NTRU}-based {FHE} for Larger Key and Message Space},
      howpublished = {Cryptology ePrint Archive, Paper 2024/634},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.