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]
Related papers¶
- FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE follow up of this paper — follow-up listed for scheme "FINAL (NTRU + LWE)"
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