PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably weak instances of Ring-LWE

Yara Elias, Kristin E. Lauter, Ekin Ozman, Katherine E. Stange

arXiv:1502.03708v2cs.CRmath.NT

TL;DR

Ring-LWE and Poly-LWE have security reductions, but general number rings have been less closely examined than cyclotomic rings. This paper extends Poly-LWE attacks to Ring-LWE and constructs provably weak instances. The attacks run in time linear in q, while the general dual approach can be difficult to carry out in number fields.

  • Problem

    Ring-LWE and Poly-LWE have been proposed as cryptographic hardness assumptions, but general number rings have received less close examination than cyclotomic rings.

    Source: §1 · p. 2

  • Method

    The paper extends the EHL Poly-LWE attack and maps certain Ring-LWE instances to Poly-LWE when the error distortion is sufficiently limited.

    Source: §1 · pp. 1–2

  • Results

    The authors construct provably weak Ring-LWE instances and report attacks running in time linear in q.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Ring-LWE hardness depends on number-field properties and q, and Poly-LWE vulnerability can also depend on polynomial basis choice.

    Source: §1 · p. 2

    Generalising dual Ring-LWE to general number fields may be difficult because working with the dual can be difficult.

    Source: §4.3 · p. 9

Abstract

from arXiv · show

The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus. Our attack is based on the attack on Poly-LWE which was presented in [Eisentr\"ager-Hallgren-Lauter]. We extend the EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-$2$ cyclotomic fields, presented using the minimal polynomial of $\zeta_{2^n} \pm 1$.

1. Introduction

The paper extends Poly-LWE attacks to Ring-LWE, identifying provably weak instances and an explicit family of vulnerable number fields. It also shows that vulnerability depends on the field, modulus, and polynomial basis.

1. Introduction

  • The paper extends earlier Poly-LWE attacks, which had identified weak Poly-LWE fields but no fields meeting both attack and reduction conditions.The authors strengthen and extend those attacks and apply them to Ring-LWE.Source: §1 · p. 1
  • The paper constructs an explicit family of number fields with an efficient attack on Decision Ring-LWE, the first such attacks for number fields with special properties.For Galois fields, an attack on decision also gives an attack on search Ring-LWE.Source: §1 · p. 1
  • Mapping Ring-LWE instances to Poly-LWE transfers the attack when the map does not distort the error too much; the spectral norm governs this distortion.For the constructed family, the authors prove success above a bound on √q/n and report practical attacks at ratios almost 100 times smaller.Source: §1 · p. 2
  • The attacks run in time linear in q, and the authors provide code and running times for practical demonstrations.One demonstration at n = 1024 and q = 2^31 − 1 runs in about 13 hours.Source: §1 · p. 2
  • Even 2-power cyclotomic fields can be weak for Poly-LWE under an alternative polynomial basis, while cyclotomic fields are immune to attacks based on roots of small order.The paper also supplies SAGE routines and successful attack demonstrations.Source: §1 · p. 2
  • Ring-LWE hardness depends on number-field properties and the choice of q, so some parameter choices may be significantly weaker than others.The paper notes that its roughly O(q) Poly-LWE attacks may apply to fields including 2-power cyclotomics with a bad polynomial basis.Source: §1 · p. 2

2. Background on Poly-LWE

This section defines the Poly-LWE sample distributions and describes parameter selection as an area not yet well explored. It gives representative parameter choices and notes a modulus issue in one recommendation.

2. Background on Poly-LWE

  • The paper models errors as discrete Gaussians of parameter σ, spherical in the power basis and truncated at width 2σ in practice.It denotes the uniform distribution on P ≃ Z^n by U and this Gaussian by Gσ.Source: §2 · p. 3
  • Poly-LWE samples have the form (a(x), b(x) = a(x)s(x) + e(x)), with uniform a(x), secret s(x), and Gaussian error e(x).The section distinguishes decision (distinguishing these samples from uniform independent pairs) and search (recovering s from samples).Source: §2 · p. 3

2.1. Parameter selection.

  • Parameter selection for Poly-LWE and Ring-LWE is not yet well explored, and recommendations generally draw on general-LWE recommendations while ignoring extra ring structure.Examples include the Lindner–Peikert, PGF, and PBCNS parameter sets.Source: §2.1 · p. 3
  • For TLS, PBCNS is listed as (n, q, w) = (1024, 2^31−1, 3.192); separately, q = 2^32−1 was suggested but is not prime, and q is large for correctness yet could potentially be decreased.Source: §2.1 · p. 3

3. Attacks on Poly-LWE

The Poly-LWE attacks map samples through a ring homomorphism and test secret guesses by checking whether the resulting errors look non-uniform. Two algorithms exploit either a small set of possible error values or small error magnitudes, with success depending on parameters and the root used.

3. Attacks on Poly-LWE

  • The general attack maps samples to Fq, tests guesses for s(α), and checks whether the resulting error values distinguish from uniform; a successful guess also reveals s(α).A small-order root α modulo q is the setting for the EHL attack.Source: §3 · pp. 3–4

3.1. Attack based on a small set of error values modulo q.

  • When r is small, e(α) takes only a small number of values modulo q, permitting efficient membership testing. For r = 2, assuming n is divisible by r, |S| = (2nσ)^2, and the attack succeeds with high probability if |S| << q.Source: §3.1 · p. 5
  • Algorithm 1 runs in eO(ℓq + nq) time and, unless it reports NOT PLWE, its samples are valid Poly-LWE with probability 1 − (#S/q)^ℓ.The stated probability tends to 1 as ℓ grows.Source: §3.1 · p. 5

3. Attacks on Poly-LWE

  • The broader homomorphism attack has vanishingly small success probability except in special situations, so its analysis also bolsters Poly-LWE security.The attack’s distinguishability depends on σ, n, ℓ, q, and the roots of f modulo q.Source: §3 · p. 4, §3.2 · p. 6

3.2. Attack based on the size of the error values.

  • Algorithm 2 runs in eO(ℓq) time under the proposition’s conditions, and its applicability overlaps with Algorithm 1.For α = ±1, Algorithm 2 covers more parameter choices; for other small orders, Algorithm 1 applies more broadly.Source: §3.2 · p. 8

4. Moving the attack from Poly-LWE to Ring-LWE

The section extends Poly-LWE attacks to Ring-LWE over general number fields by mapping instances into polynomial rings when the error distortion is controlled. It identifies conditions under which non-dual Ring-LWE decision instances can be solved in time linear in q.

4. Moving the attack from Poly-LWE to Ring-LWE

  • Ring-LWE errors are spherical Gaussians in the canonical embedding, discretized on the integer ring or its dual; the paper also considers general-number-ring definitions.The attack applies when the error image under a ring homomorphism occupies a small subset of Z/qZ; similar analysis can apply without spherical errors.Source: §4 · p. 8, §4.2 · pp. 8–9

4.1. The canonical embedding.

  • The canonical embedding maps each field element to real embedding coordinates and real and imaginary parts of complex embeddings in R^n.In this setup the inner product corresponds to the trace pairing.Source: §4.1 · p. 8

4.2. Spherical Gaussians and error distributions.

  • Ring-LWE errors are discretizations of spherical Gaussians on R or its dual, with parameters chosen to resist general LWE attacks.The continuous Gaussian is transferred through the embedding and then discretized on the corresponding lattice.Source: §4.2 · pp. 8–9

4.3. The Ring-LWE problems.

  • For general number rings, the paper distinguishes dual Ring-LWE, which retains the dual lattice, from non-dual Ring-LWE, which replaces it with the ring; the dual may be difficult to work with.The authors analyze both definitions because their security may differ; for cyclotomic fields, prior work states they are computationally equivalent [LPR, Section 3.3].Source: §4.3 · p. 9

4.4. Isomorphisms from θ(R) to a polynomial ring.

  • For a monogenic field, the ring and its dual can be represented by polynomial-basis isomorphisms, allowing either Ring-LWE problem to be restated as Poly-LWE.The ring of integers is represented as Z[X]/f(X), with the dual related through a generator of the different ideal.Source: §4.4 · p. 9

4.5. The spectral norm.

  • The spectral norm bounds how much a basis-change matrix can expand vectors, and therefore bounds the Gaussian error distortion under the isomorphism.The normalized spectral norm and condition number are also defined for the matrix.Source: §4.5 · p. 10, §4.6 · p. 10

4.6. Moving the attack from Poly-LWE to Ring-LWE

  • When the field is monogenic, f(1) ≡ 0 (mod q), and the distortion and error parameters are sufficiently small, the non-dual Ring-LWE decision problem is solvable in eO(ℓq) time with probability 1 − 2^-ℓ.The basis-change analysis relaxes the orthogonal-map assumption in [EHL]; its role is to keep transformed errors small enough for the Poly-LWE attack.Source: §4.6 · p. 10

4.7. Choice of σ.

  • The proposed Gaussian width accounts for the covolume of the embedded lattice, so sparse lattices use a larger σ to keep the same proportion of vectors within the bell.The resulting bound can be expressed using the normalized spectral norm.Source: §4.7 · p. 11

5. Provably weak Ring-LWE number fields

This section gives conditions for an explicit family of number fields whose non-dual Ring-LWE decision instances can be attacked. It also identifies how vulnerability varies with q and reports successful implementations.

5. Provably weak Ring-LWE number fields

  • For n a prime power, squarefree q − 1, and the stated divisibility condition, the polynomials f_n,q are monogenic.The monogenicity argument also goes through for p = 2, although the cited result requires an odd prime for its full conclusion.Source: §5 · p. 11
  • Under the theorem's stated conditions, the non-dual Ring-LWE decision problem for f and w is solvable in eO(ℓq) time with probability 1 − 2^-ℓ.The conditions include n being a prime power, q − 1 being squarefree, a divisibility condition, and τ > 1.Source: §5 · p. 12
  • Assuming q − 1 is infinitely often squarefree, the construction yields susceptible examples, including appropriate powers of 2 for n.For these powers of 2, the third theorem condition is automatic.Source: §5 · p. 12
  • Vulnerability is controlled by the ratio √q/n rather than overall size, provided q is small enough for a loop through its residues.The authors report that susceptibility increases as q grows relative to n.Source: §5 · p. 12
  • The theorem's τ bound is stronger than required in practice, and the spectral-norm estimate is worst-case rather than representative of average error inflation.As n increases, errors are increasingly unlikely to align with the direction that attains the full spectral norm; the paper reports several successful implemented attacks.Source: §5 · p. 13

6. Heuristics on the prevalence of weak Ring-LWE number fields

The section argues heuristically that vulnerable Ring-LWE fields may be common, then develops examples and spectral-norm evidence for that expectation.

6.1. Monogenicity.

  • For random degree-n≥4 polynomials, monogenicity is conjecturally expected with probability ≳0.307; cyclotomic fields are monogenic, but testing may be infeasible at n∼2^10.Source: §6.1 · p. 13

6.2. Examples, n = 210, q ∼232.

  • Two degree-2^10 examples use q=6442450967 and q=6442450979, and each satisfies f(1) ≡ 0 mod q; their spectral norms were not computed directly.Source: §6.2 · p. 13

6.3. Heuristics for the spectral norm.

  • For f(x)=x^n+ax+b, a perturbation argument suggests the condition number is often small, supporting the expectation that many such polynomials have small normalized spectral norm.Source: §6.3 · pp. 13–14

6.4. Experimental evidence for the spectral norm.

  • Most plotted x^32+ax+b cases cluster at low ρ′, although some have quite high values.Source: §6.4 · p. 14
  • For n=2^10 and max{a,b}≤2^30, examples are conjectured often to satisfy ρ′<2^15, the range required by Theorem 4.3; root 1 modulo q∼2^31 prevents smaller coefficients.Source: §6.4 · p. 14

7. Weak Poly-LWE number fields

The section gives methods for finding polynomials and primes that make Poly-LWE vulnerable, then presents examples—including cyclotomic fields in an alternative polynomial basis—that meet attack conditions. It also notes that checking splitting directly is infeasible at cryptographic sizes, though a sufficient test is available.

7.1. Finding f and q with roots of small order.

  • Given f, Algorithm 3 finds a prime q by computing a Bézout relation with Φ_m and returning the largest prime factor of the coefficient-denominator lcm.The section also describes constructing f from a chosen q using f(x) = Φ_m(x)g(x) + q.Source: §7.1 · p. 15

7.2. Examples, n ∼210, q ∼232.

  • For n ∼ 2^10, irreducible root-1 examples use q = 6442450967 or 6442450979 and satisfy condition 1 of Proposition 3.2 with σ = 3, hence are vulnerable.The root-of-order-3 example uses q ∼ 2^40; this larger q satisfies condition (2) of Proposition 3.1 and makes it vulnerable to Algorithm 1.Source: §7.2 · p. 15

7.3. Examples of weak Poly-LWE number fields with additional properties.

  • The section's examples require conditions for the attack and reductions; checking splitting directly is infeasible at cryptographic sizes, but a sufficient splitting condition is fast to check.The conditions include Galois and monogenic fields, complete splitting, and requirements for the Ring-LWE-to-Poly-LWE and search-to-decision reductions.Source: §7.3 · p. 16
  • The examples include cryptographic-size cyclotomic fields represented by the minimal polynomial of ζ_2^k + 1, and they are weak against the Poly-LWE attack.These examples satisfy the stated conditions, with splitting verified using Proposition 7.1.Source: §7.3 · pp. 16–17

8. Cyclotomic (in)vulnerability

For the standard cyclotomic polynomial, split-prime roots have order m, so the small-order-root attack does not apply. Alternative polynomial representations remain a possibility, but their transformed error distribution must also be considered.

8. Cyclotomic (in)vulnerability

  • Every root of Φ_m modulo a split prime q has order exactly m, excluding the small-order-root attack for this polynomial representation.The paper states that Φ_m's roots have order m modulo every split prime.Source: §8 · p. 17
  • An alternative polynomial representation could have a small-order root, but the transformed error distribution means this alone does not establish Poly-LWE vulnerability.Source: §8 · p. 17
  • To rule out such attacks without searching every representation, the paper checks the n homomorphisms from R_q to Z/qZ and whether errors map to a small subset.For cyclotomics, the n homomorphisms coincide.Source: §8 · p. 17

9. Successfully coded attacks

The section reports successful coded attacks on Poly-LWE and Ring-LWE examples, while noting that software limitations prevented testing Ring-LWE instances above dimension 256.

9. Successfully coded attacks

  • The tests include a cryptographic-size Poly-LWE attack and a generic Poly-LWE example also susceptible to Ring-LWE attack.The reported timings and parameters are documented in the table, but its values are not present in the supplied passage.Source: §9 · p. 17
  • Ring-LWE attacks were not tested for n > 256 because Sage's built-in discrete Gaussian sampler could not initialize at those dimensions.The section notes that the inability to test does not imply larger n are invulnerable when q also grows.Source: §9 · p. 17
  • The tested Ring-LWE examples illustrate an approximate practical security condition of τ < 0.013, compared with τ < 1 in theory.The final two tested rings are nonmaximal orders.Source: §9 · p. 17

A.1. Proof of concept for Ring-LWE and Poly-LWE attacks.

The appendix provides Sage code that verifies the attack procedures on the paper's examples. Its implementation uses Sage's lattice Gaussian sampler, which could not initialize in sufficiently large dimension for full testing.

A.1. Proof of concept for Ring-LWE and Poly-LWE attacks.

  • The Sage code verifies that Algorithm 2 succeeds on the Poly-LWE and Ring-LWE examples, and Algorithm 1 is a minor modification of Algorithm 2.Source: §A.1 · p. 19
  • Sage's built-in discrete Gaussian lattice sampler cannot initialize in sufficiently large dimension to fully test the attacks.The code is available electronically, and it includes error checks for insufficient numerical precision.Source: §A.1 · p. 19
  • The implementation constructs samples, maps them to F_q, and tests candidate residues against the samples to identify survivors.Source: §A.1 · pp. 20, 22, 23

A.2. Sage code for Algorithm 3.

The Sage algorithm returns the largest prime q for which a polynomial f has a root of order m modulo q.

  • The algorithm returns the largest prime q for which a polynomial f has a root of order m modulo q.Source: §A.2 · p. 24
  • The Sage code defines findq(f,m) using a polynomial ring over the rational field.Source: §A.2 · p. 24
  • It computes an extended gcd with x^m-1, takes coefficient denominators, factors their least common multiple, and returns the largest prime factor.Source: §A.2 · p. 24
Loading 1502.03708v2…