imported>Antonissimo: /* top */ more convenient syntax

2025-11-30T04:55:53Z

top: more convenient syntax

New page

{{Short description|Computational problem used in cryptography}}
'''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 [[Miklós Ajtai]]<ref name="Ajtai, Miklós 1996">Ajtai, Miklós. [Generating hard instances of lattice problems.] Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996.</ref> who presented a family of [[one-way function]]s based on SIS problem. He showed that it is secure in an average case if the [[shortest vector problem]] <math>\mathrm{SVP}_\gamma</math> (where <math>\gamma = n^c</math> for some constant <math>c>0</math>) is hard in the worst case.

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

==Lattices==
A ''full rank [[Lattice (group)|lattice]]'' <math> \mathfrak{L} \subset \R^n </math> is a set of integer linear combinations of <math> n </math> linearly independent vectors <math> \{b_1,\ldots,b_n\} </math>, named ''basis'':

: <math>
\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 \}
</math>

where <math> B \in \R ^{n\times n} </math> is a matrix having basis vectors in its columns.

'''Remark:''' Given <math> B_1,B_2 </math> two bases for lattice <math> \mathfrak{L} </math>, there exist unimodular matrices <math> U_1 </math> such that <math> B_1 = B_2U_1^{-1}, B_2 = B_1U_1 </math>.

==Ideal lattice==
'''Definition:''' Rotational [[shift operator]] on <math> \R^n (n \geq 2) </math> is denoted by <math> \operatorname{rot} </math>, and is defined as:

: <math>
\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})
</math>

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

'''Definition:''' A lattice <math> \mathfrak{L} \subseteq \Z^n </math> is cyclic if <math> \forall \boldsymbol{x} \in \mathfrak{L}: \operatorname{rot}(\boldsymbol{x}) \in \mathfrak{L} </math>.

'''Examples:'''<ref>Fukshansky, Lenny, and Xun Sun. [On the geometry of cyclic lattices.] Discrete & Computational Geometry 52.2 (2014): 240–259.</ref>
# <math> \Z^n </math> itself is a cyclic lattice.
# Lattices corresponding to any ideal in the quotient polynomial ring <math> R = \Z[x]/(x^n-1) </math> are cyclic:
consider the quotient polynomial ring <math> R = \Z[x]/(x^n-1) </math>, and let <math> p(x) </math> be some polynomial in <math> R </math>, i.e. <math> p(x) = \sum_{i=0}^{n-1}a_ix^i </math> where <math> a_i \in \Z </math> for <math> i = 0,\ldots, n-1 </math>.

Define the embedding coefficient <math> \Z </math>-module isomorphism <math> \rho </math> as:

: <math>
\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}
</math>

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

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

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

'''proof:'''
<math> \Leftarrow)</math> We have:
: <math>
\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\}
</math>

Let <math> (a_0,\ldots,a_{n-1}) </math> be an arbitrary element in <math> \mathfrak{L} </math>. Then, define <math> p(x) = \sum_{i=0}^{n-1}a_ix^i \in I </math>. But since <math> I </math> is an ideal, we have <math> xp(x) \in I </math>. Then, <math> \rho(xp(x)) \in \mathfrak{L}_I </math>. But, <math> \rho(xp(x)) = \operatorname{rot}(a_0,\ldots,a_{n-1}) \in \mathfrak{L}_I </math>. Hence, <math> \mathfrak{L} </math> is cyclic.

<math> \Rightarrow)</math>

Let <math> \mathfrak{L} \subset \Z^n </math> be a cyclic lattice. Hence <math> \forall (a_0,\ldots,a_{n-1}) \in \mathfrak{L}: \operatorname{rot}(a_0,\ldots,a_{n-1}) \in \mathfrak{L} </math>.

Define the set of polynomials <math> I: = \left\{ \sum_{i=0}^{n-1}a_ix^i \mid (a_0,\ldots,a_{n-1}) \in \mathfrak{L} \right\} </math>:

# Since <math> \mathfrak{L} </math> a lattice and hence an additive subgroup of <math> \Z^n </math>, <math> I \subset R </math> is an additive subgroup of <math> R </math>.
# Since <math> \mathfrak{L} </math> is cyclic, <math> \forall p(x) \in I: xp(x) \in I </math>.

Hence, <math> I \subset R </math> is an ideal, and consequently, <math> \mathfrak{L} = \mathfrak{L}_I </math>.

===Ideal lattices ===
Source:<ref>Craig Gentry. [http://portal.acm.org/citation.cfm?id=1536414.1536440 Fully Homomorphic Encryption Using Ideal Lattices]. In ''the 41st ACM Symposium on Theory of Computing (STOC)'', 2009.</ref>

Let <math> f(x) \in \Z[x] </math> be a [[monic polynomial]] of degree <math> n </math>. For cryptographic applications, <math> f(x) </math> is usually selected to be irreducible. The ideal generated by <math> f(x) </math> is:

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

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

: <math>
R = \Z[x]/(f(x)) = \left\{ \sum_{i=0}^{n-1}a_ix^i: a_i \in \Z \right\}
</math>
where addition and multiplication are reduced modulo <math>f(x)</math>.

Consider the embedding coefficient <math>\Z</math>-module isomorphism <math>\rho</math>. Then, each ideal in <math>R</math> defines a sublattice of <math>\Z^n</math> called [[Ideal lattice cryptography|ideal lattice]].

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

: <math>
\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.
</math>

'''Remark:<ref>Peikert, Chris. [A decade of lattice cryptography.] Cryptology ePrint Archive, Report 2015/939, 2015.</ref>'''
# It turns out that [[Lattice problem|<math>\text{GapSVP}_\gamma</math>]] for even small <math>\gamma = \operatorname{poly(n)}</math> 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.
# By exploiting the provided algebraic symmetries in ideal lattices, one can convert a short nonzero vector into <math>n</math> linearly independent ones of (nearly) the same length. Therefore, on ideal lattices, [[Shortest vector problem|<math>\mathrm{SVP}_\gamma</math>]] and [[Lattice problem|<math>\mathrm{SIVP}_\gamma</math>]] are equivalent with a small loss.<ref>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.</ref> Furthermore, even for [[Quantum algorithm|quantum algorithms]], [[Shortest vector problem|<math>\mathrm{SVP}_\gamma</math>]] and [[Lattice problem|<math>\mathrm{SIVP}_\gamma</math>]] 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<ref name="Ajtai, Miklós 1996"/> who presented a family of one-way functions based on the SIS problem. He showed that it is secure in an average case if <math>\mathrm{SVP}_{\gamma}</math> (where <math>\gamma = n^c</math> for some constant <math>c>0</math>) 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 [[Lattice-based cryptography|CRYSTALS-Dilithium]] and [[Lattice-based cryptography|Falcon]].<ref name="Crystals-Dilithium">{{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}}</ref><ref name="FALCON">{{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}}</ref>

===SIS''q'',''n'',''m'',''β''===
Let <math>A \in \Z^{n\times m}_q</math> be an <math>n\times m</math> matrix with entries in <math>\Z_q</math> that consists of <math>m</math> uniformly random vectors <math>\boldsymbol{a_i} \in \Z^n_q</math>: <math>A = [\boldsymbol{a_1}|\cdots|\boldsymbol{a_m}]</math>. Find a nonzero vector <math>\boldsymbol{x} \in \Z^m</math> such that for some norm <math>\|\cdot\|</math>:
* <math> 0 < \|\boldsymbol{x}\| \leq \beta</math>,
* <math>f_A(\boldsymbol{x}) := A\boldsymbol{x} = \boldsymbol{0} \in \Z^n_q</math>.

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

In order to guarantee <math>f_A(\boldsymbol{x})</math> has non-trivial, short solution, we require:
* <math>\beta \geq \sqrt{n\log q}</math>, and
* <math>m \geq n\log q</math>

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

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

We then define the problem as follows:

Select <math>m</math> independent uniformly random elements <math>a_i \in R_q</math>. Define vector <math>\vec{\boldsymbol{a}}:=(a_1,\ldots,a_m) \in R_q^m</math>. Find a nonzero vector <math>\vec{\boldsymbol{z}}:=(z_1,\ldots,z_m) \in R^m</math> such that:
* <math> 0<\|\vec{\boldsymbol{z}}\| \leq \beta</math>,
* <math>f_{\vec{\boldsymbol{a}}}(\vec{\boldsymbol{z}}) := \vec{\boldsymbol{a}}^{T}.\vec{\boldsymbol{z}} = \sum_{i=1}^m a_i.z_i = 0 \in R_q</math>.

Recall that to guarantee existence of a solution to SIS problem, we require <math>m \approx n\log q</math>. However, Ring-SIS problem provide us with more compactness and efficacy: to guarantee existence of a solution to Ring-SIS problem, we require <math>m \approx \log q</math> .

'''Definition:''' The ''nega-circulant matrix'' of <math>b</math> is defined as:

: <math>
\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}
</math>

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

Moreover, R-SIS problem is a special case of SIS problem where the matrix <math>A</math> in the SIS problem is restricted to negacirculant blocks: <math>A = [\operatorname{rot}(a_1)|\cdots|\operatorname{rot}(a_m)]</math>.<ref name=LangloisStehle2015 />

===M-SIS''q'',''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 <math>R = \Z[x]/(f(x))</math> and <math>R_q = \Z_q[x]/(f(x))</math> for <math>f(x) = x^n-1</math> with a special interest in cases where <math>n</math> is a power of 2. Then, let <math>M</math> be a module of rank <math>d</math> such that <math>M\subseteq R^d</math> and let <math>\|\cdot\|</math> be an arbitrary norm over <math>R_q^{m}</math>.

We then define the problem as follows:

Select <math>m</math> independent uniformly random elements <math>a_i \in R_q^d</math>. Define vector <math>\vec{\boldsymbol{a}}:=(a_1,\ldots,a_m) \in R_q^{d\times m}</math>. Find a nonzero vector <math>\vec{\boldsymbol{z}}:=(z_1,\ldots,z_m) \in R^m</math> such that:
* <math> 0 <\|\vec{\boldsymbol{z}}\| \leq \beta</math>,
* <math>f_{\vec{\boldsymbol{a}}}(\vec{\boldsymbol{z}}) := \vec{\boldsymbol{a}}^{T}.\vec{\boldsymbol{z}} = \sum_{i=1}^m a_i.z_i = 0 \in R_q^d</math>.

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.<ref name=LangloisStehle2015 />

==See also==
*[[Lattice-based cryptography]]
*[[Homomorphic encryption]]
*[[Ring learning with errors key exchange]]
*[[Post-quantum cryptography]]
*[[Lattice problem]]
*{{slink|TFNP#PPP}}

== References ==
<references/>

{{Computational hardness assumptions}}

[[Category:Number theory]]
[[Category:Lattice-based cryptography]]
[[Category:Post-quantum cryptography]]
[[Category:Computational problems]]
[[Category:Computational hardness assumptions]]

Short integer solution problem - Revision history

imported>Antonissimo: /* top */ more convenient syntax