Short integer solution problem

A full rank lattice $\backslash mathfrak\{L\}\; \backslash subset\; \backslash R^n$ is a set of integer linear combinations of $n$ linearly independent vectors $\backslash \{b\_1,\backslash ldots,b\_n\backslash \}$, named basis:

: $$

\mathfrak{L}(b_1,\ldots,b_n) = \left\{ \sum_{i=1}^n z_i b_i: z_i \in \Z \right\} = \{ B\boldsymbol{z}: \boldsymbol{z} \in \Z^n \}

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

Remark: Given $B\_1,B\_2$ two bases for lattice $\backslash mathfrak\{L\}$, there exist unimodular matrices $U\_1$ such that $B\_1\; =\; B\_2U\_1^\{-1\},\; B\_2\; =\; B\_1U\_1$.

Definition: Rotational shift operator on $\backslash R^n\; (n\; \backslash geq\; 2)$ is denoted by $\backslash operatorname\{rot\}$, and is defined as:

: $$

\forall \boldsymbol{x} = (x_1,\ldots,x_{n-1},x_n) \in \R^n: \operatorname{rot}(x_1,\ldots,x_{n-1},x_n) = (x_n,x_1,\ldots,x_{n-1})

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

Definition: A lattice $\backslash mathfrak\{L\}\; \backslash subseteq\; \backslash Z^n$ is cyclic if $\backslash forall\; \backslash boldsymbol\{x\}\; \backslash in\; \backslash mathfrak\{L\}:\; \backslash operatorname\{rot\}(\backslash boldsymbol\{x\})\; \backslash in\; \backslash mathfrak\{L\}$.

Examples:Fukshansky, Lenny, and Xun Sun. [On the geometry of cyclic lattices.] Discrete & Computational Geometry 52.2 (2014): 240–259.

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

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

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

: $$

\begin{align}

\quad \rho: R & \rightarrow \Z^n \\[4pt]

p(x) = \sum_{i=0}^{n-1}a_ix^i & \mapsto (a_0,\ldots,a_{n-1})

\end{align}

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

: $\backslash mathfrak\{L\}\_I\; :=\; \backslash rho(I)\; =\; \backslash left\backslash \{\; (a\_0,\backslash ldots,a\_\{n-1\})\; \backslash mid\; \backslash sum\_\{i=0\}^\{n-1\}a\_ix^i\; \backslash in\; I\; \backslash right\backslash \}\; \backslash subset\; \backslash Z^n.$

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

proof:

$\backslash Leftarrow)$ We have:

: $$

\mathfrak{L} = \mathfrak{L}_I := \rho(I) = \left\{ (a_0,\ldots,a_{n-1}) \mid \sum_{i=0}^{n-1}a_ix^i \in I\right\}

Let $(a\_0,\backslash ldots,a\_\{n-1\})$ be an arbitrary element in $\backslash mathfrak\{L\}$. Then, define $p(x)\; =\; \backslash sum\_\{i=0\}^\{n-1\}a\_ix^i\; \backslash in\; I$. But since $I$ is an ideal, we have $xp(x)\; \backslash in\; I$. Then, $\backslash rho(xp(x))\; \backslash in\; \backslash mathfrak\{L\}\_I$. But, $\backslash rho(xp(x))\; =\; \backslash operatorname\{rot\}(a\_0,\backslash ldots,a\_\{n-1\})\; \backslash in\; \backslash mathfrak\{L\}\_I$. Hence, $\backslash mathfrak\{L\}$ is cyclic.

$\backslash Rightarrow)$

Let $\backslash mathfrak\{L\}\; \backslash subset\; \backslash Z^n$ be a cyclic lattice. Hence $\backslash forall\; (a\_0,\backslash ldots,a\_\{n-1\})\; \backslash in\; \backslash mathfrak\{L\}:\; \backslash operatorname\{rot\}(a\_0,\backslash ldots,a\_\{n-1\})\; \backslash in\; \backslash mathfrak\{L\}$.

Define the set of polynomials $I:\; =\; \backslash left\backslash \{\; \backslash sum\_\{i=0\}^\{n-1\}a\_ix^i\; \backslash mid\; (a\_0,\backslash ldots,a\_\{n-1\})\; \backslash in\; \backslash mathfrak\{L\}\; \backslash right\backslash \}$:

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

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

Let $f(x)\; \backslash in\; \backslash 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:

: $$

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

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

: $$

R = \Z[x]/(f(x)) = \left\{ \sum_{i=0}^{n-1}a_ix^i: a_i \in \Z \right\}

where addition and multiplication are reduced modulo $f(x)$.

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

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

: $$

\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 \Z^n.

Remark:Peikert, Chris. [A decade of lattice cryptography.] Cryptology ePrint Archive, Report 2015/939, 2015.

1. It turns out that $\backslash text\{GapSVP\}\_\backslash gamma$ for even small $\backslash gamma\; =\; \backslash operatorname\{poly(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 $n$ linearly independent ones of (nearly) the same length. Therefore, on ideal lattices, $\backslash mathrm\{SVP\}\_\backslash gamma$ and $\backslash mathrm\{SIVP\}\_\backslash gamma$ are equivalent with a small loss.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. Furthermore, even for quantum algorithms, $\backslash mathrm\{SVP\}\_\backslash gamma$ and $\backslash mathrm\{SIVP\}\_\backslash gamma$ are believed to be very hard in the worst-case scenario.

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 $\backslash mathrm\{SVP\}\_\{\backslash gamma\}$ (where $\backslash gamma\; =\; n^c$ for some constant $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.{{cite web|url=https://pq-crystals.org/dilithium/data/dilithium-specification-round3.pdf|title=CRYSTALS-Dilithium:Algorithm Specifications and Supporting Documentation|last1=Bai|first1=Shi|last2=Ducas|first2=Léo|last3=Kiltz|first3=Eike|last4=Lepoint|first4= Tancrède|last5=Lyubashevsky|first5=Vadim|last6=Schwabe|first6=Peter|last7=Seiler|first7=Grego4|last8=Stehlé|first8=Damien|date=October 1, 2020|access-date=November 13, 2023|website=PQ-Crystals.org}}{{cite web|url=https://falcon-sign.info|title=Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU|first1=Pierre-Alain|last1=Fouque|first2=Jeffrey|last2=Hoffstein|first3=Paul|last3=Kirchner|first4=Vadim|last4=Lyubashevsky|first5=Thomas|last5=Pornin|first6=Thomas|last6=Prest|first7=Thomas|last7=Ricosset|first8=Gregor|last8=Seiler|first9=William|last9=Whyte|first10=Zhenfei|last10=Zhang|date=October 1, 2020|access-date=November 13, 2023}}

Let $A\; \backslash in\; \backslash Z^\{n\backslash times\; m\}\_q$ be an $n\backslash times\; m$ matrix with entries in $\backslash Z\_q$ that consists of $m$ uniformly random vectors $\backslash boldsymbol\{a\_i\}\; \backslash in\; \backslash Z^n\_q$: $A\; =\; [\backslash boldsymbol\{a\_1\}|\backslash cdots|\backslash boldsymbol\{a\_m\}]$. Find a nonzero vector $\backslash boldsymbol\{x\}\; \backslash in\; \backslash Z^m$ such that for some norm $\backslash |\backslash cdot\backslash |$:

• ,
• $f\_A(\backslash boldsymbol\{x\})\; :=\; A\backslash boldsymbol\{x\}\; =\; \backslash boldsymbol\{0\}\; \backslash in\; \backslash Z^n\_q$.

A solution to SIS without the required constraint on the length of the solution ($\backslash |\backslash boldsymbol\{x\}\backslash |\; \backslash leq\; \backslash beta$) is easy to compute by using Gaussian elimination technique. We also require , otherwise $\backslash boldsymbol\{x\}\; =\; (q,0,\backslash ldots,0)\; \backslash in\; \backslash Z^m$ is a trivial solution.

In order to guarantee $f\_A(\backslash boldsymbol\{x\})$ has non-trivial, short solution, we require:

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

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

The SIS problem solved over an ideal ring is also called the Ring-SIS or R-SIS problem.Lyubashevsky, Vadim, et al. [SWIFFT: A modest proposal for FFT hashing.] Fast Software Encryption. Springer Berlin Heidelberg, 2008. This problem considers a quotient polynomial ring $R\_q\; =\; \backslash Z\_q[x]/(f(x))$ with $f(x)\; =\; x^n-1$ for some integer $n$ and with some norm $\backslash |\backslash cdot\backslash |$. Of particular interest are cases where there exists integer $k$ such that $n=2^k$ as this restricts the quotient to cyclotomic polynomials.Langlois, Adeline, and Damien Stehlé. [Worst-case to average-case reductions for module lattices.] Designs, Codes and Cryptography 75.3 (2015): 565–599.

We then define the problem as follows:

Select $m$ independent uniformly random elements $a\_i\; \backslash in\; R\_q$. Define vector $\backslash vec\{\backslash boldsymbol\{a\}\}:=(a\_1,\backslash ldots,a\_m)\; \backslash in\; R\_q^m$. Find a nonzero vector $\backslash vec\{\backslash boldsymbol\{z\}\}:=(z\_1,\backslash ldots,z\_m)\; \backslash in\; R^m$ such that:

• ,
• $f\_\{\backslash vec\{\backslash boldsymbol\{a\}\}\}(\backslash vec\{\backslash boldsymbol\{z\}\})\; :=\; \backslash vec\{\backslash boldsymbol\{a\}\}^\{T\}.\backslash vec\{\backslash boldsymbol\{z\}\}\; =\; \backslash sum\_\{i=1\}^m\; a\_i.z\_i\; =\; 0\; \backslash in\; R\_q$.

Recall that to guarantee existence of a solution to SIS problem, we require $m\; \backslash approx\; n\backslash 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 $m\; \backslash approx\; \backslash log\; q$ .

Definition: The nega-circulant matrix of $b$ is defined as:

: $$

\text{for} \quad b = \sum_{i=0}^{n-1}b_ix^i \in R, \quad

\operatorname{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 $R\; =\; \backslash Z[x]/(x^n+1)$ for $n\; =\; 2^k$, the ring multiplication $a\_i.p\_i$ can be efficiently computed by first forming $\backslash operatorname\{rot\}(a\_i)$, the nega-circulant matrix of $a\_i$, and then multiplying $\backslash operatorname\{rot\}(a\_i)$ with $\backslash rho(p\_i(x))\; \backslash in\; Z^n$, the embedding coefficient vector of $p\_i$ (or, alternatively with $\backslash sigma(p\_i(x))\; \backslash 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: $A\; =\; [\backslash operatorname\{rot\}(a\_1)|\backslash cdots|\backslash operatorname\{rot\}(a\_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 $R\; =\; \backslash Z[x]/(f(x))$ and $R\_q\; =\; \backslash Z\_q[x]/(f(x))$ for $f(x)\; =\; x^n-1$ with a special interest in cases where $n$ is a power of 2. Then, let $M$ be a module of rank $d$ such that $M\backslash subseteq\; R^d$ and let $\backslash |\backslash cdot\backslash |$ be an arbitrary norm over $R\_q^\{m\}$.

We then define the problem as follows:

Select $m$ independent uniformly random elements $a\_i\; \backslash in\; R\_q^d$. Define vector $\backslash vec\{\backslash boldsymbol\{a\}\}:=(a\_1,\backslash ldots,a\_m)\; \backslash in\; R\_q^\{d\backslash times\; m\}$. Find a nonzero vector $\backslash vec\{\backslash boldsymbol\{z\}\}:=(z\_1,\backslash ldots,z\_m)\; \backslash in\; R^m$ such that:

• ,
• $f\_\{\backslash vec\{\backslash boldsymbol\{a\}\}\}(\backslash vec\{\backslash boldsymbol\{z\}\})\; :=\; \backslash vec\{\backslash boldsymbol\{a\}\}^\{T\}.\backslash vec\{\backslash boldsymbol\{z\}\}\; =\; \backslash sum\_\{i=1\}^m\; a\_i.z\_i\; =\; 0\; \backslash 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.

• Lattice-based cryptography
• Homomorphic encryption
• Ring learning with errors key exchange
• Post-quantum cryptography
• Lattice problem
• {{slink|TFNP#PPP}}

{{Computational hardness assumptions}}

Category:Number theory

Category:Lattice-based cryptography

Category:Post-quantum cryptography

Category:Computational problems

Category:Computational hardness assumptions