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
For cryptography applications, worst case complexity is not sufficient, and we need to guarantee cryptographic construction are hard based on average case complexity.
is a set of integer linear combinations of
is a matrix having basis vectors in its columns.
Definition: Rotational shift operator on
, and is defined as: Micciancio introduced cyclic lattices in his work in generalizing the compact knapsack problem to arbitrary rings.
Examples:[3] consider the quotient polynomial ring
More precisely, consider a quotient polynomial ring
, and is defined as: Remark:[5] 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
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.
) is easy to compute by using Gaussian elimination technique.
has non-trivial, short solution, we require: Theorem: For any
with nonnegligible probability is at least as hard as solving the
with a high probability in the worst-case scenario.
[2][9] This problem considers a quotient polynomial ring
Of particular interest are cases where there exists integer
as this restricts the quotient to cyclotomic polynomials.
independent uniformly random elements
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
is defined as: When the quotient polynomial ring is
in the SIS problem is restricted to negacirculant blocks:
Like R-SIS, this problem considers the quotient polynomial ring
independent uniformly random elements
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.