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 Miklós Ajtai[1] who presented a family of one-way functions based on SIS problem. He showed that it is secure in an average case if the shortest vector problem (where for some constant ) is hard in a worst-case scenario.

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

edit

A full rank lattice   is a set of integer linear combinations of   linearly independent vectors  , named basis:

 

where   is a matrix having basis vectors in its columns.

Remark: Given   two bases for lattice  , there exist unimodular matrices   such that  .

Ideal lattice

edit

Definition: Rotational shift operator on   is denoted by  , and is defined as:

 

Cyclic lattices

edit

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   is cyclic if  .

Examples:[3]

  1.   itself is a cyclic lattice.
  2. Lattices corresponding to any ideal in the quotient polynomial ring   are cyclic:

consider the quotient polynomial ring  , and let   be some polynomial in  , i.e.   where   for  .

Define the embedding coefficient  -module isomorphism   as:

 

Let   be an ideal. The lattice corresponding to ideal  , denoted by  , is a sublattice of  , and is defined as

 

Theorem:   is cyclic if and only if   corresponds to some ideal   in the quotient polynomial ring  .

proof:   We have:

 

Let   be an arbitrary element in  . Then, define  . But since   is an ideal, we have  . Then,  . But,  . Hence,   is cyclic.

 

Let   be a cyclic lattice. Hence  .

Define the set of polynomials  :

  1. Since   a lattice and hence an additive subgroup of  ,   is an additive subgroup of  .
  2. Since   is cyclic,  .

Hence,   is an ideal, and consequently,  .

Ideal lattices[4]

edit

Let   be a monic polynomial of degree  . For cryptographic applications,   is usually selected to be irreducible. The ideal generated by   is:

 

The quotient polynomial ring   partitions   into equivalence classes of polynomials of degree at most  :

 

where addition and multiplication are reduced modulo  .

Consider the embedding coefficient  -module isomorphism  . Then, each ideal in   defines a sublattice of   called ideal lattice.

Definition:  , the lattice corresponding to an ideal  , is called ideal lattice. More precisely, consider a quotient polynomial ring  , where   is the ideal generated by a degree   polynomial  .  , is a sublattice of  , and is defined as:

 

Remark:[5]

  1. It turns out that   for even small   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   linearly independent ones of (nearly) the same length. Therefore, on ideal lattices,   and   are equivalent with a small loss.[6] Furthermore, even for quantum algorithms,   and   are believed to be very hard in the worst-case scenario.

Short integer solution problem

edit

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[1] who presented a family of one-way functions based on the SIS problem. He showed that it is secure in an average case if   (where   for some constant  ) 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.[7][8]

SISq,n,m,β

edit

Let   be an   matrix with entries in   that consists of   uniformly random vectors  :  . Find a nonzero vector   such that for some norm  :

  •  ,
  •  .

A solution to SIS without the required constraint on the length of the solution ( ) is easy to compute by using Gaussian elimination technique. We also require  , otherwise   is a trivial solution.

In order to guarantee   has non-trivial, short solution, we require:

  •  , and
  •  

Theorem: For any  , any  , and any sufficiently large   (for any constant  ), solving   with nonnegligible probability is at least as hard as solving the   and   for some   with a high probability in the worst-case scenario.

R-SISq,n,m,β

edit

The SIS problem solved over an ideal ring is also called the Ring-SIS or R-SIS problem.[2][9] This problem considers a quotient polynomial ring   with   for some integer   and with some norm  . Of particular interest are cases where there exists integer   such that   as this restricts the quotient to cyclotomic polynomials.[10]

We then define the problem as follows:

Select   independent uniformly random elements  . Define vector  . Find a nonzero vector   such that:

  •  ,
  •  .

Recall that to guarantee existence of a solution to SIS problem, we require  . However, Ring-SIS problem provide us with more compactness and efficacy: to guarantee existence of a solution to Ring-SIS problem, we require   .

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

 

When the quotient polynomial ring is   for  , the ring multiplication   can be efficiently computed by first forming  , the nega-circulant matrix of  , and then multiplying   with  , the embedding coefficient vector of   (or, alternatively with  , the canonical coefficient vector.

Moreover, R-SIS problem is a special case of SIS problem where the matrix   in the SIS problem is restricted to negacirculant blocks:  .[10]

M-SISq,n,d,m,β

edit

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   and   for   with a special interest in cases where   is a power of 2. Then, let   be a module of rank   such that   and let   be an arbitrary norm over  .

We then define the problem as follows:

Select   independent uniformly random elements  . Define vector  . Find a nonzero vector   such that:

  •  ,
  •  .

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.[10]

See also

edit

References

edit
  1. ^ a b Ajtai, Miklós. [Generating hard instances of lattice problems.] Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996.
  2. ^ a b 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. ^ Peikert, Chris. [A decade of lattice cryptography.] Cryptology ePrint Archive, Report 2015/939, 2015.
  6. ^ 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.
  7. ^ Bai, Shi; Ducas, Léo; Kiltz, Eike; Lepoint, Tancrède; Lyubashevsky, Vadim; Schwabe, Peter; Seiler, Grego4; Stehlé, Damien (October 1, 2020). "CRYSTALS-Dilithium:Algorithm Specifications and Supporting Documentation" (PDF). PQ-Crystals.org. Retrieved November 13, 2023.{{cite web}}: CS1 maint: numeric names: authors list (link)
  8. ^ Fouque, Pierre-Alain; Hoffstein, Jeffrey; Kirchner, Paul; Lyubashevsky, Vadim; Pornin, Thomas; Prest, Thomas; Ricosset, Thomas; Seiler, Gregor; Whyte, William; Zhang, Zhenfei (October 1, 2020). "Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU". Retrieved November 13, 2023.
  9. ^ Lyubashevsky, Vadim, et al. [SWIFFT: A modest proposal for FFT hashing.] Fast Software Encryption. Springer Berlin Heidelberg, 2008.
  10. ^ a b c Langlois, Adeline, and Damien Stehlé. [Worst-case to average-case reductions for module lattices.] Designs, Codes and Cryptography 75.3 (2015): 565–599.