# 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 $$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$$

### SIS as a SVP problem

// 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$$

![](https://3048596314-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MZDWnXlfe2CXv0vGqAA%2F-M_G-TFN1no4S3ObmyHo%2F-M_Hua3xCZFECt_ktYcv%2Fajtai2.svg?alt=media\&token=ec31a6fe-c62c-4401-a594-64f9de55a746)

### 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:**

{% hint style="danger" %}
halp here
{% endhint %}

**Sage example**:

```python
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
```

### 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)

### Hermite normal form

// TODO

## Security Reduction

{% hint style="danger" %}
If somebody can explain the security bounds and reduction better, please do.
{% endhint %}

## Resources

* <https://simons.berkeley.edu/sites/default/files/docs/14967/sis.pdf> + <https://www.youtube.com/watch?v=qZIjVX61NFc&list=PLgKuh-lKre10rqiTYqJi6P4UlBRMQtPn0&index=4>
* <https://crypto.stanford.edu/cs355/18sp/lec9.pdf>
* <https://eprint.iacr.org/2015/939.pdf> - page 18


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.