In this section we will study the short integer solution problem and a hashing algorithm that is based on this algorithm.
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
Input: Short vector
We know and . Since we chose .
from Crypto.Util.number import long_to_bytes, bytes_to_longn, m, q = 20, 40, 1009set_random_seed(1337)A = random_matrix(Zmod(q),n, m)print(A.parent())# Full MatrixSpace of 20 by 40 dense matrices over Ring of integers modulo 1009print(A.lift().parent())# Full MatrixSpace of 20 by 40 dense matrices over Integer Ringmsg = b'msg'x = vector(Zmod(q), [int(i) for i in bin(bytes_to_long(msg))[2:].zfill(m)]) # pad messageprint(len(x)# 40print(x.parent())# Vector space of dimension 40 over Ring of integers modulo 1009print(len(A * x))# 20
Inverting the function:
Given and find such that
Formulating as a lattice problem:
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)
https://eprint.iacr.org/2015/939.pdf - page 18