SIS, LWE, Ring-SIS

What’s the difference between Learning With Errors (LWE) and Ring Learning With Errors(RLWE)? Well, for this, one first needs to know what are ideal lattices.

Ideal lattices are a generalization of cyclic lattices. And what are cyclic lattices?

First, we define the rotational shift operator $rot$ on $\mathbb{R}^n$ ($n \ge 2$):

$rot(x_1, ..., x_{n-1}, x_n) = (x_n, x_1, ..., x_{n-1})$

A cyclic lattice is a lattice that is closed under the rotation shift operator. For example, $\mathbb{Z}^n$ is a cyclic lattice.

Let’s now observe the ring $\mathbb{Z}[x]/(x^n-1)$.

First of all, if we take the polynomials in $\mathbb{Z}[x]$ up to some degree, let’s say $n$, we can view these polynomials as points in $\mathbb{Z}^n$, simply by viewing, for example, $a_0 + a_1 x + a_2 x^2$ as $(a_0, a_1, a_2)$. Now, the problem is that when we multiply two polynomials, we can end up with the polynomial that is of degree greater than $n$.

For example, let’s have $n = 2$ and polynomials $a = a_0 + a_1 x$, $b = b_0 + b_1 x$. We can see $a$ as $(a_0, a_1)$ and $b$ as $(b_0, b_1)$.

However, we have:

$a b = a_0 b_0 + (a_1 b_0 + a_0 b_1) x + a_1 b_1 x^2$

We would need three coordinates for $a b = (a_0 b_0, a_1 b_0 + a_0 b_1, a_1 b_1)$.

It would be nice if we could stay within two coordinates. So, we take $R = \mathbb{Z}[x]/(x^2-1)$. Now, in $R$, we have $x^2 - 1 = 0$, which means $x^2 = 1$. This allows us to always replace $x^2$ by $1$, ensuring that we never get a polynomial of degree greater than $1$.

So, our vector $ab$ is actually:

$a b = a_0 b_0 + (a_1 b_0 + a_0 b_1) x + a_1 b_1 x^2 = a_0 b_0 + (a_1 b_0 + a_0 b_1) x + a_1 b_1 =$

$= (a_0 b_0 + a_1 b_1) + (a_1 b_0 + a_0 b_1) x$

In lattice-based cryptograpy, we operate in the ring $R = \mathbb{Z}[x]/(x^n-1)$. Let’s consider an ideal $I \subset R$. The lattice that corresponds to $I$ (by viewing the $R$ elements as points in $\mathbb{Z}^n$, as described earlier) is called an ideal lattice. It is a sublattice of $\mathbb{Z}^n$.

It holds:

Theorem: The lattice $L \subset \mathbb{Z}^n$ is cyclic if and only if it corresponds to some ideal $I$ in the quotient polynomial ring $R = \mathbb{Z}[x]/(x^n-1)$.

The theorem can be quickly proved (see Wikipedia (opens new window)) by observing that the rotational shift operator is the same as multiplying by $x$ in $\mathbb{Z}[x]/(x^n-1)$.

Let’s have (I am abusing the equal sign operator a bit):

$(a_0, ..., a_{n-2}, a_{n-1}) = a_0 + ... + a_{n-2} x^{n-2} + a_{n-1} x^{n-1}$

Then:

$rot((a_0, ..., a_{n-2}, a_{n-1})) = (a_{n-1}, a_0, ..., a_{n-2})) =$

$= a_{n-1} + a_0 x + ... + a_{n-2} x^{n-2}$

$= x(a_0 + ... + a_{n-2} x^{n-2} + a_{n-1} x^{n-1})$

Learning With Errors (LWE)

The LWE problem was introduced by Oded Regev in 2005, and it asks to solve a system of noisy linear equations. That is, to find $s \in \mathbb{Z}^n_q$ given:

$\{(a_i, y = <a_i, s> + e_i); s \in \mathbb{Z}^n_q, a_i \in \mathbb{Z}^n_q, e_i \in \mathbb{Z} \}^m_{i=1}$

We could also write:

$A s + e = y \; mod \; q$

where $A \in \mathbb{Z}^{m \times n}_q$ and $e \in \mathbb{Z}^n_q$.

Short Integer Solution (SIS) problem

The system of linear equations

$Ax = b \; mod \; q$

where $A \in \mathbb{Z}^{m \times n}_q$ and $b \in \mathbb{Z}^n_q$ can be solved in polynomial time with Gaussian elimination. However, variations of this problem can be hard. For example, when we require that the norm of $x$ is smaller than some bound $B$. Note that the bound needs to be smaller than $q$; otherwise, $(q, 0, ..., 0)$ is a trivial solution.

The SIS problem $SIS(m, n, q, B)$ is the problem of finding $x = (x_1, ..., x_n)$ such that $|x_i| \leq B$.

MIT notes (opens new window) say the solutions are very likely to exist if $(2B + 1)^m >>q^n$. If not, we first pick a $B$-bounded vector $e$ and compute $b = Ae \; mod \; q$. We "plant" the solution $e$ inside $b$ (this is called the planted regime or the LWE regime).

The SIS and LWE problems are related.

Let’s say we have a matrix $C$ such that $C A = 0 \; mod \; q$. We are solving

$A s + e = y \; mod \; q$

$C(A s + e) = C y \; mod \; q$

$C e = C y \; mod \; q$

which is a SIS problem.

Example of public-key cryptosystem based on LWE

Let’s have a secret key $s \in \mathbb{Z}^n_q$ and a public key $(a_i, b_i = \frac{<a_i, s>}{q} + e_i)^m_{i=1}$.

The encryption of a bit $x$ goes as follows. Let’s choose a subset $S \subset [m]$ and compute the ciphertext:

$c = (a, b) = (\sum_{i \in S} a_i, \frac{x}{2} + \sum_{i \in S} b_i)$

The decryption of $c$ is $0$ if $b - \frac{<a, s>}{q}$ is closer to $0$ than to $\frac{1}{2}$, and $1$ otherwise.

Just for intuition, let’s have $S = \{1, 2\}$. Then

$c = (a, b) = (a_1 + a_2, x/2 + \frac{<a_1, s>}{q} + \frac{<a_2, s>}{q})$

And we have:

$(b - \frac{<a, s>}{q}) = \frac{x}{2}$

Hash function based on SIS

Let’s have $A \in \mathbb{Z}^{n \times m}_q$ and $e \in [0, B]^m$. We define

$h_A(e) = Ae \; mod \; q$

Can we find a collision? It’s difficult, because

$h_A(e_1) = h_A(e_2)$

means

$Ae_1 - Ae_2 = A(e_1 - e_2) = 0$

and because $(e_1 - e_2) \in [-B, B]^m$ this means a solution to the SIS problem.

However, as simple as this hash function is, it is also inefficient—just reading the matrix requires a time of $n^2$.

How to make hash function faster

This is where ideal lattices come into play. The idea is to only have matrices which enable very fast multiplication.

So let’s have $A \in \mathbb{Z}^{n \times m}_q$ where $m > n$ (to have a compression function), and let’s have $n | m$, let’s denote $l = \frac{m}{n}$. Let’s see $A$ as a tuple of matrices: $A = (A_1, ..., A_l)$.

Let’s have $e \in \{-1, 0, 1\}^m$. Let’s see $e$ as an $l$-tuple $(e_1, ..., e_l)$.

The operation $A e$ is now:

$h_A(e) = (A_1, ..., A_l) (e_1, ..., e_l)^T$

We will take $A_i$ of special form to have fast multiplication. Let’s have vectors $a_1, ..., a_l$ where $a_i = (a_{i,1}, ..., a_{i,n})$.

We define

$Rot(a_i) = \begin{pmatrix} a_{i,1} & a_{i, n} & ... & a_{i,2} \\ a_{i,2} & a_{i, 1} & ... & a_{i,3} \\ ... & ... & ... & ... \\ a_{i,n-1} & a_{i,n-2} & ... & a_{i,n} \\ a_{i,n} & a_{i,n-1} & ... & a_{i,1} \end{pmatrix}$

Let’s define

$X = \begin{pmatrix} 0 & 0 & ... & 0 & 1 \\ 1 & 0 & ... & 0 & 0 \\ 0 & 1 & ... & 0 & 0 \\ ... & ... & ... & 0 & 0 \\ 0 & 0 & ... & 1 & 0 \end{pmatrix}$

It holds:

$Rot(a_i) = (a_i, X a_i, X^2 a_i, X^{n-1} a_i)$

But also:

$Rot(a_i) = a_{i,1} I_n + a_{i,2} X + ... + a_{i,n} X^{n-1}$

We can see that $\tilde{R} := \{Rot(a); a \in \mathbb{Z}^n \}$ is isomorphic to $R = \mathbb{Z}[x]/(x^n - 1)$.

So instead of multiplying the matrices from $\mathbb{Z}^{n \times n}_q$, we can move into $R_{[q]}$ and multiply polynomials via fast Fourier transform.

So above we had:

$h_A(e) = (Rot(a_1), ..., Rot(a_l)) (e_1, ..., e_l)^T \; mod \; q$

And thus:

$h_A(e) = Rot(a_1) e_1 + ... + Rot(a_l) e_l \; mod \; q$

But wait! We haven’t moved to $\tilde R$ fully, we have matrix-vector multiplication, this is not in $\tilde R$. We should have something like:

$h_A(e) = Rot(a_1) Rot(e_1) + ... + Rot(a_l) Rot(e_l) \; mod \; q$

Which would mean:

$h_A(e) = a_1 e_1 + ... + a_l e_l \; mod \; qR$

However, this is ok since:

$Rot(a) Rot(e) = Rot(Rot(a) e)$

Why is this so? Let’s have two vectors $x = (x_1, ..., x_n)$. It’s enough to show:

$X Rot(x) e = Rot(x) X e$

This is clear from below:

$X Rot(x) e = X (x_1 I_n + x_2 X ... + x_n X^{n-1}) e$

$Rot(x) X e = (x_1 I_n + x_2 X ... + x_n X^{n-1}) X e$

I haven’t read the paper, but MIT lecture (opens new window) says Miccancio showed in 2007 that such hash function is a secure one-way function (difficult to invert).

However, it is not a collision-resistant hash function. Before having a look what’s the reason let’s see the definition of Ring-SIS problem.

Definition: For a ring $R$, integer modulus $Q \geq 2$, and integer $l \geq 1$, the (average-case) Ring-SIS problem is defined as follows. The input is $a_1,...,a_l \in R_{[q]}$ sampled independently and uniformly at random. The goal is to output $e_1, ..., e_l \in R_{\{-1, 0, 1\}}$ not all zero such that $a_1 e_1 + ... + a_l e_l = 0 \; mod \; qR$.

However, Ring-SIS over $\mathbb{Z}[x]/(x^n-1)$ is not hard.

It holds:

$x^n - 1 = (x - 1) (x^{n-1} + ... + x + 1)$

Let’s denote $\tilde{e} = x^{n-1} + ... + x + 1$.

We can see that $(\tilde{e}, 0, ..., 0)$ is a solution to Ring-SIS problem whenever $a_1$ is divisible by $x-1$. The probability that $a_1$ is divisible by $x-1$ is $\frac{1}{q}$ (whenever $a_1(1) = 0 \; mod \; q$).