Short integer solutions (SIS)
Last updated
Last updated
In this section we will study the short integer solution problem and a hashing algorithm that is based on this algorithm.
Definition
Let be a Short Integer Solution problem. We define it as such:
Given uniformly random vectors , forming the columns of a matrix , find a nonzero integer vector of norm (short) such that
Without the constraint the solution would be as simple as Gaussian elimination. Also we want otherwise would be a fine solution.
Notice that a solution for can be converted to a solution for the extension by appending s to
big easy (the more vectors we are given, the easier the problem becomes)
big hard (the more dimension we work in the harder the problem becomes)
Solution existence is based on parameters set. One should think about them as follows:
is the security parameter. The bigger it is the harder the problem becomes
is set depending from application to application. Usually
, think of it as
the bound is set depending on application and
// TODO
Compression
Collision resistance:
halp here
Sage example:
Inverting the function:
Formulating as a lattice problem:
// TODO
If somebody can explain the security bounds and reduction better, please do.
https://eprint.iacr.org/2015/939.pdf - page 18
Parameters: ,
Key:
Input: Short vector
Output: where
We know and . Since we chose .
Given and find such that
Find arbitrary such that
All solutions to are of the form where
So we need to find a short vector in
Equivalent, find closest to (CVP)