FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE

Jeongeun Park; Barry Van Leeuwen; Oliver Zajonc

Paper 2024/1505

FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE

Jeongeun Park

, Norwegian University of Science and Technology

Barry Van Leeuwen

, KU Leuven

Oliver Zajonc

, KU Leuven

Abstract

Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in CIC 2024
DOI: https://doi.org/10.62056/aebn-4c2h
Keywords: FHE Multi-key FHE LWE NTRU
Contact author(s): jeongeun park @ ntnu no
barry vanleeuwen @ kuleuven be
oliver zajonc @ esat kuleuven be
History: 2024-10-10: last of 2 revisions; 2024-09-25: received; See all versions
Short URL: https://ia.cr/2024/1505
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1505,
      author = {Jeongeun Park and Barry Van Leeuwen and Oliver Zajonc},
      title = {{FINALLY}: A Multi-Key {FHE} Scheme Based on {NTRU} and {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1505},
      year = {2024},
      doi = {https://doi.org/10.62056/aebn-4c2h},
      url = {https://eprint.iacr.org/2024/1505}
}