The Ajtai hash function Over Goldilocks
---
## TL;DR
- Scheme 1 directly build on top of SIS problem. But it has a large input and output space.
- Scheme 2 reduces the input and output space, but the security proof became hard and we probably need a different assumption.

## Scheme 1

The concrete hash function is a map

$$\mathcal{H}: \{0,1\}^{32 \times 1024} \mapsto \mathbb{F}_q^{256}$$
where $q$ is roughly $64$ bits, i.e., Goldilocks.

1. Public parameters
1. Set $\mathcal{R}_{q}:= \mathbb{Z}_{q}[X]/(x^{n} + 1)$ for $q = 2^{64} - 2^{32} + 1$ (i.e., Goldilocks field) and $n = 256$.
2. Sample $m = 4$ random elements from $\mathcal{R}_q$, denoted by $\mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3,\mathbf{b}_4$.

1. Hash a message $m \in \{0,1\}^{32 \times 1024}$
1. parse the input $m$ to $1024$ integers $a_1\dots a_{1024}$ where each $a_i$ is between $0$ and $2^{32}$.
2. define four polynomials $\mathbf{s}_i = \sum_{j=1}^{256} a_{256i+j}X^{j-1}$ for $i\in[0,4)$.
3. compute $\mathbf{c} = \sum_{i=1}^4 \mathbf{s}_i\mathbf{b}_i$
4. let $\mathbf{c}:= \sum_{j=1}^{256} c_{j}X^{j-1}$. Output $d = \{c_j \}_{i=1}^{256}$

### Proof sketch
- preimage resisitence.
Given $\mathbf{c}$, recover $m$ requires one to solve an Inhomogenous SIS problem for $\{\mathbf{b}_1, \mathbf{b}_2, \mathbf{b}_3, \mathbf{b}_4\}$ and $\mathbf{c}$.

- collision resisitence.
Suppose there exists two messages $m$ and $m'$ both hash to $d$. Denote $\mathbf{s}_1,\mathbf{s}_2, \mathbf{s}_3,\mathbf{s}_4$ and $\mathbf{s}_1',\mathbf{s}_2', \mathbf{s}_3',\mathbf{s}_4'$ the corresponding polynomials. Then $\{\mathbf{s}_i - \mathbf{s}_i'\}$ is a solution to SIS problem for $\{\mathbf{b}_1, \mathbf{b}_2, \mathbf{b}_3, \mathbf{b}_4\}$.

- unifomity. Output is unifrom over $\mathbb{F}_q$ via leftover hash lemma.

## Scheme 2
The concrete hash function is a map

$$\mathcal{H}: \{0,1\}^{4096} \mapsto \{0,1\}^{512}$$

which works as follows.

1. Public parameters
1. Set $\mathcal{R}_{q}:= \mathbb{Z}_{q}[X]/(x^{n} + 1)$ for $q = 2^{64} - 2^{32} + 1$ (i.e., Goldilocks field) and $n = 256$.
2. Sample $m = 4$ random elements from $\mathcal{R}_q$, denoted by $\mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3,\mathbf{b}_4$.

1. Hash a message $m \in \{0,1\}^{4096}$
1. parse the input $m$ to $1024$ integers $a_1\dots a_{1024}$ where each $a_i$ is between $0$ and $15$.
2. define four polynomials $\mathbf{s}_i = \sum_{j=1}^{256} a_{256i+j}X^{j-1}$ for $i\in[0,4)$.
3. compute $\mathbf{c} = \sum_{i=1}^4 \mathbf{s}_i\mathbf{b}_i$
4. let $\mathbf{c}:= \sum_{j=1}^{256} c_{j}X^{j-1}$. Output $d = \{c_j \bmod 4\}_{i=1}^{256}$

### Proof sketch
I don't think we can directly build from SIS assumption anymore. We probably need to use Learning with Rounding assumption. Still **work in progress**.

- preimage resisitence.
Given $\mathbf{c}$, recover $m$ requires one to solve an SIS problem for $\{\mathbf{b}_1, \mathbf{b}_2, \mathbf{b}_3, \mathbf{b}_4\}$ and $\mathbf{c}$. There is a gap here though as the attacker is not given $\mathbf{c}$ but $d$.

- collision resisitence.
Suppose there exists two messages $m$ and $m'$ both hash to $d$. Denote $\mathbf{s}_1,\mathbf{s}_2, \mathbf{s}_3,\mathbf{s}_4$ and $\mathbf{s}_1',\mathbf{s}_2', \mathbf{s}_3',\mathbf{s}_4'$ the corresponding polynomials. Suppose $\mathbf{c}:= 4\mathbf{e} + d$ and $\mathbf{c}':= 4\mathbf{e}' + d$ for a same d, where $\mathbf{e}$ and $\mathbf{e}'$'s infinity norm are bounded by $q/8$, then
$$\mathbf{c}-\mathbf{c}'=4(\mathbf{e}-\mathbf{e}')
$$

- unifomity.
A random $\mathbb{F}_q$ element mod $4$ is biased with $2^{-16}$~ish probability. We can argue the overall result is statisically close to uniform.

# old material

## TL;DR

This blog presents an old hash function, the Ajtai hash function, over the Goldilocks field. It is efficient to compute, and has a small circuit size. It has a __security proof__ to the so-called short integer solution problem over the rings; it is also plausible __quantum-safe__. All those property makes it a perfect alternative to the widely used Poseidon hash function.

__Caution__: A lot things here are still very preliminary...

## Motivation

Algebric hash functions, or better known as zero-knowledge friendly, or circuit friendly hash functions, are an important building blocks in zero-knowledge proof applications. They maps arbitrary length prime field elements into constant length prime field elements, i.e., $\mathbb{F}_q^* \mapsto \mathbb{F}_q^c$. This differs from standard hash functions such as SHA2, where both input and output domain are binary. The fact that the input, output and the internal states of zk-friendly hash functions are field elements makes them very expressible in zk circuits. Typically, a poseidon hash function can be expressed within hundreds of witnesses, whereas a keccak hash function requires over 15k witnesses.

In cryptography, a security proof is a reduction of the primitive's security to some hard mathmatically problem. If the primitive is broken, then the underly mathmatical problem is broken. For example, if one is able to forge an ECDSA signature, then there must exist an efficient solver to the discrete logartihm problem over the Ellipitic curve.

Most of the hash functions do not come with a security proof. They rely on extensive cryptanalysis and heuritics. There is a tinny chance that the hash function is not secure.

[Code](https://github.com/zhenfeizhang/Goat-hash)

$$\mathcal{H}: \mathcal{R}_{t}\times\mathcal{R}_{t}\times\mathcal{R}_{t}\times\mathcal{R}_{t}\mapsto \mathcal{R}_q$$

with parameters

| q | n | m | t |
|:-----:|--------|--------|--------|
|`0xffffffff00000001` | 256 | 4 | 16 |

where
$\mathcal{R}_{t}:= \mathbb{Z}_{t}[X]/(x^{n} + 1)$ and $\mathcal{R}_{q}:= \mathbb{Z}_{q}[X]/(x^{n} + 1)$ for $q = 2^{64} - 2^{32} + 1$ (i.e., Goldilocks field).

The hash function is defined as

- Setup: $\forall i \in [0,4), a_i \gets_R \mathcal{R}_q$
- Hashing messages $m_1, m_2, m_3, m_4\in\mathcal{R}_{16}$
$$\mathcal{H}({\bf m}) = a_1 m_1 + a_2 m_2 + a_3m_3 + a_4m_4 \in \mathcal{R}_q$$

Padding: we need to be careful about the input message. When the message does not fully fill ${R}_{16}^4$, extra cautions need to be taken about padding. We may parse the message as a vector of 4 bits elements, and pad with `t` to achieve a dimension of `256 * 4 = 1024`, and then parse the vector as 4 $\mathcal{R}_t$ elements.

# Performance
## native cost
Single thread, none optimized. Poseidon over Goldilocks with width = 12.

poseidon hash cost 5.142µs
goat hash cost 11.846µs 

## in circuit cost
Metric: multiplication gates
- Poseidon:
- Partial S-box takes 4 muls
- Full S-box takes 48 muls
- Permutation takes 144 muls (may accelerate with NTT muls)
- total costs 22 partial rounds * 4 + 8 full rounds * 48 + 30 total rounds * 144 = `4792` muls

- Goat
- requires 4 forward NTT and 1 backward NTT which adds up to `10496` muls
- forward NTT: converting a single poly into NTT poly takes `n * log n = 2048` muls
- backward NTT: converting a single NTT poly into normal poly takes `n * log n + n = 2304` muls
- requires additionally 4 NTT multiplications which takes `4 n = 1024` muls
- total cost `10496 + 1024 = 11520` muls

- Sanity check:
- 11520/4792 ~ 2.4
- 11.85/5.15 ~ 2.3