Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme¶
Authors: Bos, Lauter, Loftus, Naehrig
Year: 2013
Venue: IMA Cryptography and Coding 2013
type: scheme collection: schemes status: auto
Links: ePrint 2013/75 · link
Visual lesson: YASHE · Scheme table row: YASHE
Summary¶
Auto-extracted summary (unreviewed)
The paper constructs a new fully homomorphic encryption scheme (YASHE) from the Stehle-Steinfeld provably secure NTRU variant, using Brakerski's scale-invariant tensoring technique to remove the non-standard decisional small polynomial ratio (DSPR) assumption required by Lopez-Alt, Tromer and Vaikuntanathan; security rests on standard lattice assumptions plus circular security, ciphertexts are a single ring element, and modulus switching is avoided. A more practical variant YASHE' (still using DSPR) is implemented in C: with ring dimension 4096, t=2^10 and a 127-bit modulus, encryption takes 27 ms, ciphertext multiplication 31 ms, addition 0.024 ms and decryption 5 ms on an Intel Core i7-3520M, one to two orders of magnitude faster than a prior implementation; a CRT-based encoding extends the input size.
Abstract¶
In 1996, Hoffstein, Pipher and Silverman introduced an ef- ficient lattice based encryption scheme dubbed NTRUEncrypt. Unfortunately, this scheme lacks a proof of security. However, in 2011, Stehl´e and Steinfeld showed how to modify NTRUEncrypt to reduce security to standard problems in ideal lattices. In 2012, L´opez-Alt, Tromer and Vaikuntanathan proposed a fully homomorphic scheme based on this modified system. However, to allow homomorphic operations and prove security, a non-standard assumption is required. In this paper, we show how to remove this non-standard assumption via techniques introduced by Brakerski and construct a new fully homomorphic encryption scheme from the Stehl´e and Steinfeld version based on standard lattice assumptions and a circular security assumption. The scheme is scale-invariant and therefore avoids modulus switching and the size of ciphertexts is one ring element. Moreover, we present a practical variant of our scheme, which is secure under stronger assumptions, along with parameter recommendations and promising implementation results. Finally, we present an approach for encrypting larger input sizes by extending ciphertexts to several ring elements via the CRT on the message space.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | FHE scheme from the Stehle-Steinfeld NTRU variant secure under standard lattice assumptions and circular security, without DSPR | llm | 0.90 |
| contribution | scale-invariant construction avoiding modulus switching with single-ring-element ciphertexts | llm | 0.90 |
| contribution | practical variant YASHE' with parameter recommendations and C implementation results | llm | 0.90 |
| contribution | ciphertext word truncation optimization reducing ciphertext and evaluation-key size | llm | 0.90 |
| contribution | CRT-based encoding to extend plaintext input size across multiple ciphertexts | llm | 0.90 |
| schemes | YASHE | llm | 0.90 |
| schemes | NTRU | llm | 0.90 |
| schemes | RLWE | llm | 0.90 |
| tasks | homomorphic encryption primitive benchmarking | llm | 0.90 |
| hardware | Intel Core i7-3520M CPU (2.9 GHz) | llm | 0.90 |
| security level | 80-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| limitations | the practical variant YASHE' still requires the stronger DSPR assumption | llm | 0.90 |
| limitations | HE remains practical mainly for shallow circuits (around 2^2 to 2^5 multiplications) rather than deep circuits such as AES | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | encryption time: 27 ms (79.2 million cycles) (YASHE', R=Z[X]/(X^4096+1), t=2^10, 127-bit prime q, w=2^32, Core i7-3520M) | llm | 0.90 |
| key result | ciphertext multiplication time (incl. key switching): 31 ms (90.7 million cycles) (same parameters) | llm | 0.90 |
| key result | ciphertext addition time: 0.024 ms (70 thousand cycles) (same parameters) | llm | 0.90 |
| key result | decryption time: 5 ms (14.1 million cycles) (same parameters) | llm | 0.90 |
| key result | speed-up vs prior implementation: one to two orders of magnitude (vs 756 ms encryption / 1590 ms multiplication / 57 ms decryption on Intel Core 2 Duo 2.1 GHz) | llm | 0.90 |
Scheme card: YASHE¶
| Group | 5. Earlier and other FHE constructions |
| Kind | Scheme |
| Hardness assumption | NTRU + RLWE |
| Plaintext type | Exact integers |
| SIMD packing | Yes |
| Bootstrapping | Leveled |
| Post-quantum | Broken parameters (subfield attacks) |
| Status | Deprecated |
| Fit for LLM inference | Once competitive with BFV. Abandoned after overstretched-NTRU attacks. |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: YASHE 83 [p.8], Leveled / somewhat HE 7 [p.3], NTRU 3 [p.20], RSA 2 [p.20]
- technique: Key switching 14 [p.2], Bootstrapping 5 [p.3], Modulus switching 4 [p.1]
- assumption: Lattice-based 20 [p.1], RLWE 19 [p.2], IND-CPA 9 [p.11], LWE 8 [p.2]
- topic: Homomorphic encryption 33 [p.1]
Related papers¶
- this paper follow up of On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption — follow-up listed for scheme "LTV (NTRU multi-key FHE)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s32-1_eprint-2013-075.pdf |
schemes | 30 | 502.4 KB | ee7117ce06bf |
|
references/schemes/s33-0_improved-security-for-a-ring-based-fully-homomorphic-encrypt.pdf |
schemes | 30 | 502.4 KB | ee7117ce06bf |
byte-identical to references/schemes/s32-1_eprint-2013-075.pdf |
Database key: improved-security-for-a-ring-based-fully-homomorphic-encryption-scheme · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set improved-security-for-a-ring-based-fully-homomorphic-encryption-scheme COLUMN VALUE