Skip to content

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

Authors: Jeongeun Park; Barry van Leeuwen; Oliver Zajonc
Year: 2024
Venue: IACR Communications in Cryptology

type: technique collection: schemes status: auto

Links: DOI · ePrint 2024/1505 · Semantic Scholar

Summary

Auto-extracted summary (unreviewed)

FINALLY extends the NTRU/LWE-based FINAL scheme to the multi-key setting, re-opening NTRU-based multi-key FHE while keeping parameters below the NTRU fatigue point. By redefining how the hybrid-product construction is used (amortizing key-switching key generation over bootstraps), the scheme reduces the computational complexity from quadratic to linear in the number of keys and gives up to 40% smaller keys and computation time than LWE-based multi-key TFHE.

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.
Source: crossref

Extracted details

Field Value Source Confidence
contribution Multi-key FHE scheme built on FINAL (NTRU + LWE) with parameters under the fatigue point llm 0.80
contribution Noise-growth analysis for both single-key and multi-key FINAL llm 0.80
contribution Complexity reduced to O(Nkl) polynomial multiplications, linear in the number of keys llm 0.80
contribution Redefined use of the hybrid product so key-switching key generation is amortized over bootstraps llm 0.80
schemes NTRU llm 0.80
schemes LWE llm 0.80
schemes multi-key FHE llm 0.80
schemes FINAL llm 0.80
schemes TFHE llm 0.80
tasks multi-party computation on data encrypted under multiple keys llm 0.80
threat model multiple mutually distrusting input parties outsourcing computation to another party llm 0.80
interaction non-interactive FHE llm 0.80
limitations Parameter sets are only proof of concept; a finer analysis may yield more efficient parameters llm 0.80
limitations Multi-key FHE suffers larger error inflation than single-key FHE, requiring larger parameters llm 0.80
llm relevance low llm 0.80
key result computational complexity in number of keys: linear instead of quadratic (vs state-of-the-art multi-key TFHE) llm 0.80
key result key size and computation time: up to 40% smaller (vs LWE-based multi-key FHE) llm 0.80

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: NTRU 38 [p.1], FINAL 27 [p.1], Multi-key HE 18 [p.1], TFHE 12 [p.1], FHEW 3 [p.2], MPC 3 [p.28], GSW 2 [p.3]
  • technique: Key switching 49 [p.2], Bootstrapping 47 [p.1], Modulus switching 3 [p.16], Rotations 2 [p.3]
  • assumption: LWE 42 [p.1], RLWE 10 [p.9]
  • topic: Homomorphic encryption 37 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s24-1_eprint-2024-1505.pdf schemes 29 686.3 KB 97d2375e041c
references/schemes/s38-3_eprint-2024-1505.pdf schemes 29 686.3 KB 97d2375e041c byte-identical to references/schemes/s24-1_eprint-2024-1505.pdf

Database key: finally-a-multi-key-fhe-scheme-based-on-ntru-and-lwe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set finally-a-multi-key-fhe-scheme-based-on-ntru-and-lwe COLUMN VALUE