# 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 $SIS_{n, m, q, \beta}$ be a Short Integer Solution problem. We define it as such:

Given $m$ uniformly random vectors $a_i∈(\mathbb{Z}/q\mathbb Z)^n$, forming the columns of a matrix $A∈(\mathbb{Z}/q\mathbb Z)^{n×m}$, find a nonzero integer vector $z∈\mathbb{Z}^m$ of norm $‖z‖ ≤β$ (short) such that

$f_A(z) = Az = \sum_i a_i \cdot z_i = 0 \in (\mathbb{Z}/q\mathbb Z)^n \\ z_1\vec{a_1} + z_2\vec{a_2} +...+ z_m\vec{a_m} = 0$

Without the constraint $\beta$ the solution would be as simple as Gaussian elimination. Also we want $\beta < q$ otherwise $z = (q,0, ..., 0) \in \mathbb{Z}^m$ 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 $0$s to $z$ $\Rightarrow$

• big $m \Rightarrow$ easy (the more vectors we are given, the easier the problem becomes)

• big $n \Rightarrow$ 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:

• $n$ is the security parameter. The bigger it is the harder the problem becomes

• $m$ is set depending from application to application. Usually $m \gg n$

• $q = \text{poly}(n)$, think of it as $q = \mathcal{O}(n^2)$

• $\beta =$the bound is set depending on application and $\beta \ll q$

// TODO

# Ajtai's hashing function

• Parameters: $m, n, q \in \mathbb{Z}$, $m > n \log_2 q$

• Key: $A \in (\mathbb{Z}/q\mathbb Z)^{n \times m}$

• Input: $x \in \{0, 1\}^m \Rightarrow$ Short vector

• Output: $\boxed {f_A(x) = Ax \bmod q}$ where $f_A : \{0, 1\}^m \to (\mathbb{Z}/q\mathbb Z)^n$

## Hash function properties:

Compression

We know $x \in \{0, 1\}^m \Rightarrow |\mathcal{X}| = 2^n$ and $Ax \in \mathcal Y = (\mathbb{Z}/q\mathbb Z)^n \Rightarrow |(\mathbb{Z}/q\mathbb Z)^n| = q^n = (2^{\log q})^n$. Since we chose $m > n \log q \Rightarrow |\mathcal{X}| > |\mathcal{Y}|$.

Collision resistance:

halp here

Sage example:

from Crypto.Util.number import long_to_bytes, bytes_to_long​n, 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 Ring​msg = b'msg'x = vector(Zmod(q), [int(i) for i in bin(bytes_to_long(msg))[2:].zfill(m)]) # pad messageprint(len(x)# 40​print(x.parent())# Vector space of dimension 40 over Ring of integers modulo 1009​print(len(A * x))# 20

## Cryptanalysis

Inverting the function:

Given $A$ and $y$ find $x \in \{0, 1\}^m$ such that $Ax = y \bmod q$

Formulating as a lattice problem:

Find arbitrary $t$ such that $At = y \bmod q$

• All solutions to $Ax = y$ are of the form $t + L^{\perp}$ where ${L}^\perp(A) = \{x \in \mathbb{Z}^m : Ax = 0 \in (\mathbb{Z}/q\mathbb Z)^n \}$

• So we need to find a short vector in $t + {L}^{\perp}(A)$

• Equivalent, find $v \in {L}^{\perp}(A)$ closest to $t$ (CVP)

// TODO

# Security Reduction

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