Short integer solution problem

Lattices

A full rank lattice L ⊂ R n is a set of integer linear combinations of n linearly independent vectors { b 1 , … , b n } , named basis:

where B ∈ R n × n is a matrix having basis vectors in its columns.

Remark: Given B 1 , B 2 two bases for lattice L , there exist unimodular matrices U 1 such that B 1 = B 2 U 1 − 1 , B 2 = B 1 U 1 .

Ideal lattice

Definition: Rotational shift operator on R n ( n ≥ 2 ) is denoted by rot , and is defined as: ∀ x = ( x 1 , … , x n − 1 , x n ) ∈ R n : rot ⁡ ( x 1 , … , x n − 1 , x n ) = ( x n , x 1 , … , 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 L ∈ Z n is cyclic if ∀ x ∈ L : rot ⁡ ( x ) ∈ L .

Examples:

1. Z n itself is a cyclic lattice.
2. 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 ) = ∑ i = 0 n − 1 a i x i where a i ∈ Z for i = 0 , … , n − 1 .

Define the embedding coefficient Z -module isomorphism ρ as:

Let I ⊂ R be an ideal. The lattice corresponding to ideal I ⊂ R , denoted by L I , is a sublattice of Z n , and is defined as

Theorem: L ⊂ Z n is cyclic if and only if L corresponds to some ideal I in the quotient polynomial ring R = Z [ x ] / ( x n − 1 ) .

proof: ⇐ ) We have:

Let ( a 0 , … , a n − 1 ) be an arbitrary element in L . Then, define p ( x ) = ∑ i = 0 n − 1 a i x i ∈ I . But since I is an ideal, we have x p ( x ) ∈ I . Then, ρ ( x p ( x ) ) ∈ L I . But, ρ ( x p ( x ) ) = rot ⁡ ( a 0 , … , a n − 1 ) ∈ L I . Hence, L is cyclic.

⇒ )

Let L ⊂ Z n be a cyclic lattice. Hence ∀ ( a 0 , … , a n − 1 ) ∈ L : rot ⁡ ( a 0 , … , a n − 1 ) ∈ L .

Define the set of polynomials I := { ∑ i = 0 n − 1 a i x i ∣ ( a 0 , … , a n − 1 ) ∈ L } :

1. Since L a lattice and hence an additive subgroup of Z n , I ⊂ R is an additive subgroup of R .
2. Since L is cyclic, ∀ p ( x ) ∈ I : x p ( x ) ∈ I .

Hence, I ⊂ R is an ideal, and consequently, L = L I .

Ideal latices

Let f ( x ) ∈ 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:

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

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

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

Definition: 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 ) ∈ Z [ x ] . L I , is a sublattice of Z n , and is defined as:

Rremark:

1. It turns out that GapSVP γ for even small γ = p o l y ( n ) is typically easy on ideal lattices. The intuition is that the algebraic symmetries results 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, S V P γ and S I V P γ are equivalent with a small loss. Furthermore, even for quantum algorithms, S V P γ and S I V P γ 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 average case if S V P γ (where γ = n c for some constant c > 0 ) is hard in worse case scenario.

SISn,m,q,β

Let A ∈ Z q n × m be an n × m matrix with entries in Z q that consists of m uniformly random vectors a i ∈ Z q n : A = [ a 1 | ⋯ | a m ] . Find a nonzero vector x ∈ Z m such that:

It should be noted that a solution to SIS without the required constrain on the length of the solution ( ∥ x ∥ ≤ β ) is easy to compute by using Gaussian elimination technique. We also require β < q , otherwise x = ( q , 0 , … , 0 ) ∈ Z m is a trivial solution.

In order to guarantee f A ( x ) has non-trivial, short solution, we require:

Theorem: For any m = poly ⁡ ( n ) , any β > 0 , and any sufficiently large q ≥ β n c (for any constant c > 0 ), solving S I S n , m , q , β with nonnegligible probability is at least as hard as solving the G a p S V P γ and S I V P γ for some γ = β . O ( n ) 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 R = Z / ( f ( x ) ) with f ( x ) = x n − 1 and x 2 k + 1 , respectively, and extend the definition of norm on vectors in R n to vectors in R m as follows:

Given a vector z → = ( p 1 , … , p m ) ∈ R m where p i ( x ) are some polynomial in R . Consider the embedding coefficient Z -module isomorphism ρ :

Let z i = ρ ( p i ( x ) ) ∈ Z n . Define norm z → as:

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

where α i is the i t h complex root of f ( x ) for i = 1 , … , n .

R-SISm,q,β

Given the quotient polynomial ring R = Z / ( f ( x ) ) , define

R q := R / q R = Z q [ x ] / ( f ( x ) ) . Select m independent uniformly random elements a i ∈ R q . Define vector a → := ( a 1 , … , a m ) ∈ R q m . Find a nonzero vector z → := ( p 1 , … , p m ) ∈ R m such that:

Recall that to guarantee existence of a solution to SIS problem, we require m ≈ 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 ≈ log ⁡ q .

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

When the quotient polynomial ring is R = Z / ( x n + 1 ) for n = 2 k , the ring multiplication a i . p i can be efficiently computed by first forming Rot ⁡ ( a i ) , the nega-circulant matrix of a i , and then multiplying Rot ⁡ ( a i ) with ρ ( p i ( x ) ) ∈ Z n , the embedding coefficient vector of p i (or, alternatively with σ ( p i ( x ) ) ∈ 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 = [ Rot ⁡ ( a 1 ) | ⋯ | Rot ⁡ ( a m ) ] .