Short integer solution (SIS) and ring-SIS problems are two ''average''-case problems that are used in
lattice-based cryptography
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for pos ...
constructions. Lattice-based cryptography began in 1996 from a seminal work by
Miklós Ajtai
Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (dev ...
[Ajtai, Miklós. enerating hard instances of lattice problems.Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996.] 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 In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: L ...
(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
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit a ...
to arbitrary rings.
[Micciancio, Daniele. eneralized 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.] 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 lattices
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