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]
Related papers¶
- this paper follow up of FINAL: Faster FHE Instantiated with NTRU and LWE — follow-up listed for scheme "FINAL (NTRU + LWE)"
- this paper follow up of Multi-Key Homomorphic Encryption from TFHE — follow-up listed for scheme "Multi-key TFHE"
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