Skip to content

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]

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