Skip to content

FINAL: Faster FHE Instantiated with NTRU and LWE

Authors: Charlotte Bonte; Ilia Iliashenko; Jeongeun Park; Hilder V. L. Pereira; Nigel P. Smart
Year: 2022
Venue: ASIACRYPT 2022

type: scheme collection: catalogue, schemes status: auto

Links: DOI · ePrint 2022/74 · link · Semantic Scholar

Visual lesson: FINAL (NTRU + LWE) · Scheme table row: FINAL (NTRU + LWE)

Summary

Auto-extracted summary (unreviewed)

FINAL constructs two FHEW-style bootstrappable FHE schemes whose NTRU parameters stay below the 'fatigue point' where sublattice attacks on overstretched NTRU apply, using the Ducas-van Woerden analysis. The first scheme relies solely on NTRU and is competitive with TFHE; the second combines NTRU and LWE and bootstraps 28% faster than TFHE with 45% smaller bootstrapping and key-switching keys.

Abstract

The NTRU problem is a promising candidate to build efficient Fully Homomorphic Encryption (FHE). However, all the existing proposals (e.g. LTV, YASHE) need so-called ‘overstretched’ parameters of NTRU to enable homomorphic operations. It was shown by Albrecht et al. (CRYPTO 2016) that these parameters are vulnerable against subfield lattice attacks. Based on a recent, more detailed analysis of the overstretched NTRU assumption by Ducas and van Woerden (ASIACRYPT 2021), we construct two FHE schemes whose NTRU parameters lie outside the overstretched range. The first scheme is based solely on NTRU and demonstrates competitive performance against the state-of-the-art FHE schemes including TFHE. Our second scheme, which is based on both the NTRU and LWE assumptions, outperforms TFHE with a 28% faster bootstrapping and 45% smaller bootstrapping and key-switching keys.
Source: pdf

Extracted details

Field Value Source Confidence
contribution FHE scheme based solely on NTRU with parameters outside the overstretched regime llm 0.85
contribution Hybrid NTRU+LWE FHE scheme that outperforms TFHE in bootstrapping time and key size llm 0.85
contribution Parameter selection grounded in the Ducas-van Woerden NTRU fatigue analysis llm 0.85
contribution Open-source implementation llm 0.85
schemes NTRU llm 0.85
schemes LWE llm 0.85
schemes FHEW-style bootstrapping llm 0.85
schemes TFHE llm 0.85
tasks boolean gate bootstrapping llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/WvanWoerden/NTRUFatigue (URL found in the full text) regex 0.50
code url https://github.com/KULeuven-COSIC/FINAL (URL found in the full text) regex 0.50
code url https://github.com/KULeuven-COSIC/FINAL llm 0.85
limitations Better parameters (sampling NTRU secrets f and g with different variances) could widen the gap over TFHE but lack a formal concrete-hardness analysis, so they were not used llm 0.85
limitations Circuit bootstrapping (as in TFHE) is left for future work llm 0.85
limitations NTRU rings offer little flexibility in choosing parameters for a target security level llm 0.85
llm relevance low llm 0.85
key result bootstrapping speed-up: 28% faster than TFHE (NTRU+LWE scheme) llm 0.85
key result key size reduction: 45% smaller bootstrapping and key-switching keys than TFHE (NTRU+LWE scheme) llm 0.85
key result performance of pure-NTRU scheme: competitive with TFHE (NTRU-only scheme) llm 0.85

Scheme card: FINAL (NTRU + LWE)

Group 3. Bit-wise / lookup-table FHE (GSW, FHEW, TFHE family)
Kind Scheme
Hardness assumption NTRU + LWE
Plaintext type Bits
SIMD packing No
Bootstrapping Yes, fast
Post-quantum Yes
Status Niche
Fit for LLM inference NTRU-based gate bootstrapping with smaller keys than TFHE.
Follow-ups FINALLY multi-key NTRU FHE (CIC 2024, 2024/1505).
Libraries FINAL
Follow-up papers in the archive FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE

System card: FINAL (NTRU + LWE)

Group 4. Alternative FHE schemes
Family NTRU-based bootstrapping
Arithmetic Bits
Interaction Non-interactive
Model scale -
Status Niche
Relation to the SoK NTRU alternative to TFHE gate bootstrapping.
Note Smaller keys and faster bootstrapping than TFHE at the time, with NTRU security caveats.
Code https://github.com/KULeuven-COSIC/FINAL
Systems page FINAL (NTRU + LWE)

Keyword mentions

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

  • scheme: NTRU 113 [p.1], TFHE 55 [p.1], GSW 20 [p.2], FHEW 7 [p.2], Leveled / somewhat HE 4 [p.1], YASHE 3 [p.1], FINAL 2 [p.1], Hybrid HE / transciphering 2 [p.4], PIR 2 [p.4]
  • library: Concrete (Zama) 1 [p.18], Zama 1 [p.1]
  • technique: Bootstrapping 93 [p.1], Key switching 29 [p.1], Modulus switching 9 [p.12]
  • assumption: LWE 55 [p.1], Lattice-based 19 [p.1], RLWE 8 [p.1]
  • topic: Homomorphic encryption 44 [p.1], Open source 2 [p.19]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/4-057_final-faster-fhe-instantiated-with-ntru-and-lwe.pdf catalogue 24 455.5 KB dbf2e69f225c
references/schemes/s24-0_final-faster-fhe-instantiated-with-ntru-and-lwe.pdf schemes 24 455.5 KB dbf2e69f225c byte-identical to references/catalogue/4-057_final-faster-fhe-instantiated-with-ntru-and-lwe.pdf

Database key: final-faster-fhe-instantiated-with-ntru-and-lwe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set final-faster-fhe-instantiated-with-ntru-and-lwe COLUMN VALUE