Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?

Question

I am reading Peikert's paper [Pei16] about secure instantiating of R-LWE problem. In section 3.1, The author gives a new attack framework by using "reduction modulo an ideal divisor $\mathfrak{q}$ of the modulus $qR$". I'm a little new to Algebraic number theory and so I did not understand this framework especially the following part:

"Let $\mathfrak{q} ⊆ R$ be an ideal divisor of $qR$, having norm $N(\mathfrak{q}) := |R/\mathfrak{q}|$, and let $ψ$ be a continuous error distribution over $K_\mathbb{R}$. Given Ring-LWE samples $(a_i, b_i = s · a_i + e_i) \in R_q × K_\mathbb{R}/qR$ where $a_i ← R_q$ and $e_i ← ψ$, we can reduce them modulo $\mathfrak{q}$ to obtain samples $(a'_i = a_i \mod \mathfrak{q} , b'_i = b_i \mod \mathfrak{q}) \in R/{\mathfrak{q}} × K_\mathbb{R}/\mathfrak{q}$"

What "reduction modulo $\mathfrak{q}$" means? Can anyone help clarify things for me? Giving an example would be perfect.

Answer 1

Recall that any ideal $I$ of $R$ is in particular an additive subgroup of $R$, and that the quotient $R/I$ is the collection of cosets $a + I = \{a + i : i \in I\}$ for each $a \in R$. Two cosets $a+I, b+I$ are equal iff $a-b \in I$. The map that sends $a \in R$ to $a + I \in R/I$ is called "reduction modulo $I$," and often written "$a \bmod I$." The quotient $R/I$ is a ring via the induced ring operations from $R$ itself: $(a+I) + (b+I) = (a+b) + I$ and similarly for multiplication.

Now suppose we have some ideal divisor $J$ of $I$, i.e., $J \supseteq I$. The "natural" or "reduction mod $J$" homomorphism from $R/I$ to $R/J$ simply sends $a+I$ to $a+J$. This is well defined because if $a+I = b+I$, then $a+J=b+J$ because $a - b \in I \subseteq J$. (You can easily check that this is both an additive and multiplicative homomorphism.)

In the present setting, we have $I=qR$ and an ideal divisor $J = \mathfrak{q} \supseteq I$. For a Ring-LWE sample $(a_i, b_i = s \cdot a_i + e_i)$, we should view $a_i \in R/qR$ as the coset $a_i + qR$. Reducing it modulo $\mathfrak{q}$ just means sending it to the coset $a'_i = a_i + \mathfrak{q} \in R/\mathfrak{q}$. Similarly, we send the coset $b_i + qR$ to the coset \begin{equation} b'_i = b_i + \mathfrak{q} = (s \cdot a_i + e_i) + \mathfrak{q} = (s \cdot a'_i + e_i) + \mathfrak{q}. \end{equation} Note that the last equation holds because $s \in R$, $\mathfrak{q}$ is an ideal, and $(a_i - a'_i) = \mathfrak{q}$, so $s \cdot (a_i - a'_i) \subseteq \mathfrak{q}$.

The upshot of all this is that we can transform "mod $qR$" Ring-LWE samples $(a_i, b_i)$ into "mod $\mathfrak{q}$" samples $(a'_i, b'_i)$. However, as the paper notes, if the error distribution $\psi$ is very "smooth" modulo $\mathfrak{q}$---i.e., if $e + \mathfrak{q}$ is very close to uniform for $e \gets \psi$---then the resulting sample is useless: $(a'_i, b'_i)$ is just uniform junk, and it's impossible (information theoretically) to recover anything about $s$ from it.

Answer 2

Peikert's Method

The continuous error distribution over $K_\mathbb{R}$ denoted as $\psi$ is usually a Gaussian parameter that adds noise to $(a_i, b_i)$ which produces the equation:

$(a_i, b_i = s · a_i + e_i) \in R_q × K_\mathbb{R}/qR$

By analyzing $e_i ← ψ$ and $a_i ← R_q$ an attacker is able to derive:

$\lbrace a'_i = a_i \pmod{\mathfrak{q}} ,\ \ b'_i = b_i \pmod{\mathfrak{q}} \rbrace \ \in R/{\mathfrak{q}} × K_\mathbb{R}/\mathfrak{q}$

This is done by reducing the samples modulo q.

In section 2.2.4 Peikert states: "Any fractional ideal $I \subset K$ maps, via the canonical embedding σ, to a lattice $L = \sigma(I) \subset H$, which is called an ideal lattice." This then means that the ideal divisor, treated as a fractional ideal, maps to the ideal lattice.

By demonstrating that you can derive the variables $(a_i, b_i)$ from the Gaussian distribution, it's immediately apparent $\psi\pmod q$ is detectably non-uniform. This amounts to an attack that can separate the "noise" from the secret $s*a_i$ and $e_i$, which in turn means a bias is evident in the error distribution. This is a serious issue for R-LWE because the fundamental operation relies on non-bias in the error distribution. By using $\pmod q$ for poorly implemented R-LWE, an attack may succeed.

The norm of the ideal divisor is defined as $N(q):=|R/q|$, so if (as Peikert states) $N(q)$ is too small the decision form is weak. You simply look for any non-uniform $\hat s$ and accept if one exists. The second bullet point of the attacks in section 3.1 are similar in that an attacker focuses on errorless samples, which in turn are an attack against the statistically uniform distribution.

The third bullet point addresses solutions to both of the attacks by stating a proper implementation of a continuous Gaussian parameter mitigates the attacks. Essentially, if you've implemented it properly no attacker could distinguish between the error, or "noise" compared to $(a_i, b_i)$.

Modular Arithmetic

Reduction $\pmod q$ is defined by the rules of modular arithmetic. This is more or less straightforward in terms of addition, subtraction, and multiplication but a little more nuanced with division. Addition and multiplication are carried out by adding or multiplying as you normally would, but then dividing the result by $m$, with the remainder then being an element of that ring. Given integers $(a,b)$, they are congruent $\pmod m$ if their difference is divisible by $m$. This is expressed as: $a \equiv b \pmod m$. Any number that satisfies $a \equiv 0 \pmod m$ are the numbers divisible by $m$. This is relevant because the rings used in R-LWE are defined as some form of integer ring, and for any $\pmod q$ for prime $q$ the range is restricted to $(0,1,...q-1)$. Fermat's little theorem states that for a prime $q$ and an arbitrary integer $a$, then:

$a^{q-1} \equiv \bigg \lbrace \begin{matrix} 1 \pmod{q},\ q \nmid{a} \\ 0 \pmod{q},\ q \mid{a} \end{matrix}$

The notation $q \mid{a}$ is read as "q divides a" and equivalently, $q \nmid{a}$ is read as "q does not divide a."

Tying it Together

If I am able to calculate:

$a'_i = a_i \pmod \mathfrak{q} ,\\ b'_i = b_i \pmod \mathfrak{q}$

Using a reduction $\pmod q$, I'm effectively able to sift through the integers to pull apart the "noisy" errors from the private key $e_i$. Given Fermat's little theorem, an algorithm to return an accept value under the conditions Peikert outlines in the first bullet point would be more or less straightforward to implement. The reduction using modular arithmetic is how all operations are carried out with respect to the elements of the ring.

Examples

Examples for the decision version of R-LWE would be having to find the closest vector, which is hidden by "noise." If a bias is present, and $\psi$ is detectably non-uniform the CVP is much more straightforward because the noise is essentially removed from the problem.

An example of the search version of R-LWE would be finding the shortest non-zero vector given a basis, but again this becomes straightforward once the error is removed. You simply compare the lengths of the dual vectors, and this is as simple as comparing rows in a matrix which represent the coefficient vector of $e$.

An example outside of cryptography is a standard analog clock. The way we tell time uses modular arithmetic. If it's 3 p.m. and you tell someone you'll meet them in 11 hours, once you hit the number 12 you reduce the number so the actual time of the meeting is less than 12 (assuming you aren't using a 24 hour standard, in which case the time will always be less than or equal to 24).

Reduction $\pmod q$, in the methods Peikert outlines, is the difference between only knowing the hour of a meeting, and needing the exact time down to seconds. His attack based on poor implementations makes this problem easier. Instead of only having an hour, an alarm might as well go off when you return the ACCEPT for $\hat s$, because the value is detectably non-uniform. The same is true for the search form of R-LWE, you're essentially able to find the correct meeting time by reducing the numbers you sift through. So instead of comparing all possible times on the clock, you can reduce it to a smaller range (like comparing the dual vectors as rows in a matrix).