Ring-SIS, Ideal lattices, and Ring-LWE

Following the MIT notes here (opens new window).

Some notation first: $\lceil x \rceil$ means rounding up, $\lfloor x \rfloor$ means rounding down, $\lfloor x \rceil$ means the nearest integer,

The problem with $h_A$ over $\mathbb{Z}[x]/(x^n-1)$, as defined previously, was that the polynomial $x^n - 1$ is not irreducible.

We might try using $x^n + 1$ instead.

The following holds: $x^n + 1$ is irreducible over $\mathbb{Z}$ if and only if $n$ is a power of $2$. For some intuition, if $n$ is divisible by an odd positive integer $d$, then $x^n + 1$ is divisible by $x^{\frac{n}{d}} + 1$.

So, we take $\mathbb{Z}[x]/(x^n+1)$, where $n$ is some power of $2$.

In this case, we have

$Rot(a_i) = (a_i, Xa_i, X^{n-1}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}$

and

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

Note that $X$ differs in just one entry from last time. Matrices of the form $Rot(a)$, as above, are sometimes called anti-cyclic or negacyclic.

If we have polynomials $a = a_0 + a_1 x + ... + a_{n-1} x^{n-1}$ and $b = b_0 + b_1 x + ... + b_{n-1} x^{n-1}$, the multiplication $a b$ can be obtained by a matrix-vector product:

$a(x) b(x) = Rot(a) [b_0 b_1 ... b_{n-1}]^T$

Let’s consider the multiplication of the following two polynomials:

$a = a_0 + a_1 x + a_2 x^2$

$b = b_0 + b_1 x + b_2 x^2$

In this case, we have $n = 3$ (though in reality, we would need $n$ to be a power of $2$), so $x^3 = -1.$

For the sake of brevity (or perhaps out of laziness), let’s focus only on the constant coefficient.

$Rot(a) b = \begin{pmatrix} a_0 & -a_2 & -a_1 \\ a_1 & a_0 & -a_2 \\ a_2 & a_1 & a_0 \end{pmatrix} \begin{pmatrix} b_0 \\ b_1 \\ b_2 \end{pmatrix}$

$= \begin{pmatrix} a_0 b_0 -a_2 b_1 -a_1 b_2 \\ ... \\ ... \end{pmatrix}$

We will see below that we obtain the same result when multiplying $a(x)$ and $b(x)$. Again, I am ignoring the non-constant coefficients (represented by three dots).

$a(x) b(x) = a_0 b_0 + a_2 b_1 x^3 + a_1 b_2 x^3 + ... = a_0 b_0 - a_2 b_1 - a_1 b_2 + ...$

Now, let’s consider the SIS problem defined by the following matrix:

$A = \begin{pmatrix} a_0 & -a_2 & -a_1 & b_0 & -b_2 & -b_1 \\ a_1 & a_0 & -a_2 & b_1 & b_0 & -b_2 \\ a_2 & a_1 & a_0 & b_2 & b_1 & b_0 \\ c_0 & -c_2 & -c_1 & d_0 & -d_2 & -d_1 \\ c_1 & c_0 & -c_2 & d_1 & d_0 & -d_2 \\ c_2 & c_1 & c_0 & d_2 & d_1 & d_0 \end{pmatrix}$

The matrix $A \in \mathbb{Z}^{6 \times 6}_q$ has some structure—the blocks are negacylic matrices. The strange thing is (at least to me) that the SIS problem is not easier due to this structure; it is still difficult to find a short vector $s$ such that:

$As = 0 \; mod \; q$

But we can think of $A$ as follows:

$a(x) = a_0 + a_1 x + a_2 x^2$

$b(x) = b_0 + b_1 x + b_2 x^2$

$c(x) = c_0 + c_1 x + c_2 x^2$

$d(x) = d_0 + d_1 x + d_2 x^2$

$A = \begin{pmatrix} Rot(a) & Rot(b) \\ Rot(c) & Rot(d) \end{pmatrix}$

To store $A$, we only need $4$ polynomials—specifically, 3 elements from $\mathbb{Z}_q$ for each block (instead of $9$ with an unstructured matrix).

But that’s not all; we can also apply a much faster algorithm for the multiplication.

$\begin{pmatrix} a_0 & -a_2 & -a_1 & b_0 & -b_2 & -b_1 \\ a_1 & a_0 & -a_2 & b_1 & b_0 & -b_2 \\ a_2 & a_1 & a_0 & b_2 & b_1 & b_0 \\ c_0 & -c_2 & -c_1 & d_0 & -d_2 & -d_1 \\ c_1 & c_0 & -c_2 & d_1 & d_0 & -d_2 \\ c_2 & c_1 & c_0 & d_2 & d_1 & d_0 \end{pmatrix} \begin{pmatrix} e_0 \\ e_1 \\ e_2 \\ f_0 \\ f_1 \\ f_2 \end{pmatrix}$

When we, for example, multiply $Rot(a) e(x)$, where $e(x) = e_0 + e_1 x + e_2 x^2$, we are actually multiplying $a(x) e(x)$, and we can use the NTT for this, which means $O(nlog(n))$ operations instead of $O(n^2).$

Hash function

The hash function is again defined:

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

where $mod \; qR$ means reducing the coefficients of the result of the polynomial multiplication modulo $q$.

As in the previous case, finding a collision for this hash function is equivalent to solving Ring-SIS, now over this new ring, $R = \mathbb{Z}[x]/(x^n + 1)$. It turns out, Ring-SIS is in fact hard over this ring, under a reasonable worst-case complexity assumption.

Ideal lattices

An ideal $I \subset R$ is an additive subgroup of a ring $R$ that is closed under multiplication by any element of the ring.

We can view $I$ as a lattice by embedding $R$ in $\mathbb{Z}^n$ via the trivial embedding that maps $x^i$ to the unit vector $e_i$.

So, $I$ can be viewed as a lattice in $\mathbb{Z}^n$ that is invariant under the linear transformation $X$. This means $I \subset \mathbb{Z}^n$ is a lattice such that $(y_1, ..., y_n)^T \in I$ if and only if $(-y_n, y_1, ..., y_{n-1})^T \in I$.

Let’s now take a look at successive minima:

Definition: Let $L$ be a lattice of rank $n$. The successive minima of $L$ are $\lambda_1$,...,$\lambda_n$ such that, for $1 \leq i \leq n$, $\lambda_i$ is minimal such that there exist $i$ linearly independent vectors $v_1$,...,$v_i \in L$ with $||v_j|| \leq \lambda_i$ for $1 \leq j \leq i$.

The embedding of $I$ into $\mathbb{Z}^n$ allows us to consider the geometry of an ideal $I$. We can define the $l_2$ norm. Non-zero lattice elements $y \in I$ can be divided into groups of $n$ linearly independent vectors $y, xy, x^2 y, ..., x^{n-1}y$, all with the same length, $||x^i y|| = ||x^j y||$. Thus, it also holds: $\lambda_1(I) = \lambda_n(I)$.

Definition: For a ring $R$ (with an associated norm $||\cdot||$) and approximation factor $\gamma \geq 1$, $\gamma$-IdealSVP over $R$ is the approximate search problem defined as follows. The input is (a basis for) an ideal lattice $I$ over $R$. The goal is to output a non-zero element $y \in I$ with $||y|| \leq \gamma \lambda_1(I)||$.

Peikert and Rosen, and independently Lyubashevsky and Micciancio, proved the following result:

Theorem: For $n$ any power of $2$, integer $l \geq 1$, and integer modulus $q \geq 2n^2 l$, $\gamma$-Ideal SVP over $R = \mathbb{Z}[x]/(x^n+1)$ can be efficiently reduced to Ring-SIS over $R$, where $\gamma = l \cdot poly(n)$.

Ring-LWE

We continue taking notes from an MIT lecture (opens new window).

Theorem: For integers $l, q \geq 2$, for $n$ power of $2$, and an error distribution $\chi$ over short elements in $R$, the (average-case, search) Ring-LWE problem is defined as follows. The input is $a_1,..,a_n \in R_q$ sampled independently and uniformly at random together with $b_1,...,b_n \in R_q$, where $b_i := a_i s + e_i \; mod \; qR$ for $s \in R_q$, and $e_i \sim \chi$. The goal is to output $s$.

Let’s take a look at the example of public key encryption based on Ring-LWE.

The secret key is a short secret $s \sim \chi$ (short usually means it’s from $R_{\{-1, 0, 1\}})$. The public key is $(\hat{a}, y)$, where $\hat{a} \in R_q$ is chosen uniformly at random, and $y := \hat{a} s + e \; mod ; qR$, where $e \sim \chi$.

To encrypt $m \in R_q$, compute

$(a, b) = (\hat{a} r + x \; mod \; q, yr + x' + \lfloor q/2 \rceil m \; mod \; q)$

for $r, x, x' \sim \chi$.

To decrypt $(a, b)$, compute $b - a s \; mod \; qR = \lfloor q/2 \rceil m + er + x' - xs \; mod \; q$. Round each coefficient to either $q/2$ or $0$, whichever is closest, and interpret $0$ as $0$ and $q/2$ as $1$.

Note that in LWE-encryption, only one bit is encrypted at a time.