1 of 1

Short integer solutions (SIS)

Introduction

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

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

SIS as a SVP problem

// TODO

Ajtai's hashing function

Parameters: ,
Key:
Input: Short vector

Hash function properties:

Compression

We know and . Since we chose .

Collision resistance:

halp here

Sage example:

Cryptanalysis

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)

Hermite normal form

// TODO

Security Reduction

If somebody can explain the security bounds and reduction better, please do.

Resources

+
- page 18

Short integer solutions (SIS)

Introduction

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

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

SIS as a SVP problem

// TODO

Ajtai's hashing function

Parameters: ,
Key:
Input: Short vector

Hash function properties:

Compression

We know and . Since we chose .

Collision resistance:

halp here

Sage example:

Cryptanalysis

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)

Hermite normal form

// TODO

Security Reduction

If somebody can explain the security bounds and reduction better, please do.

Resources

+
- page 18

from Crypto.Util.number import long_to_bytes, bytes_to_long

n, m, q = 20, 40, 1009
set_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 1009
print(A.lift().parent())
# Full MatrixSpace of 20 by 40 dense matrices over Integer Ring

msg = b'msg'
x = vector(Zmod(q), [int(i) for i in bin(bytes_to_long(msg))[2:].zfill(m)]) # pad message
print(len(x)
# 40

print(x.parent())
# Vector space of dimension 40 over Ring of integers modulo 1009

print(len(A * x))
# 20

from Crypto.Util.number import long_to_bytes, bytes_to_long

n, m, q = 20, 40, 1009
set_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 1009
print(A.lift().parent())
# Full MatrixSpace of 20 by 40 dense matrices over Integer Ring

msg = b'msg'
x = vector(Zmod(q), [int(i) for i in bin(bytes_to_long(msg))[2:].zfill(m)]) # pad message
print(len(x)
# 40

print(x.parent())
# Vector space of dimension 40 over Ring of integers modulo 1009

print(len(A * x))
# 20

Short integer solutions (SIS)

hashtagIntroduction

hashtagShort integer solution problem

hashtagSIS as a SVP problem

hashtagAjtai's hashing function

hashtagHash function properties:

hashtagCryptanalysis

hashtagHermite normal form

hashtagSecurity Reduction

hashtagResources

Short integer solutions (SIS)

hashtagIntroduction

hashtagShort integer solution problem

hashtagSIS as a SVP problem

hashtagAjtai's hashing function

hashtagHash function properties:

hashtagCryptanalysis

hashtagHermite normal form

hashtagSecurity Reduction

hashtagResources

Introduction

Short integer solution problem

SIS as a SVP problem

Ajtai's hashing function

Hash function properties:

Cryptanalysis

Hermite normal form

Security Reduction

Resources

Introduction

Short integer solution problem

SIS as a SVP problem

Ajtai's hashing function

Hash function properties:

Cryptanalysis

Hermite normal form

Security Reduction

Resources