Short integer solution problem

Ideal lattice

Definition: Rotational shift operator on ${\displaystyle {\mathbb{R}}^n(n\ge 2)}$ is denoted by ${\displaystyle \mathrm{rot}}$, and is defined as:

${\displaystyle \mathrm{\forall }\mathit{x}=(x_1,\dots ,x_{n-1},x_n)\in {\mathbb{R}}^n:\mathrm{rot}(x_1,\dots ,x_{n-1},x_n)=(x_n,x_1,\dots ,x_{n-1})}$

Cyclic lattices

Micciancio introduced cyclic lattices in his work in generalizing the compact knapsack problem to arbitrary rings. A cyclic lattice is a lattice that is closed under rotational shift operator. Formally, cyclic lattices are defined as follows:

Definition: A lattice ${\displaystyle \mathfrak{L}\subseteq {\mathbb{Z}}^n}$ is cyclic if ${\displaystyle \mathrm{\forall }\mathit{x}\in \mathfrak{L}:\mathrm{rot}(\mathit{x})\in \mathfrak{L}}$.

Examples:

1. ${\displaystyle {\mathbb{Z}}^n}$ itself is a cyclic lattice.
2. Lattices corresponding to any ideal in the quotient polynomial ring ${\displaystyle R=\mathbb{Z}[x]/(x^n-1)}$ are cyclic:

consider the quotient polynomial ring ${\displaystyle R=\mathbb{Z}[x]/(x^n-1)}$, and let ${\displaystyle p(x)}$ be some polynomial in ${\displaystyle R}$, i.e. ${\displaystyle p(x)=\sum _{i=0}^{n-1}{a}_i{x}^i}$ where ${\displaystyle a_i\in \mathbb{Z}}$ for ${\displaystyle i=0,\dots ,n-1}$.

Define the embedding coefficient ${\displaystyle \mathbb{Z}}$-module isomorphism ${\displaystyle \rho }$ as:

${\displaystyle \begin{array}{cc}\rho :R& \to {\mathbb{Z}}^n\\ p(x)=\sum _{i=0}^{n-1}{a}_i{x}^i& \mapsto (a_0,\dots ,a_{n-1})\end{array}}$

Let ${\displaystyle I\subset R}$ be an ideal. The lattice corresponding to ideal ${\displaystyle I\subset R}$, denoted by ${\displaystyle {\mathfrak{L}}_I}$, is a sublattice of ${\displaystyle {\mathbb{Z}}^n}$, and is defined as

${\displaystyle {\mathfrak{L}}_I:=\rho (I)=\left\{(a_0,\dots ,a_{n-1})\mid \sum _{i=0}^{n-1}{a}_i{x}^i\in I\right\}\subset {\mathbb{Z}}^n.}$

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

proof: ${\displaystyle \Leftarrow )}$ We have:

${\displaystyle \mathfrak{L}={\mathfrak{L}}_I:=\rho (I)=\left\{(a_0,\dots ,a_{n-1})\mid \sum _{i=0}^{n-1}{a}_i{x}^i\in I\right\}}$

Let ${\displaystyle (a_0,\dots ,a_{n-1})}$ be an arbitrary element in ${\displaystyle \mathfrak{L}}$. Then, define ${\displaystyle p(x)=\sum _{i=0}^{n-1}{a}_i{x}^i\in I}$. But since ${\displaystyle I}$ is an ideal, we have ${\displaystyle xp(x)\in I}$. Then, ${\displaystyle \rho (xp(x))\in {\mathfrak{L}}_I}$. But, ${\displaystyle \rho (xp(x))=\mathrm{rot}(a_0,\dots ,a_{n-1})\in {\mathfrak{L}}_I}$. Hence, ${\displaystyle \mathfrak{L}}$ is cyclic.

${\displaystyle \Rightarrow )}$

Let ${\displaystyle \mathfrak{L}\subset {\mathbb{Z}}^n}$ be a cyclic lattice. Hence ${\displaystyle \mathrm{\forall }(a_0,\dots ,a_{n-1})\in \mathfrak{L}:\mathrm{rot}(a_0,\dots ,a_{n-1})\in \mathfrak{L}}$.

Define the set of polynomials ${\displaystyle I:=\left\{\sum _{i=0}^{n-1}{a}_i{x}^i\mid (a_0,\dots ,a_{n-1})\in \mathfrak{L}\right\}}$:

1. Since ${\displaystyle \mathfrak{L}}$ a lattice and hence an additive subgroup of ${\displaystyle {\mathbb{Z}}^n}$, ${\displaystyle I\subset R}$ is an additive subgroup of ${\displaystyle R}$.
2. Since ${\displaystyle \mathfrak{L}}$ is cyclic, ${\displaystyle \mathrm{\forall }p(x)\in I:xp(x)\in I}$.

Hence, ${\displaystyle I\subset R}$ is an ideal, and consequently, ${\displaystyle \mathfrak{L}={\mathfrak{L}}_I}$.

Ideal lattices[4]

Let ${\displaystyle f(x)\in \mathbb{Z}[x]}$ be a monic polynomial of degree ${\displaystyle n}$. For cryptographic applications, ${\displaystyle f(x)}$ is usually selected to be irreducible. The ideal generated by ${\displaystyle f(x)}$ is:

${\displaystyle (f(x)):=f(x)\cdot \mathbb{Z}[x]=\{f(x)g(x):\mathrm{\forall }g(x)\in \mathbb{Z}[x]\}.}$

The quotient polynomial ring ${\displaystyle R=\mathbb{Z}[x]/(f(x))}$ partitions ${\displaystyle \mathbb{Z}[x]}$ into equivalence classes of polynomials of degree at most ${\displaystyle n-1}$:

${\displaystyle R=\mathbb{Z}[x]/(f(x))=\left\{\sum _{i=0}^{n-1}{a}_i{x}^i:a_i\in \mathbb{Z}\right\}}$

where addition and multiplication are reduced modulo ${\displaystyle f(x)}$.

Consider the embedding coefficient ${\displaystyle \mathbb{Z}}$-module isomorphism ${\displaystyle \rho }$. Then, each ideal in ${\displaystyle R}$ defines a sublattice of ${\displaystyle {\mathbb{Z}}^n}$ called ideal lattice.

Definition: ${\displaystyle {\mathfrak{L}}_I}$, the lattice corresponding to an ideal ${\displaystyle I}$, is called ideal lattice. More precisely, consider a quotient polynomial ring ${\displaystyle R=\mathbb{Z}[x]/(p(x))}$, where ${\displaystyle (p(x))}$ is the ideal generated by a degree ${\displaystyle n}$ polynomial ${\displaystyle p(x)\in \mathbb{Z}[x]}$. ${\displaystyle {\mathfrak{L}}_I}$, is a sublattice of ${\displaystyle {\mathbb{Z}}^n}$, and is defined as:

${\displaystyle {\mathfrak{L}}_I:=\rho (I)=\left\{(a_0,\dots ,a_{n-1})\mid \sum _{i=0}^{n-1}{a}_i{x}^i\in I\right\}\subset {\mathbb{Z}}^n.}$

Remark:

1. It turns out that ${\displaystyle {\text{GapSVP}}_{\gamma }}$ for even small ${\displaystyle \gamma =\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\mathrm{n})}$ is typically easy on ideal lattices. The intuition is that the algebraic symmetries causes the minimum distance of an ideal to lie within a narrow, easily computable range.
2. By exploiting the provided algebraic symmetries in ideal lattices, one can convert a short nonzero vector into ${\displaystyle n}$ linearly independent ones of (nearly) the same length. Therefore, on ideal lattices, ${\displaystyle {\mathrm{S}\mathrm{V}\mathrm{P}}_{\gamma }}$ and ${\displaystyle {\mathrm{S}\mathrm{I}\mathrm{V}\mathrm{P}}_{\gamma }}$ are equivalent with a small loss. Furthermore, even for quantum algorithms, ${\displaystyle {\mathrm{S}\mathrm{V}\mathrm{P}}_{\gamma }}$ and ${\displaystyle {\mathrm{S}\mathrm{I}\mathrm{V}\mathrm{P}}_{\gamma }}$ are believed to be very hard in the worst-case scenario.

Short integer solution problem

The Short Integer Solution (SIS) problem is an average case problem that is used in lattice-based cryptography constructions. Lattice-based cryptography began in 1996 from a seminal work by Ajtai who presented a family of one-way functions based on the SIS problem. He showed that it is secure in an average case if ${\displaystyle {\mathrm{S}\mathrm{V}\mathrm{P}}_{\gamma }}$ (where ${\displaystyle \gamma =n^c}$ for some constant ${\displaystyle c>0}$) is hard in a worst-case scenario. Along with applications in classical cryptography, the SIS problem and its variants are utilized in several post-quantum security schemes including CRYSTALS-Dilithium and Falcon.

SISq,n,m,β

Let ${\displaystyle A\in {\mathbb{Z}}_q^{n\times m}}$ be an ${\displaystyle n\times m}$ matrix with entries in ${\displaystyle {\mathbb{Z}}_q}$ that consists of ${\displaystyle m}$ uniformly random vectors ${\displaystyle {\mathit{a}}_{\mathit{i}}\in {\mathbb{Z}}_q^n}$: ${\displaystyle A=[{\mathit{a}}_{\mathbf{1}}|\cdots |{\mathit{a}}_{\mathit{m}}]}$. Find a nonzero vector ${\displaystyle \mathit{x}\in {\mathbb{Z}}^m}$ such that for some norm ${\displaystyle \Vert \cdot \Vert }$:

• ${\displaystyle 0<\Vert \mathit{x}\Vert \le \beta }$,
• ${\displaystyle f_A(\mathit{x}):=A\mathit{x}=\mathbf{0}\in {\mathbb{Z}}_q^n}$.

A solution to SIS without the required constraint on the length of the solution (${\displaystyle \Vert \mathit{x}\Vert \le \beta }$) is easy to compute by using Gaussian elimination technique. We also require ${\displaystyle \beta <q}$, otherwise ${\displaystyle \mathit{x}=(q,0,\dots ,0)\in {\mathbb{Z}}^m}$ is a trivial solution.

In order to guarantee ${\displaystyle f_A(\mathit{x})}$ has non-trivial, short solution, we require:

• ${\displaystyle \beta \ge \sqrt{n\log q}}$, and
• ${\displaystyle m\ge n\log q}$

Theorem: For any ${\displaystyle m=\mathrm{poly}(n)}$, any ${\displaystyle \beta >0}$, and any sufficiently large ${\displaystyle q\ge \beta n^c}$ (for any constant ${\displaystyle c>0}$), solving ${\displaystyle {\mathrm{SIS}}_{n,m,q,\beta }}$ with nonnegligible probability is at least as hard as solving the ${\displaystyle {\mathrm{GapSVP}}_{\gamma }}$ and ${\displaystyle {\mathrm{SIVP}}_{\gamma }}$ for some ${\displaystyle \gamma =\beta \cdot O(\sqrt{n})}$ with a high probability in the worst-case scenario.

R-SISq,n,m,β

The SIS problem solved over an ideal ring is also called the Ring-SIS or R-SIS problem. This problem considers a quotient polynomial ring ${\displaystyle R_q={\mathbb{Z}}_q[x]/(f(x))}$ with ${\displaystyle f(x)=x^n-1}$ for some integer ${\displaystyle n}$ and with some norm ${\displaystyle \Vert \cdot \Vert }$. Of particular interest are cases where there exists integer ${\displaystyle k}$ such that ${\displaystyle n=2^k}$ as this restricts the quotient to cyclotomic polynomials.

We then define the problem as follows:

Select ${\displaystyle m}$ independent uniformly random elements ${\displaystyle a_i\in R_q}$. Define vector ${\displaystyle \overrightarrow{\mathit{a}}:=(a_1,\dots ,a_m)\in R_q^m}$. Find a nonzero vector ${\displaystyle \overrightarrow{\mathit{z}}:=(z_1,\dots ,z_m)\in R^m}$ such that:

• ${\displaystyle 0<\Vert \overrightarrow{\mathit{z}}\Vert \le \beta }$,
• ${\displaystyle f_{\overrightarrow{\mathit{a}}}(\overrightarrow{\mathit{z}}):={\overrightarrow{\mathit{a}}}^T.\overrightarrow{\mathit{z}}=\sum _{i=1}^m{a}_i.z_i=0\in R_q}$.

Recall that to guarantee existence of a solution to SIS problem, we require ${\displaystyle m\approx n\log q}$. However, Ring-SIS problem provide us with more compactness and efficacy: to guarantee existence of a solution to Ring-SIS problem, we require ${\displaystyle m\approx \log q}$ .

Definition: The nega-circulant matrix of ${\displaystyle b}$ is defined as:

${\displaystyle \text{for}b=\sum _{i=0}^{n-1}{b}_i{x}^i\in R,\mathrm{rot}(b):=\left[\begin{array}{cccc}{b}_0& -b_{n-1}& \dots & -b_1\\ b_1& b_0& \dots & -b_2\\ ⋮& ⋮& \ddots & ⋮\\ b_{n-1}& b_{n-2}& \dots & b_0\end{array}\right]}$

When the quotient polynomial ring is ${\displaystyle R=\mathbb{Z}[x]/(x^n+1)}$ for ${\displaystyle n=2^k}$, the ring multiplication ${\displaystyle a_i.p_i}$ can be efficiently computed by first forming ${\displaystyle \mathrm{rot}(a_i)}$, the nega-circulant matrix of ${\displaystyle a_i}$, and then multiplying ${\displaystyle \mathrm{rot}(a_i)}$ with ${\displaystyle \rho (p_i(x))\in Z^n}$, the embedding coefficient vector of ${\displaystyle p_i}$ (or, alternatively with ${\displaystyle \sigma (p_i(x))\in Z^n}$, the canonical coefficient vector.

Moreover, R-SIS problem is a special case of SIS problem where the matrix ${\displaystyle A}$ in the SIS problem is restricted to negacirculant blocks: ${\displaystyle A=[\mathrm{rot}(a_1)|\cdots |\mathrm{rot}(a_m)]}$.

M-SISq,n,d,m,β

The SIS problem solved over a module lattice is also called the Module-SIS or M-SIS problem. Like R-SIS, this problem considers the quotient polynomial ring ${\displaystyle R=\mathbb{Z}[x]/(f(x))}$ and ${\displaystyle R_q={\mathbb{Z}}_q[x]/(f(x))}$ for ${\displaystyle f(x)=x^n-1}$ with a special interest in cases where ${\displaystyle n}$ is a power of 2. Then, let ${\displaystyle M}$ be a module of rank ${\displaystyle d}$ such that ${\displaystyle M\subseteq R^d}$ and let ${\displaystyle \Vert \cdot \Vert }$ be an arbitrary norm over ${\displaystyle R_q^m}$.

We then define the problem as follows:

Select ${\displaystyle m}$ independent uniformly random elements ${\displaystyle a_i\in R_q^d}$. Define vector ${\displaystyle \overrightarrow{\mathit{a}}:=(a_1,\dots ,a_m)\in R_q^{d\times m}}$. Find a nonzero vector ${\displaystyle \overrightarrow{\mathit{z}}:=(z_1,\dots ,z_m)\in R^m}$ such that:

• ${\displaystyle 0<\Vert \overrightarrow{\mathit{z}}\Vert \le \beta }$,
• ${\displaystyle f_{\overrightarrow{\mathit{a}}}(\overrightarrow{\mathit{z}}):={\overrightarrow{\mathit{a}}}^T.\overrightarrow{\mathit{z}}=\sum _{i=1}^m{a}_i.z_i=0\in R_q^d}$.

While M-SIS is a less compact variant of SIS than R-SIS, the M-SIS problem is asymptotically at least as hard as R-SIS and therefore gives a tighter bound on the hardness assumption of SIS. This makes assuming the hardness of M-SIS a safer, but less efficient underlying assumption when compared to R-SIS.