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 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
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
Definition: Rotational shift operator on  is denoted by , and is defined as:

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

Examples:
  itself is a cyclic lattice.
 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 :

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

Hence,  is an ideal, and consequently, .

Ideal latticeshttp://web.cse.ohio-state.edu/~lai/5359-aut13/05.Gentry-FHE-concrete-scheme.pdf 
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:
 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. 
 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. Furthermore, even for quantum algorithms,  and  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 who presented a family of one-way functions based on SIS problem. He showed that it is secure in an average case if  (where  for some constant ) is hard in a worst-case scenario.

SISn,m,q,β
Let  be an  matrix with entries in  that consists of  uniformly random vectors : . Find a nonzero vector  such that:
 
 

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.

Ring-SIS
Ring-SIS problem, a compact ring-based analogue of SIS problem, was studied in. 
They consider quotient polynomial ring  with  and , respectively, and extend the definition of norm on vectors in  to vectors in  as follows:

Given a vector  where  are some polynomial in . Consider the embedding coefficient -module isomorphism :

Let . Define norm  as:

 

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

 

where  is the  complex root of  for .

R-SISm,q,β
Given the quotient polynomial ring , define

. 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: .

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

References 

Number theory
Lattice-based cryptography
Post-quantum cryptography
Computational problems
Computational hardness assumptions