# Hades-based POSEIDON$$^\pi$$ permutation design

Recall in the previous section, the $$\mathsf{Poseidon}^\pi$$ permutation is a composition of round functions, each of which consists of $$3$$ components such as $$AddroundConstants$$, $$SubWords$$, and $$MixLayer$$, each takes input a state $$S=(S_1,S_2,\dots,S_t)$$ and produces a new state $$S'$$. In this Section, we describe the $$3$$ main components of the round function of $$\mathsf{Poseidon}^\pi$$.

## Notation

The function takes input of $$t \geq 2$$ words in $$\mathbb{F}_p$$, where $$p$$ is a prime of size $$p \approx 2^n > 2^{30}$$ and $$N = nt$$ to denote the size of texts in bits.

This is the first component of the round function described in Hades design strategy. Given the input state $$S = ( S_1, S_2, \cdots, S_t )$$, where each of $$S_i$$ is a word, it outputs $$S' = AddRoundConstants(S, T) = S + T = ( S_1 + T_1, S_2 + T_2, \dots, S_t + T_t )$$ where $$T$$ is the round constant vector that is randomly generated in a method described in Poseidon concrete instantiation. Essentially, this component performs a field addition between the state and the round constant.

## The SubWords (SBox) layer

This is the second component of the round function described in Hades design strategy. Subtitution boxes (or S-Boxes) are widely used in cryptography. In this context of an architecture that resembles block ciphers, SBoxes are used to ensure Shannon's property of confusion.

Given the state $$S = ( S_1, S_2, \cdots, S_t )$$, where each of $$S_i$$ is a word, this component outputs a new state $$S' = SB(S) = ( SB(S_1), SB(S_2), \dots, SB(S_t) ).$$ Essentially, this component performs multiple field multiplications on the state.

In [GKRRS21], the authors focus on the setting: $$SB(x) = x^\alpha, \alpha \geq 3$$ where $$\alpha$$ is the smallest positive integer that satisfies $$gcd(\alpha, p - 1) = 1$$. These permutations are called "$$x^\alpha-Poseidon^\pi$$".

Specifically, they use:

• $$\alpha = 3$$ if $$p \not\equiv 1 \pmod{3}$$
• $$\alpha = 5$$ if $$p \equiv 1 \pmod{3}$$ and $$p \not\equiv 1 \pmod{5}$$

It turns out that $$\alpha = 5$$, which is $$SB(x) = x^5$$, is suitable for the prime subfields of the scalar field of BLS12-381 and BN254, which are two of the most popular prime fields in ZK applications.

## MixColumns - The linear layer

This is the last layer (also called the linear layer) of the round function. Given the state $$S = ( S_1, S_2, \cdots, S_t )$$. This layer outputs the new state $$S' = \mathcal{M} \times S = \begin{bmatrix} \mathcal{M}_{11} & \mathcal{M}_{12} & \dots & \mathcal{M}_{1t} \\ \mathcal{M}_{21} & \mathcal{M}_{22} & \dots & \mathcal{M}_{2t} \\ \dots & \dots & \ddots & \dots \\ \mathcal{M}_{t1} & \mathcal{M}_{t2} & \dots & \mathcal{M}_{tt} \end{bmatrix} \times \begin{bmatrix} S_1 \\ S_2 \\ \dots \\ S_t \end{bmatrix}$$ where $$\mathcal{M}$$ is the secure Maximum Distance Separable matrix of size $$t \times t$$, which is explained in the Hades design strategy. The MDS matrices are randomly and securely generated using a method described in Poseidon concrete instantiations.

It is proved [MS78] that a $$t \times t$$ MDS matrix with elements in $$\mathbb{F}_p$$ exists if $$2t + 1 \leq p$$.

One method of constructing such a matrix introduced in this paper is using a Cauchy matrix. For $$(x_i, y_i) \in \mathbb{F}_p$$, where $$i \in [1, t]$$, the entries of the matrix $$\mathcal{M}$$ are: $$\mathcal{M}_{i, j} = \dfrac{1}{x_i + y_j}$$ where the entries of $$\{x_i\}_{1 \leq i \leq t}$$ and $$\{y_i\}_{1 \leq i \leq t}$$ are pairwise distinct and $$x_i + y_i \neq 0$$, where $$i \in \{1,\cdots,t\}$$ and $$j \in \{1,\cdots,t\}$$

## Constructing the matrix

The paper suggest the following method to generate matrices to avoid some known vulnerabilities which this note skipped:

• Randomly select pairwise distinct $$\{x_i\}_{1 \leq i \leq t}$$ and $$\{y_i\}_{1 \leq i \leq t}$$ where $$x_i + y_j \neq 0$$ and where $$i \in \{ 1,\cdots,t \}$$ and $$j \in \{ 1,\cdots,t \}$$.
• Determine if the matrix is secure using this test introduced in [GRS20]
• Repeat this procedure until we find a secure matrix.