Problem: A new algebraic hash function

(Proposer: Jordi Baylina)

Can you find a collision for the following hash function?

Let $p = 2^{64} - 2^{32} + 1$; this number is prime.

Our hash function $H: \mathbb{F}_p^8 \rightarrow \mathbb{F}_p^4$ is defined as follows.

$H$ is built as a composition of 30 “rounds”. Each “round” $f_i$ is a function $f_i: \mathbb{F}_p^{12} \rightarrow \mathbb{F}_p^{12}$. To compute $H(x_1, \ldots, x_8)$:

• pad the input with four 0’s to form $(x_1, \ldots, x_8, 0, 0, 0, 0)$;
• apply the round functions $f_1, \ldots, f_{30}$ in succession; and
• return the first four entries of the output vector.

Of the 30 rounds, the first 4 and last 4 rounds are “full rounds”. The 22 intermediate rounds are “partial rounds”.

Each full round takes an input vector $(v_1, \ldots, v_{12})$, and:

• adds a constant vector $b_i$ to $v$ (the vector $b_i$ is different in each round)
• raises each entry of $v$ to the 7th power $(x_1, x_2, x_3, \ldots, x_{12}) \mapsto (x_1^7, x_2^7, x_3^7, \ldots, x_{12}^7)$
• applies a linear transformation (i.e. a 12-by-12 matrix $M$) to $v$ (the vector $M$ is the same in each round).

A partial round is the same as a full round, except that the second step only raises the first entry of $v$ to the 7th power: $(x_1, x_2, x_3, \ldots, x_{12}) \mapsto (x_1^7, x_2, x_3, \ldots, x_{12})$.

Motivation and discussion

We want hash functions that can be evaluated efficiently inside a STARK. This means the function should be made of algebraic operations in the field $\mathbb{F}_{p}$, where $p \approx 2^{64}$ is the prime mentioned above.

The Poseidon hash function is a SNARK-friendly algebraic hash function, but it is designed for a prime field with $p \approx 2^{256}$.

For collision-resistance, we need the hash values to be at least $256$ bits. Working over a 64-bit field, this means the hash should output 4 field elements, rather than 1.

This new hash function, like Poseidon, is composed of a succession of “rounds”, each a composition of a linear function with a low-degree polynomial nonlinearity.