In this section we will study the short integer solution problem and a hashing algorithm that is based on this algorithm.
Short integer solution problem
Definition
Solution existence is based on parameters set. One should think about them as follows:
SIS as a SVP problem
// TODO
Ajtai's hashing function
Hash function properties:
Compression
Collision resistance:
halp here
Sage example:
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 inbin(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
Cryptanalysis
Inverting the function:
Formulating as a lattice problem:
Hermite normal form
// TODO
Security Reduction
If somebody can explain the security bounds and reduction better, please do.
Let SISn,m,q,β be a Short Integer Solution problem. We define it as such:
Given m uniformly random vectors ai∈(Z/qZ)n, forming the columns of a matrix A∈(Z/qZ)n×m, find a nonzero integer vector z∈Zm of norm ‖z‖≤β (short) such that
Without the constraint β the solution would be as simple as Gaussian elimination. Also we want β<q otherwise z=(q,0,...,0)∈Zm would be a fine solution.
Notice that a solution z for A can be converted to a solution for the extension [A∣A′] by appending 0s to z⇒
big m⇒ easy (the more vectors we are given, the easier the problem becomes)
big n⇒ hard (the more dimension we work in the harder the problem becomes)
n is the security parameter. The bigger it is the harder the problem becomes
m is set depending from application to application. Usually m≫n
q=poly(n), think of it as q=O(n2)
β=the bound is set depending on application and β≪q
Parameters: m,n,q∈Z, m>nlog2q
Key: A∈(Z/qZ)n×m
Input: x∈{0,1}m⇒ Short vector
Output: fA(x)=Axmodq where fA:{0,1}m→(Z/qZ)n
We know x∈{0,1}m⇒∣X∣=2n and Ax∈Y=(Z/qZ)n⇒∣(Z/qZ)n∣=qn=(2logq)n. Since we chose m>nlogq⇒∣X∣>∣Y∣.
Given A and y find x∈{0,1}m such that Ax=ymodq
Find arbitrary t such that At=ymodq
All solutions to Ax=y are of the form t+L⊥ where L⊥(A)={x∈Zm:Ax=0∈(Z/qZ)n}