Weak Instances of PLWE

Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter

TL;DR

This paper introduces a novel attack that breaks the Polynomial Learning With Errors (PLWE) assumption in specific types of number fields. This is significant because PLWE is a foundational assumption for many modern cryptographic schemes, including fully homomorphic encryption. The attack exploits a particular property of the number field's polynomial, making certain PLWE instances computationally feasible to break.

What Problem Does This Paper Address?

The paper tackles the security of the Polynomial Learning With Errors (PLWE) assumption, a cryptographic primitive that underpins advanced encryption techniques like fully homomorphic encryption (FHE). PLWE is a variant of the Ring Learning With Errors (RLWE) problem, which itself is derived from the Learning With Errors (LWE) problem. While RLWE and PLWE offer efficiency advantages over standard LWE, their security relies on the hardness of underlying lattice problems.

The PLWE assumption, as defined in prior work ([BV11]), is known to be as hard as RLWE for specific types of number fields, particularly 2-power cyclotomic fields. However, the security of PLWE in more general number fields was less understood. The challenge was to determine if the structural properties of these more general number fields could be exploited to create "weak instances" of PLWE that are easier to break than the general assumption suggests. This paper investigates this very question, aiming to identify conditions under which PLWE instances are not as hard as presumed, and to develop an attack exploiting these conditions.

Methods

The core of the paper's contribution lies in developing a new attack on PLWE instances that satisfy specific properties related to the number field and the modulus. The attack leverages a key observation: if the polynomial defining the number field, $f(x)$, has the property that $f(1) \equiv 0 \pmod{q}$ (where $q$ is the modulus), then it becomes possible to distinguish PLWE samples from random ones.

The attack proceeds as follows:

  1. Guessing a secret value: The attacker guesses the value of the secret polynomial $s$ evaluated at 1, i.e., $s(1)$. Since $f(1) \equiv 0 \pmod{q}$, there are $q$ possible values for $s(1)$ in the field $\mathbb{F}_q$.
  2. Exploiting the polynomial property: For a PLWE sample $(a, b)$, where $b = a \cdot s + e$ (with $e$ being the error term), the attacker evaluates this equation at 1: $b(1) = a(1) \cdot s(1) + e(1) \pmod{q}$.
  3. Distinguishing samples: If the attacker guesses $s(1)$ correctly, then $b(1) - a(1) \cdot s(1) = e(1)$. If the error distribution $\psi$ is such that $e(1)$ is likely to be "small" or non-uniform (e.g., from a Gaussian distribution with small variance), this difference will reveal the error term. For uniform samples, $b(1) - a(1) \cdot s(1)$ will remain uniformly distributed modulo $q$, regardless of the guess for $s(1)$.
  4. Attack complexity: This attack runs in time proportional to $O(q)$.

The paper also establishes theoretical reductions between different versions of the Ring-LWE problem (Search and Decision) and PLWE, under various conditions on the number field. These reductions help understand the relationship between the hardness of these problems.

Datasets

Not discussed in the paper. The paper focuses on theoretical attacks and reductions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Exploiting $f(1) \equiv 0 \pmod{q}$: The most crucial insight is that the condition $f(1) \equiv 0 \pmod{q}$ creates a "weakness" in PLWE instances. This condition allows for a direct attack by evaluating polynomials at 1, which is not possible when $f(1) \not\equiv 0 \pmod{q}$.
  • Attack Complexity $O(q)$: The developed attack has a time complexity of $O(q)$. This is significantly faster than generic lattice attacks (like those based on SVP or BDD) which often have exponential complexity in the dimension $n$, especially when $q$ is chosen to be large for security.
  • Generalization to other roots: The attack can be extended to other roots $\beta$ of $f(x)$ if $\beta$ has a small order in the multiplicative group $(\mathbb{Z}/q\mathbb{Z})^*$. This suggests that the weakness is not solely tied to the root 1.
  • Implications for parameter selection: The existence of this attack implies that number fields satisfying $f(1) \equiv 0 \pmod{q}$ are not suitable for constructing secure PLWE-based cryptosystems. This necessitates careful selection of number fields and moduli to avoid such weak instances.
  • Theoretical Reductions: The paper provides valuable theoretical reductions between R-LWE, R-DLWE, and PLWE, clarifying their relative hardness under specific conditions.

Key Results

  • A new attack on PLWE: The paper presents a novel attack that breaks PLWE instances in number fields $K$ where the defining polynomial $f(x)$ satisfies $f(1) \equiv 0 \pmod{q}$, with $q$ being the modulus.
  • Attack complexity: The attack runs in time $O(q)$. For typical cryptographic parameters where $q$ is large (e.g., $2^{128}$), this is still computationally infeasible for a direct attack. However, it is much faster than exponential-time lattice attacks and demonstrates a fundamental weakness for specific parameter choices.
  • Conditions for the attack: The attack is applicable when the number field $K$ satisfies certain properties, including $f(1) \equiv 0 \pmod{q}$, and $q$ can be chosen suitably large.
  • Theoretical reductions: The paper establishes search-to-decision reductions for R-LWE and R-DLWE, and a reduction from R-DLWE to PLWE under specific conditions on the number field.

Limitations and Future Work

  • Practicality of the $O(q)$ attack: While the $O(q)$ complexity is a theoretical breakthrough, for current high-security parameters where $q$ is very large (e.g., $2^{128}$), the attack is not directly practical. The paper notes that it is "far from a practical attack when $q$ is taken to be of size $2^{128}$".
  • Limited scope of the attack: The attack is specific to number fields satisfying $f(1) \equiv 0 \pmod{q}$ (or similar properties related to other roots). It does not break PLWE in general, particularly not in the commonly used cyclotomic fields where $f(1) \not\equiv 0 \pmod{q}$.
  • Need for specific number fields: The paper highlights that for practical cryptographic applications, it is advisable to stick to cyclotomic number fields until the class of fields for which reductions exist is enlarged.
  • Future Work: The authors suggest exploring extensions of the attack to more general number fields and investigating the conditions under which the theoretical reductions hold. They also point out that constructing a number field satisfying all six properties discussed in the paper would be a significant theoretical result, though not necessarily directly impacting current practical cryptosystems.

Summary updated

BibTeX
@article{eisentrager2014weak,
  author = {Kirsten Eisenträger and Sean Hallgren and Kristin E. Lauter},
  title = {{Weak Instances of PLWE}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2014},
}
Figure