Short integer solution problem

A full rank lattice \mathfrak{L} \subset \R^n is a set of integer linear combinations of n linearly independent vectors \{b_1,\ldots,b_n\} , 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 \in \R ^{n\times n} is a matrix having basis vectors in its columns. Remark: Given B_1,B_2 two bases for lattice \mathfrak{L} , there exist unimodular matrices U_1 such that B_1 = B_2U_1^{-1}, B_2 = B_1U_1 . ==Ideal lattice==

Definition: Rotational shift operator on \R^n (n \geq 2) is denoted by \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}) 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 \mathfrak{L} \subseteq \Z^n is cyclic if \forall \boldsymbol{x} \in \mathfrak{L}: \operatorname{rot}(\boldsymbol{x}) \in \mathfrak{L} . Examples: • \Z^n itself is a cyclic lattice. • Lattices corresponding to any ideal in the quotient polynomial ring R = \Z[x]/(x^n-1) are cyclic: consider the quotient polynomial ring R = \Z[x]/(x^n-1) , and let p(x) be some polynomial in R , i.e. p(x) = \sum_{i=0}^{n-1}a_ix^i where a_i \in \Z for i = 0,\ldots, n-1 . Define the embedding coefficient \Z -module isomorphism \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 \subset R be an ideal. The lattice corresponding to ideal I \subset R , denoted by \mathfrak{L}_I , is a sublattice of \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_ix^i \in I \right\} \subset \Z^n. Theorem: \mathfrak{L} \subset \Z^n is cyclic if and only if \mathfrak{L} corresponds to some ideal I in the quotient polynomial ring R = \Z[x]/(x^n-1) . proof: \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,\ldots,a_{n-1}) be an arbitrary element in \mathfrak{L} . Then, define p(x) = \sum_{i=0}^{n-1}a_ix^i \in I . But since I is an ideal, we have xp(x) \in I . Then, \rho(xp(x)) \in \mathfrak{L}_I . But, \rho(xp(x)) = \operatorname{rot}(a_0,\ldots,a_{n-1}) \in \mathfrak{L}_I . Hence, \mathfrak{L} is cyclic. \Rightarrow) Let \mathfrak{L} \subset \Z^n be a cyclic lattice. Hence \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 I: = \left\{ \sum_{i=0}^{n-1}a_ix^i \mid (a_0,\ldots,a_{n-1}) \in \mathfrak{L} \right\} : • Since \mathfrak{L} a lattice and hence an additive subgroup of \Z^n , I \subset R is an additive subgroup of R . • Since \mathfrak{L} is cyclic, \forall p(x) \in I: xp(x) \in I . Hence, I \subset R is an ideal, and consequently, \mathfrak{L} = \mathfrak{L}_I . Ideal lattices Source: Let f(x) \in \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 = \Z[x]/(f(x)) partitions \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 \Z-module isomorphism \rho. Then, each ideal in R defines a sublattice of \Z^n called ideal lattice. Definition: \mathfrak{L}_I, the lattice corresponding to an ideal I, is called ideal lattice. More precisely, consider a quotient polynomial ring R = \Z[x]/(p(x)), where (p(x)) is the ideal generated by a degree n polynomial p(x) \in \Z[x]. \mathfrak{L}_I, is a sublattice of \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: • It turns out that \text{GapSVP}_\gamma for even small \gamma = \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. • 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, \mathrm{SVP}_\gamma and \mathrm{SIVP}_\gamma are equivalent with a small loss. Furthermore, even for quantum algorithms, \mathrm{SVP}_\gamma and \mathrm{SIVP}_\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 SISq,n,m,β Let A \in \Z^{n\times m}_q be an n\times m matrix with entries in \Z_q that consists of m uniformly random vectors \boldsymbol{a_i} \in \Z^n_q: A = [\boldsymbol{a_1}|\cdots|\boldsymbol{a_m}]. Find a nonzero vector \boldsymbol{x} \in \Z^m such that for some norm \|\cdot\|: • 0 , • f_A(\boldsymbol{x}) := A\boldsymbol{x} = \boldsymbol{0} \in \Z^n_q. A solution to SIS without the required constraint on the length of the solution (\|\boldsymbol{x}\| \leq \beta) is easy to compute by using Gaussian elimination technique. We also require \beta , otherwise \boldsymbol{x} = (q,0,\ldots,0) \in \Z^m is a trivial solution. In order to guarantee f_A(\boldsymbol{x}) has non-trivial, short solution, we require: • \beta \geq \sqrt{n\log q}, and • m \geq n\log q Theorem: For any m = \operatorname{poly}(n), any \beta > 0, and any sufficiently large q \geq \beta n^c (for any constant c >0), solving \operatorname{SIS}_{n,m,q,\beta} with nonnegligible probability is at least as hard as solving the \operatorname{GapSVP}_\gamma and \operatorname{SIVP}_\gamma for some \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 R_q = \Z_q[x]/(f(x)) with f(x) = x^n-1 for some integer n and with some norm \|\cdot\|. Of particular interest are cases where there exists integer k such that n=2^k as this restricts the quotient to cyclotomic polynomials. We then define the problem as follows: Select m independent uniformly random elements a_i \in R_q. Define vector \vec{\boldsymbol{a}}:=(a_1,\ldots,a_m) \in R_q^m. Find a nonzero vector \vec{\boldsymbol{z}}:=(z_1,\ldots,z_m) \in R^m such that: • 0, • 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. Recall that to guarantee existence of a solution to SIS problem, we require 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 m \approx \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 = \Z[x]/(x^n+1) for n = 2^k, the ring multiplication a_i.p_i can be efficiently computed by first forming \operatorname{rot}(a_i), the nega-circulant matrix of a_i, and then multiplying \operatorname{rot}(a_i) with \rho(p_i(x)) \in Z^n, the embedding coefficient vector of p_i (or, alternatively with \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: A = [\operatorname{rot}(a_1)|\cdots|\operatorname{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 R = \Z[x]/(f(x)) and R_q = \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\subseteq R^d and let \|\cdot\| be an arbitrary norm over R_q^{m}. We then define the problem as follows: Select m independent uniformly random elements a_i \in R_q^d. Define vector \vec{\boldsymbol{a}}:=(a_1,\ldots,a_m) \in R_q^{d\times m}. Find a nonzero vector \vec{\boldsymbol{z}}:=(z_1,\ldots,z_m) \in R^m such that: • 0 , • 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. 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. ==See also==