NTRU-based FHE for Larger Key and Message Space

Robin Jadoul; Axel Mertens; Jeongeun Park; Hilder V. L. Pereira

Paper 2024/634 Original: eprint.iacr.org/2024/634 ↗

NTRU-based FHE for Larger Key and Message Space

Robin Jadoul

Axel Mertens

Jeongeun Park

Hilder V. L. Pereira

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2024-04-25: last updated; 2024-04-25: published
Short URL: https://ia.cr/2024/634
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2024/634,
      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},
      url = {https://eprint.iacr.org/2024/634}
}