Short integer solution problem

Short integer solution (SIS) and ring-SIS problems are two average-case problems that are used in lattice-based cryptography constructions. Lattice-based cryptography began in 1996 from a seminal work by Ajtai ^[1] who presented a family of one-way functions based on SIS problem. He showed that it is secure in average case if ${\displaystyle \mathrm {SVP} _{\gamma }}$ (where ${\displaystyle \gamma =n^{c}}$ for some constant $c>0$) is hard in worse case scenario.

Average case problems are the problems that are hard to be solved for some randomly selected instances. It should be noted that for cryptography applications, worse case complexity is not sufficient, and we need to guarantee cryptographic construction are hard based on average case complexity.

Lattices

A full rank lattice ${\displaystyle {\mathfrak {L}}\subset \mathbb {R} ^{n}}$ is a set of integer linear combinations of $n$ linearly independent vectors ${\displaystyle \{b_{1},\ldots ,b_{n}\}}$, named basis:

${\displaystyle {\mathfrak {L}}(b_{1},\ldots ,b_{n})=\left\{\sum _{i=1}^{n}z_{i}b_{i}:z_{i}\in \mathbb {Z} \right\}=\{B{\boldsymbol {z}}:{\boldsymbol {z}}\in \mathbb {Z} ^{n}\}}$

where ${\displaystyle B\in \mathbb {R} ^{n\times n}}$ is a matrix having basis vectors in its columns.

Remark: Given ${\displaystyle B_{1},B_{2}}$ two bases for lattice ${\displaystyle {\mathfrak {L}}}$, there exist unimodular matrices ${\displaystyle U_{1}}$ such that ${\displaystyle B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1}}$.

Ideal lattice

Definition: Rotational shift operator on ${\displaystyle \mathbb {R} ^{n}(n\geq 2)}$ is denoted by ${\displaystyle \operatorname {rot} }$, and is defined as: ${\displaystyle \forall {\boldsymbol {x}}=(x_{1},\ldots ,x_{n-1},x_{n})\in \mathbb {R} ^{n}:\operatorname {rot} (x_{1},\ldots ,x_{n-1},x_{n})=(x_{n},x_{1},\ldots ,x_{n-1})}$

Cyclic lattices

Micciancio introduced cyclic lattices in his work in generalizing the compact knapsack problem to arbitrary rings.^[2] 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}}\in \mathbb {Z} ^{n}}$ is cyclic if ${\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}}$.

Examples: ^[3]

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 $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,\ldots ,n-1}$.

Define the embedding coefficient $\Z$-module isomorphism $\rho$ as:

${\displaystyle {\begin{aligned}\quad \rho :R&\rightarrow \mathbb {Z} ^{n}\\[4pt]p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned}}}$

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},\ldots ,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 $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},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}}$

Let ${\displaystyle (a_{0},\ldots ,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 $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))=\operatorname {rot} (a_{0},\ldots ,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 \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,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},\ldots ,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 $R$.
2. Since ${\displaystyle {\mathfrak {L}}}$ is cyclic, ${\displaystyle \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 latices ^[4][5]

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

${\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\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 $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 $f(x)$.

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

Definition: ${\displaystyle {\mathfrak {L}}_{I}}$, the lattice corresponding to an ideal $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 $n$ polynomial ${\displaystyle p(x)\in \mathbb {Z} [x]}$. ${\displaystyle {\mathfrak {L}}_{I}}$, is a sublattice of $\mathbb{Z } ^{n}$, and is defined as:

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

Rremark:^[6]

1. It turns out that ${\displaystyle {\text{GapSVP}}_{\gamma }}$ for even small ${\displaystyle \gamma =\operatorname {poly(n)} }$ is typically easy on ideal lattices. The intuition is that the algebraic symmetries results 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 $n$ linearly independent ones of (nearly) the same length. Therefore, on ideal lattices, ${\displaystyle \mathrm {SVP} _{\gamma }}$ and ${\displaystyle SIVP_{\gamma }}$ are equivalent with a small loss.^[7] Furthermore, even for quantum algorithms, ${\displaystyle \mathrm {SVP} _{\gamma }}$ and ${\displaystyle SIVP_{\gamma }}$ are very hard in the worst-case scenario.

Short integer solution problem

SIS and Ring-SIS are two average case problems that are used in lattice-based cryptography constructions. Lattice-based cryptography began in 1996 from a seminal work by Ajtai ^[1] who presented a family of one-way functions based on SIS problem. He showed that it is secure in average case if ${\displaystyle SVP_{\gamma }}$ (where ${\displaystyle \gamma =n^{c}}$ for some constant $c>0$) is hard in worse case scenario.

SIS_n,m,q,β

Let ${\displaystyle A\in \mathbb {Z} _{q}^{n\times m}}$ be an $n\times m$ matrix with entries in ${\displaystyle \mathbb {Z} _{q}}$ that consists of $m$ uniformly random vectors ${\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}}$: ${\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]}$. Find a nonzero vector ${\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m}}$ such that:

• ${\displaystyle \|{\boldsymbol {x}}\|\leq \beta }$
• ${\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}}$

It should be noted that a solution to SIS without the required constrain on the length of the solution (${\displaystyle \|{\boldsymbol {x}}\|\leq \beta }$) is easy to compute by using Gaussian elimination technique. We also require ${\displaystyle \beta <q}$, otherwise ${\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}}$ is a trivial solution.

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

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

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

Ring-SIS

Ring-SIS problem, a compact ring-based analogue of SIS problem, was studied in.^[2][8] They consider quotient polynomial ring ${\displaystyle R=\mathbb {Z} /(f(x))}$ with ${\displaystyle f(x)=x^{n}-1}$ and ${\displaystyle x^{2^{k}}+1}$, respectively, and extend the definition of norm on vectors in $\mathbb {R} ^{n}$ to vectors in $R^m$ as follows:

Given a vector ${\displaystyle {\vec {\boldsymbol {z}}}=(p_{1},\ldots ,p_{m})\in R^{m}}$ where $p_{i}(x)$ are some polynomial in $R$. Consider the embedding coefficient $\mathbb {Z}$-module isomorphism $\rho$:

${\displaystyle {\begin{array}{c}\quad \rho :R\rightarrow \mathbb {Z} ^{n}\\p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\mapsto (a_{0},\ldots ,a_{n-1})\end{array}}}$

Let ${\displaystyle {\boldsymbol {z_{i}}}=\rho (p_{i}(x))\in Z^{n}}$. Define norm ${\displaystyle {\vec {\boldsymbol {z}}}}$ as:

${\displaystyle \|{\vec {\boldsymbol {z}}}\|:={\sqrt {\sum _{i=1}^{m}\|{\boldsymbol {z_{i}}}\|^{2}}}}$

Alternatively, a better notion for norm is achieved by exploiting the canonical embedding. The canonical embedding is defined as:

${\displaystyle {\begin{aligned}\sigma :R=\mathbb {Z} /(f(x))&\rightarrow \mathbb {C} ^{n}\\p(x)&\mapsto (p(\alpha _{1}),\ldots ,p(\alpha _{n})\end{aligned}}}$

where $\alpha _{i}$ is the $i^{th}$ complex root of $f(x)$ for $i=1,\ldots, n$.

R-SIS_m,q,β

Given the quotient polynomial ring ${\displaystyle R=\mathbb {Z} /(f(x))}$, define

${\displaystyle R_{q}:=R/qR=\mathbb {Z} _{q}[x]/(f(x))}$. Select $m$ independent uniformly random elements ${\displaystyle a_{i}\in R_{q}}$. Define vector ${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}}$. Find a nonzero vector ${\displaystyle {\vec {\boldsymbol {z}}}:=(p_{1},\ldots ,p_{m})\in R^{m}}$ such that:

• ${\displaystyle \|{\vec {\boldsymbol {z}}}\|\leq \beta }$
• ${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{\,t}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.p_{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 $b$ is defined as:

${\displaystyle {\text{for}}\quad b=\sum _{i=0}^{n-1}b_{i}x^{i}\in R,\quad \mathrm {Rot} (b):={\begin{bmatrix}b_{0}&-b_{n-1}&\ldots &-b_{1}\\[0.3em]b_{1}&b_{0}&\ldots &-b_{2}\\[0.3em]\vdots &\vdots &\ddots &\vdots \\[0.3em]b_{n-1}&b_{n-2}&\ldots &b_{0}\end{bmatrix}}}$

When the quotient polynomial ring is ${\displaystyle R=\mathbb {Z} /(x^{n}+1)}$ for $n = 2^k$, the ring multiplication ${\displaystyle a_{i}.p_{i}}$ can be efficiently computed by first forming ${\displaystyle \operatorname {Rot} (a_{i})}$, the nega-circulant matrix of $a_{i}$, and then multiplying ${\displaystyle \operatorname {Rot} (a_{i})}$ with ${\displaystyle \rho (p_{i}(x))\in Z^{n}}$, the embedding coefficient vector of $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 $A$ in the SIS problem is restricted to negacirculant blocks: ${\displaystyle A=[\operatorname {Rot} (a_{1})|\cdots |\operatorname {Rot} (a_{m})]}$.^[9]

See also

• Lattice-based cryptography
• Homomorphic encryption
• Ring learning with errors key exchange
• Post-quantum cryptography
• Lattice problem

References

1. Ajtai, Miklós. [Generating hard instances of lattice problems.] Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996.
2. Micciancio, Daniele. [Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions.] Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on. IEEE, 2002.
3. Fukshansky, Lenny, and Xun Sun. [On the geometry of cyclic lattices.] Discrete & Computational Geometry 52.2 (2014): 240-259.
4. Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009.
5. http://web.cse.ohio-state.edu/~lai/5359-aut13/05.Gentry-FHE-concrete-scheme.pdf
6. Peikert, Chris. [A decade of lattice cryptography.] Cryptology ePrint Archive, Report 2015/939, 2015.
7. Peikert, Chris, and Alon Rosen. [Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices.] Theory of Cryptography. Springer Berlin Heidelberg, 2006. 145-166.
8. Lyubashevsky, Vadim, et al. [SWIFFT: A modest proposal for FFT hashing.] Fast Software Encryption. Springer Berlin Heidelberg, 2008.
9. Langlois, Adeline, and Damien Stehlé. [Worst-case to average-case reductions for module lattices.] Designs, Codes and Cryptography 75.3 (2015): 565-599.