11institutetext: Alpen-Adria-Universität Klagenfurt, Universitätsstraße 65-67,
9020 Klagenfurt am Wörthersee, Austria
11email<EMAIL_ADDRESS>22institutetext: Technische Universität
Wien, Karlsplatz 13, 1040 Wien, Austria
22email<EMAIL_ADDRESS>
#  Arion: Arithmetization-Oriented Permutation and Hashing from Generalized
Triangular Dynamical Systems

Arnab Roy 11 Matthias Johann Steiner 11 Stefano Trevisani 22

###### Abstract

In this paper we propose the (keyed) permutation Arion and the hash function
ArionHash over $\mathbb{F}_{p}$ for odd and particularly large primes. The
design of Arion is based on the newly introduced Generalized Triangular
Dynamical System (GTDS), which provides a new algebraic framework for
constructing (keyed) permutation using polynomials over a finite field. At
round level Arion is the first design which is instantiated using the new
GTDS. We provide extensive security analysis of our construction including
algebraic cryptanalysis (e.g. interpolation and Gröbner basis attacks) that
are particularly decisive in assessing the security of permutations and hash
functions over $\mathbb{F}_{p}$. From an application perspective, ArionHash
aims for efficient implementation in zkSNARK protocols and Zero-Knowledge
proof systems. For this purpose, we exploit that CCZ-equivalence of graphs can
lead to a more efficient implementation of Arithmetization-Oriented
primitives.

We compare the efficiency of ArionHash in R1CS and Plonk settings with other
hash functions such as Poseidon, Anemoi and Griffin. For demonstrating the
practical efficiency of ArionHash we implemented it with the zkSNARK libraries
libsnark and Dusk Network Plonk. Our result shows that ArionHash is
significantly faster than Poseidon \- a hash function designed for zero-
knowledge proof systems. We also found that an aggressive version of ArionHash
is considerably faster than Anemoi and Griffin in a practical zkSNARK setting.

##  1 Introduction

With the advancement of Zero-Knowledge (ZK), Multi-Party Computation (MPC) and
Fully Homomorphic Encryption (FHE) in recent years new efficiency measures for
symmetric-key primitives allowing efficient implementation in these schemes,
namely low multiplicative complexity and low multiplicative depth, have been
introduced. The block ciphers, permutations and hash functions with low
multiplicative complexity are also referred to as Arithmetization-Oriented
(AO) primitives. A significant number of these new types of AO primitives are
defined over large finite fields of prime order $p\ggg 2$ for target
applications. Our focus in this paper will be such a low multiplicative
complexity construction over $\mathbb{F}_{p}$ for large primes. Some generic
definitions and results in this paper are applicable to any odd prime, thus we
describe these results and definitions accordingly. However, the security of
the construction(s) will be analyzed only for large primes.

To put this paper into context with previous AO constructions we give a short
overview of their developments. The AO primitives proposed in the literature
until now can be categorized into three generations.

  1. Gen I:

LowMC [3], MiMC [2]

  2. Gen II:

Hades [34], Poseidon [33], GMiMC [1], Rescue-Prime [4]

  3. Gen III:

Reinforced Concrete [32], Griffin [31], Anemoi [16], Arion (this paper)

The first generation consists of constructions which demonstrated that one can
construct secure and efficient ciphers and hash functions with low degree
primitives at round level. In particular, LowMC introduced the partial
Substitution Permutation Network (SPN) strategy in AO.

In the second generation researchers tried to obtain further efficiency
improvements from Feistel and (partial) SPNs to obtain new efficient
primitives. Moreover, more focus was given on constructions native in large
prime fields $\mathbb{F}_{p}$ rather than $\mathbb{F}_{2^{n}}$. This resulted
in Hades which combines full and partial SPNs over $\mathbb{F}_{p}$, and its
derived sponge function Poseidon which is now a widely deployed hash function
for ZK applications.

The current third generation adopts new design principles which neither reduce
to the Feistel nor the SPN that culminated in the Generalized Triangular
Dynamical System (GTDS) [48]. Moreover, this generation diverted from the
consensus that one needs low degree polynomials to instantiate a secure and
efficient AO primitive.

In this paper we propose new AO primitives - Arion (block cipher) and the hash
function derived from it ArionHash. At round level Arion (and ArionHash) like
Griffin, utilize(s) a polynomial of very high degree in one branch and low
degree polynomials in the remaining branches to significantly cut the number
of necessary rounds compared to the previous generations. Anemoi also utilizes
a high degree permutation, the so-called open Flystel, at round level, but to
limit the number of constraints in a prover circuit the authors proved that
the open Flystel is CCZ-equivalent (cf. [19] and [16, §4.2]) to a low degree
function, the so-called closed Flystel. Lastly, Reinforced Concrete is the
first AO hash function that utilizes look-up tables which significantly
reduces the number of necessary rounds of Reinforced Concrete and consequently
also the number of constraints in a prover circuit.

###  1.1 Our Results

In this paper we propose the block cipher Arion and the hash function
ArionHash (Section 2), using the Generalized Triangular Dynamical System [48].
The block cipher and hash function are constructed over $\mathbb{F}_{p}$ with
the target to achieve low multiplicative complexity in a prover circuit.
Utilizing the structure of GTDS enables us to provide a systematic security
analysis of the newly proposed block cipher and hash function. The GTDS
structure also allows us to choose the best suited parameters for the
efficiency. We provide extensive security analysis of the proposed block
cipher and hash function against state-of-the-art cryptanalysis techniques to
justify their security (Section 3). Our construction validates the soundness
of the generic GTDS structure that uses polynomial dynamical system for
constructing cryptographic permutations over finite fields.

Although Arion and ArionHash are defined on arbitrary finite fields
$\mathbb{F}_{p}$, the parameters of the block cipher and hash function are
chosen in such way to be compatible with the primes chosen for the target ZK
application namely, for $\text{BLS}12$ and $\text{BN}254$ curves. We propose
aggressive versions of Arion and ArionHash namely, -Arion and -ArionHash. The
difference between Arion (and ArionHash) and its aggressive version is that
the former avoids a recently proposed probabilistic Gröbner basis [27] attack
(Section 3.2 and Appendix C in the full version of the paper [49]).

To demonstrate and compare the efficiencies of our constructions (Section 4)
we implemented them using the zkSNARK libraries libsnark [50], a `C++` library
used in the privacy protecting digital currency Zcash [35], and Dusk Network
Plonk [23], a `Rust` library used in the privacy-oriented blockchain protocol
Dusk. Our results show that ArionHash is significantly (2x) faster than
Poseidon \- an efficient hash function designed for zkSNARK applications. The
efficiency of ArionHash is comparable to the recently proposed (but not yet
published at a peer-reviewed venue) hash functions Anemoi and Griffin. We find
that -ArionHash for practical choices of parameters in a Merkle tree mode of
hashing is faster than Griffin. We also reveal that CCZ-equivalence between
the graphs of the ArionHash GTDS and another closely related GTDS leads to a
more efficient implementation of ArionHash in ZK applications compared to the
naive circuit for ArionHash (Section 4.1).

Our public GitHub repository

https://github.com/sca-research/Arion

contains reference implementations in `SageMath`, `C++` and `Rust`, our
`OSCAR` implementation to perform Gröbner basis experiments, and our
`SageMath` code to estimate the security levels of Arion & ArionHash.

##  2 The (Keyed) Permutation and Hash Function

###  2.1 Overview of the Design Rationale

Before we define Arion and ArionHash, we quickly summarize the design
rationale behind our construction.

  * •

By utilizing the GTDS to instantiate the permutation we aim to achieve fast
degree growth in each component like in SPNs and non-linear mixing between the
components as in Feistel network. Our GTDS, see Theorem 2.1, incorporates the
strength of both SPN and Feistel in a single primitive at round level.

  * •

It follows from the generic security analysis in [48, §5] that the univariate
permutations, the SPN part, of the GTDS determine worst case security bounds
against differential and linear cryptanalysis. Hence, we chose parameters that
minimize these bounds.

  * •

To thwart interpolation attacks we opted for a design that can achieve a
degree overflow in the input variables in the first round, see Theorem 2.2 and
Table 2. This is achieved in the SPN part of the GTDS by applying a low degree
univariate permutation polynomial $p_{1}$ in all branches except the last one
and by applying a high-degree inverse permutation $p_{2}^{-1}$ in the last
branch.

  * •

We opted for a linear layer that mixes all branches in every round. This is
achieved with a circulant matrix which has only non-zero entries.

  * •

For the high degree inverse permutation, the naive circuit for
$p_{2}^{-1}(x)=y$ introduces many multiplicative constraints, though one can
always transform such a circuit into a circuit for $x=p_{2}(y)$ in constant
time, see Section 4.1. This trick plays a fundamental role in the efficiency
of ArionHash circuits.

###  2.2 Keyed Permutation

We start with the definition of the generalized triangular dynamical system of
Arion.

######  Definition 2.1 (GTDS of Arion)

Let $p\in\mathbb{Z}_{>4}$ be a prime, and let $\mathbb{F}_{p}$ be the field
with $p$ elements. Let $n,d_{1},d_{2},e\in\mathbb{Z}_{>1}$ be integers such
that

  1. (i)

$d_{1}$ is the smallest positive integer such that
$\gcd\left(d_{1},p-1\right)=1$,

  2. (ii)

$d_{2}$ is an arbitrary integer such that $\gcd\left(d_{2},p-1\right)=1$, and

  3. (iii)

$e\cdot d_{2}\equiv 1\mod p-1$.

For $1\leq i\leq n-1$ let
$\alpha_{i,1},\alpha_{i,2},\beta_{i}\in\mathbb{F}_{p}$ be such that
$\alpha_{i,1}^{2}-4\cdot\alpha_{i,2}$ is a quadratic non-residue modulo $p$.
The generalized triangular dynamical system
$\mathcal{F}_{\textsf{Arion}}=\\{f_{1},\dots,f_{n}\\}$ of Arion is defined as

$\begin{split}f_{i}(x_{1},\dots,x_{n})&=x_{i}^{d_{1}}\cdot
g_{i}(\sigma_{i+1,n})+h_{i}(\sigma_{i+1,n}),\qquad 1\leq i\leq n-1,\\\
f_{n}(x_{1},\dots,x_{n})&=x_{n}^{e},\end{split}$

where

$\begin{split}g_{i}(x)&=x^{2}+\alpha_{i,1}\cdot x+\alpha_{i,2},\\\
h_{i}(x)&=x^{2}+\beta_{i}\cdot x,\\\
\sigma_{i+1,n}&=\sum_{j=i+1}^{n}x_{j}+f_{j}(x_{1},\dots,x_{n}).\end{split}$

Note that the GTDS $\mathcal{F}=\\{f_{1},\dots,f_{n}\\}$ must be considered as
ordered tuple of polynomials since in general the order of the $f_{i}$’s
cannot be interchanged. Since $\alpha_{i,1}^{2}-4\cdot\alpha_{i,2}$ is a non-
residue modulo $p$ for all $1\leq i\leq n-1$ the polynomials $g_{i}$ do not
have any zeros over $\mathbb{F}_{p}$, therefore we can invert the GTDS with
the procedure described in [48, Proposition 8, Corollary 9]. In Table 1 we
propose suitable exponents for $d_{2}$ which can be evaluated with at most $9$
multiplications.

All exponents are chosen so that Arion and ArionHash provide at least 128 bit
security against Gröbner basis attacks while minimizing the number of
multiplicative constraints in a prover circuit, see Sections 3.2 and 4.1.

Table 1: Efficient evaluation of exponents
$d_{2}\in\\{121,123,125,129,161,193,195,257\\}$.

$d_{2}$ |  Evaluation chain |  Number of Multiplications
---|---|---
$121$ |  $y=\left(x^{2}\right)^{2}$, $z=\left(y^{2}\cdot y\right)^{2}$, $x^{121}=\left(z^{2}\right)^{2}\cdot z\cdot x$ |  $9$
$123$ |  $y=x^{2}\cdot x$, $z=\left(\left(y^{2}\right)^{2}\right)^{2}$, $x^{123}=\left(z^{2}\right)^{2}\cdot z\cdot y$ |  $9$
$125$ |  $y=\left(x^{2}\right)^{2}\cdot x$, $z=\left(\left(y^{2}\right)^{2}\right)^{2}$, $x^{125}=z^{2}\cdot z\cdot y$ |  $9$
$129$ |  $y=\left(\left(\left(x^{2}\right)^{2}\right)^{2}\right)^{2}$, $z=\left(\left(y^{2}\right)^{2}\right)^{2}$, $x^{129}=z\cdot x$ |  $8$
$161$ |  $y=\left(x^{2}\right)^{2}\cdot x$, $z=\left(\left(y^{2}\right)^{2}\right)^{2}$, $x^{161}=\left(z^{2}\right)^{2}\cdot x$ |  $9$
$193$ |  $y=\left(x^{2}\right)\cdot x$, $z=\left(\left(\left(y^{2}\right)^{2}\right)^{2}\right)^{2}$, $x^{193}=\left(z^{2}\right)^{2}\cdot x$ |  $9$
$195$ |  $y=\left(x^{2}\right)\cdot x$, $z=\left(\left(\left(y^{2}\right)^{2}\right)^{2}\right)^{2}$, $x^{195}=\left(z^{2}\right)^{2}\cdot y$ |  $9$
$257$ |  $y=\left(\left(\left(x^{2}\right)^{2}\right)^{2}\right)^{2}$, $z=\left(\left(\left(y^{2}\right)^{2}\right)^{2}\right)^{2}$, $x^{257}=z\cdot x$ |  $9$

Let us compute the degrees of the polynomials in the GTDS.

###### Lemma 2.2

Let $n,d_{1},e\geq 1$ be integers, and let
$\mathcal{F}_{\textsf{Arion}}=\\{f_{1},\dots,f_{n}\\}$ be an Arion GTDS. Then

$\deg\left(f_{i}\right)=2^{n-i}\cdot(d_{1}+e)-d_{1}.$

###### Proof

We perform an upwards induction, for $n$ and $n-1$ the claim is clear. Suppose
the claim is true for indices greater than or equal to $i$, i.e.
$\deg\left(f_{i}\right)=\deg\left(f_{i}\right)=2^{n-i}\cdot(d_{1}+e)-d_{1}$.
By construction, the leading monomial of $f_{i-1}$ is the leading term of the
polynomial $x_{i-1}^{d_{1}}\cdot f_{i}^{2}$. Thus,

$\displaystyle\deg\left(f_{i-1}\right)$
$\displaystyle=\deg\left(x_{i-1}^{d_{1}}\cdot
f_{i}^{2}\right)=d_{1}+2\cdot\left(2^{n-i}\cdot(d_{1}+e)-d_{1}\right)$
$\displaystyle=2^{n-(i-1)}\cdot(d_{1}+e)-d_{1},$

which proves the claim. ∎

To introduce mixing between the blocks we chose a circulant matrix whose
product with a vector can be efficiently evaluated.

######  Definition 2.3 (Affine layer of Arion)

Let $p\in\mathbb{Z}$ be a prime and let $\mathbb{F}_{p}$ be the field with $p$
elements. The affine layer of Arion is defined as

$\mathcal{L}_{\mathbf{c}}:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n},\quad\mathbf{x}\mapsto\operatorname{circ}\left(1,\dots,n\right)\mathbf{x}+\mathbf{c},$

where $\operatorname{circ}\left(1,\dots,n\right)\in\mathbb{F}_{p}^{n\times n}$
is the circulant matrix111 We shortly recall the definition of (right)
circulant matrices: Let $k$ be a field and let
$\mathbf{v}=(v_{1},\dots,v_{n})\in k^{n}$, then the circulant matrix of
$\mathbf{v}$ is defined as
$\operatorname{circ}(\mathbf{v})=\begin{pmatrix}v_{1}&v_{2}&\ldots&v_{n-1}&v_{n}\\\
v_{n}&v_{1}&\ldots&v_{n-2}&v_{n-1}\\\ &&\ddots&&\\\
v_{2}&v_{3}&\ldots&v_{n}&v_{1}\end{pmatrix}.$ with entries $1,\dots,n$ in the
first row and $\mathbf{c}\in\mathbb{F}_{p}^{n}$ is a constant vector.

###### Remark 2.4

For any prime number $p\in\mathbb{Z}$ with $p>130$ and $n=2,3,4$ the matrix
$\operatorname{circ}\left(1,\dots,n\right)$ is a MDS matrix over
$\mathbb{F}_{p}$.

The following algorithm provides an efficient way to evaluate the matrix-
vector product for $\operatorname{circ}\left(1,\dots,n\right)$.

Algorithm 1 Efficient evaluation of matrix-vector product

1:Input

2:
$\mathbf{v}=\left(v_{1},\dots,v_{n}\right)^{\intercal}\in\mathbb{F}_{p}^{n}$

3:Output

4: $\operatorname{circ}\left(1,\dots,n\right)\mathbf{v}\in\mathbb{F}_{p}^{n}$

5:Initialize $\mathbf{w}=\left(0,\dots,0\right)\in\mathbb{F}_{p}^{n}$.

6:Compute $\sigma=\sum_{i=1}^{n}v_{i}$ and set
$w_{1}=\sigma+\sum_{i=1}^{n}(i-1)\cdot v_{i}$.

7:Set $i=2$.

8:while $i\leq n$ do

9: Set $w_{i}=w_{i-1}-\sigma+n\cdot v_{i-1}$.

10: $i=i+1$.

11:return $\mathbf{w}$

To define a keyed permutation we need a key addition which we denote as

$\mathcal{K}_{\mathbf{k}}:\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n},\qquad(\mathbf{x},\mathbf{k})\mapsto\mathbf{x}+\mathbf{k}.$

The keyed permutation Arion is now defined as follows.

######  Definition 2.5 (Arion)

Let $p\in\mathbb{Z}$ be a prime and let $\mathbb{F}_{p}$ be the field with $p$
elements, and let $n>1$ and $r\geq 1$ be integers. For $1\leq i\leq r$ let
$\mathcal{F}^{(i)}_{\textsf{Arion}}:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$
be an Arion GTDS and for $1\leq i\leq r$ let
$\mathcal{L}_{\mathbf{c}_{i}}:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$ be
affine layers from Theorem 2.3. The $i$th round function of Arion is defined
as

$\begin{split}\mathcal{R}_{\mathbf{k}}^{(i)}:\mathbb{F}_{p}^{n}&\times\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n},\\\
\left(\mathbf{x},\mathbf{k}\right)&\mapsto\mathcal{K}_{\mathbf{k}}\circ\mathcal{L}_{\mathbf{c}_{i}}\circ\mathcal{F}^{(i)}_{\textsf{Arion}}\left(\mathbf{x}\right).\end{split}$

Then Arion is defined as the following composition

$\begin{split}\textsf{Arion}:\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n\times(r+1)}&\to\mathbb{F}_{p}^{n},\\\
\big{(}\mathbf{x},\mathbf{k}_{0},\mathbf{k}_{1},\dots,\mathbf{k}_{r}\big{)}&\mapsto\mathcal{R}_{\mathbf{k}_{r}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}_{1}}^{(1)}\circ\mathcal{L}_{\mathbf{0}}\circ\mathcal{K}_{\mathbf{k}_{0}}\left(\mathbf{x}\right).\end{split}$

Further, we denote with Arion\- the unkeyed permutation, i.e. Arion is
instantiated with the key $\mathbf{k}_{0}=\ldots=\mathbf{k}_{r}=\mathbf{0}$.

Since our final aim is to construct a hash function using the Arion-, we
analyze Arion only for keys $\mathbf{k}_{j}=\mathbf{k}$, where
$\mathbf{k}\in\mathbb{F}_{p}^{n}$, in every round. We do not give any key
scheduling algorithm for keys whose sizes are larger than the block size.
Instantiation of Arion with such a key is not the main topic of this paper.

###  2.3 Hash Function

For the hash function ArionHash over $\mathbb{F}_{p}^{n}$ we instantiate
Arion\- in sponge mode [9, 10]. The state size $n=r+c$ is split into the rate
part $r$ and the capacity part $c$. In [10, Theorem 2] it has been proven that
for a random permutation the sponge construction is indistinguishable from a
random oracle up to $\min\left\\{p^{r},p^{c/2}\right\\}$ queries. Therefore,
to provide $\kappa$ bits of security, $p^{r}\geq 2^{\kappa}$ and $p^{c/2}\geq
2^{\kappa}$, we require that

$r\geq\frac{\kappa}{\log_{2}\left(p\right)},\qquad\text{and}\qquad
c\geq\frac{2\cdot\kappa}{\log_{2}\left(p\right)}.$ (1)

Given an input message $m$ we choose a similar padding rule as for Poseidon
[33, §4.2], we add the smallest number of zeros $<r$ such that the size of
$m\mid\mid 0^{\ast}$ is a multiple of $r$. If we have to pad the message, then
we replace the initial value $\texttt{IV}\in\mathbb{F}_{p}^{c}$ with
$|m|\mid\mid\texttt{IV}^{\prime}\in\mathbb{F}_{p}^{c}$, where
$|m|\in\mathbb{F}_{p}$ is the size of the input message $m$ and
$\texttt{IV}^{\prime}\in\mathbb{F}_{p}^{c-1}$ is an initial value.

###  2.4 Instantiations

Target primes for Arion & ArionHash are the $250$ bit prime numbers
$\text{BLS}12$ and $\text{BN}254$222
${\scriptstyle\text{BLS}12=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001}$,
${\scriptstyle\text{BN}254=0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001}$..
Since degree growth of the Arion GTDS is dominated by the power permutation in
the bottom component we list the smallest integer $m\in\mathbb{Z}$ such that
$m\cdot e\geq p$ in Table 2.

Table 2: Smallest positive integer so that $m\in\mathbb{Z}$ such that $m\cdot e\geq p$ for $\text{BLS}12$ and $\text{BN}254$. | $\left\lceil p/e\right\rceil$
---|---
$d_{2}$ |  $\text{BLS}12$ |  $\text{BN}254$
$121$ |  n.a. |  $3$
$123$ |  n.a. |  n.a.
$125$ |  $3$ |  $2$
$129$ |  n.a. |  n.a.
$161$ |  $3$ |  $4$
$193$ |  $13$ |  $3$
$195$ |  n.a. |  n.a.
$257$ |  $3$ |  $2$

Therefore, by Theorem 2.2 for $n=3$ and all exponents except $d_{2}=193$ the
Arion GTDS surpasses degree $p$ in the first component.

In Table 3 we provide the parameters for Arion and ArionHash and their
aggressive versions -Arion and -ArionHash with $d_{1},d_{2}\in\mathbb{Z}$ such
that $\gcd\left(d_{i},p-1\right)=1$, $d_{1}=3,5$ and $121\leq d_{2}\leq 257$.
The number of rounds for Arion and ArionHash are chosen to provide 128 bit
security against the most efficient probabilistic algorithm (available till
date) for polynomial system solving in a Gröbner basis attack on ArionHash.
Since $2^{\frac{250}{2}}=2^{125}$ we consider all possible rate-capacity pairs
$n=c+r$ suitable for ArionHash over $\text{BLS}12$ and $\text{BN}254$. As hash
output of ArionHash over $\text{BLS}12$ and $\text{BN}254$ we recommend to use
a single $\mathbb{F}_{p}$ element.

Table 3: Arion, ArionHash, -Arion and -ArionHash parameters over primes $p\geq 2^{250}$ with $d_{1},d_{2}\in\mathbb{Z}$ such that $\gcd\left(d_{i},p-1\right)=1$ and $121\leq d_{2}\leq 257$ and 128 bit security. | Rounds
---|---
Blocks |  Arion & ArionHash |  -Arion & -ArionHash
$d_{1}=3$
$3$ |  $6$ |  $5$
$4$ |  $6$ |  $4$
$5$ |  $5$ |  $4$
$6$ |  $5$ |  $4$
$8$ |  $4$ |  $4$
$d_{1}=5$
$3$ |  $6$ |  $4$
$4$ |  $5$ |  $4$
$5$ |  $5$ |  $4$
$6$ |  $5$ |  $4$
$8$ |  $4$ |  $4$

The number of rounds for -Arion and -ArionHash are chosen to provide 128 bit
security against the most efficient deterministic algorithm for polynomial
system solving in a Gröbner basis attack on ArionHash. For more details on the
security with respect to Gröbner basis attacks we refer to Appendix C in the
full version of the paper [49].

##  3 Security Analysis of Arion

###  3.1 Statistical Cryptanalysis

####  3.1.1 Differential Cryptanalysis.

In differential cryptanalysis [13] and its variants the propagation of input
differences through the rounds of a block cipher or hash function is exploited
to recover the secret key or to construct a collision. For the Arion GTDS the
probability that an input difference $\boldsymbol{\Delta
x}\in\mathbb{F}_{q}^{n}\setminus\\{\mathbf{0}\\}$ propagates to the output
difference is $\boldsymbol{\Delta y}\in\mathbb{F}_{q}^{n}$ is bounded by (see
[48, Theorem 18, Corollary 19])

$\operatorname{\mathbb{P}}\left[\mathcal{F}_{\textsf{Arion}}\\!:\boldsymbol{\Delta
x}\to\boldsymbol{\Delta
y}\right]\leq\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}\left(\boldsymbol{\Delta
x}\right)}\leq\frac{d_{2}}{p},$ (2)

where $\operatorname{wt}:\mathbb{F}_{q}^{n}\to\mathbb{Z}$ denotes Hamming
weight. For $p\geq 2^{250}$ and $d_{2}\leq 2^{9}$ this probability is bounded
by $2^{-241\cdot\operatorname{wt}\left(\boldsymbol{\Delta x}\right)}\leq
2^{-241}$. Under the assumption that the rounds of Arion are statistically
independent we can estimate the probability of any non-trivial differential
trail via $2^{-241\cdot r}$. Moreover, even if an adversary can search a
restricted differential hull of size $2^{120}$ between the $2$nd and the $r$th
round, then two rounds are already sufficient to provide $128$ bit security
against differential cryptanalysis. For more details we refer to Appendix A.1
in the full version of the paper [49].

Note that a small differential probability also rules out the boomerang attack
[52, 37] which exploits two complementary differential patterns that span the
cipher, of which one must at least cover two rounds.

####  3.1.2 Truncated Differential & Rebound Cryptanalysis.

In a truncated differential attack [38] an attacker can only predict parts of
the difference between pairs of text. We expect that the Arion GTDS admits
truncated differentials of Hamming weight $1$ with probability $1$ for the
first round. On the other hand, if $\operatorname{wt}(\mathbf{v})=1$, then we
have that
$\operatorname{wt}\big{(}\operatorname{circ}(1,\dots,n)\mathbf{v}\big{)}=n$.
Therefore, such a truncated differential activates all inputs in the second
round of Arion. Hence, for $p\geq 2^{250}$ and $d_{2}\leq 2^{9}$ the
differential probability for the second round is bounded by $2^{-250\cdot n}$.
Even if an adversary can search restricted differential hulls of size
$2^{120}$ after the first round, this probability and Equation 2 nullify
truncated differential attacks within the $128$ bit security target.

In a rebound attack [41, 45] an adversary connects two (truncated)
differentials in the middle of a cipher or hash function. Probability $1$
truncated differentials can cover at most one round of Arion, so $r-2$ rounds
can be covered with an inside-out approach. By our previous analysis we do not
expect that a successful rebound attack can be mounted on $4$ or more rounds
on Arion & ArionHash within the $128$ bit security target.

For more details we refer to Appendix A.2 in the full version of the paper
[49].

####  3.1.3 Linear Cryptanalysis.

Linear cryptanalysis [44, 5] utilizes affine approximations of round functions
for a sample of known plaintexts. For any additive character
$\chi:\mathbb{F}_{q}\to\mathbb{C}$ and any affine approximation
$\mathbf{a},\mathbf{b}\in\mathbb{F}_{q}^{n}\setminus\\{\mathbf{0}\\}$, the
linear probability of the Arion GTDS is bounded by (see [48, Theorem 24,
Corollary 25])

$\operatorname{LP}_{\mathcal{F}_{\textsf{Arion}}}(\chi,\mathbf{a},\mathbf{b})\leq\frac{\left(d_{2}-1\right)^{2}}{q}.$
(3)

Therefore, for $p\geq 2^{250}$ and $d_{2}\leq 2^{9}$ this probability is
bounded by $2^{-232}$, and henceforth under the assumption of statistically
independent rounds of Arion the linear probability of any non-trivial linear
trail is bounded by $2^{-232\cdot r}$. Moreover, even if an adversary can
search a restricted linear hull of size $2^{120}$ between the $2$nd and the
$r$th round, then two rounds are already sufficient to provide $128$ bit
security against linear cryptanalysis. For more details we refer to Appendix
A.3 in the full version of the paper [49].

###  3.2 Algebraic Cryptanalysis

####  3.2.1 Interpolation & Integral Cryptanalysis.

Interpolation attacks [36] construct the polynomial vector representing a
cipher without knowledge of the secret key. If such an attack is successful
against a cipher, then an adversary can encrypt any plaintext without
knowledge of the secret key. Recall that any function
$F:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ can be represented by a polynomial
$f\in\mathbb{F}_{p}[\mathbf{X}_{n}]=\mathbb{F}_{q}[x_{1},\dots,x_{n}]/\left(x_{1}^{q}-x_{1},\dots,x_{n}^{q}-x_{n}\right)$,
thus at most $q^{n}$ monomials can be present in $f$. After the first round of
Arion\- we expect that the terms

$\left(\sum_{i=1}^{n}i\cdot x_{i}\right)^{e}+\sum_{i=1}^{n}i\cdot x_{i}$ (4)

are present in every branch. After another application of the round function
we expect to produce the terms

$\left(\left(\sum_{i=1}^{n}i\cdot x_{i}\right)^{e}+\sum_{i=1}^{n}i\cdot
x_{i}\right)^{e}\mod\left(x_{1}^{p}-x_{1},\dots,x_{n}^{p}-x_{n}\right)$ (5)

in every branch. By our specification $e$ is the inverse exponent of a
relatively low degree permutation, therefore we expect that after two rounds
almost all monomials from $\mathbb{F}_{p}[\mathbf{X}_{n}]$ are present in
every component of Arion. For more details we refer to Appendix B.1 in the
full version of the paper [49].

For a polynomial $f\in\mathbb{F}_{q}[x_{1},\dots,x_{n}]$ an integral
distinguisher [39, 11] exploits that for any affine subspace
$V\subset\mathbb{F}_{q}^{n}$ with
$\deg\left(f\right)<\dim\left(V\right)\cdot\left(q-1\right)$ one has that

$\sum_{\mathbf{x}\in V}f(\mathbf{x})=0.$ (6)

If almost all monomials are present in Arion-, then
$\deg\left(\text{{Arion}-\textpi}\right)\approx n\cdot(q-1)$ in every
component, so only $V=\mathbb{F}_{q}^{n}$ is a suitable subspace for an
integral distinguisher. Therefore, we do not expect that non-trivial integral
distinguishers exist for Arion-. For more details we refer to Appendix B.2 in
the full version of the paper [49].

####  3.2.2 Gröbner Basis Analysis.

In a Gröbner basis attack [17, 21] one models a cipher or hash function as
fully determined polynomial system and then solves for the key or preimage.
For Gröbner basis analysis of Arion & ArionHash we assume that a degree
reverse lexicographic (DRL) Gröbner basis can be found in $\mathcal{O}(1)$. We
base the security of Arion & ArionHash solely on the complexity of solving
their polynomial systems via state of the art deterministic and probabilistic
Gröbner basis conversion algorithms [28, 29, 27] combined with the univariate
polynomial solving algorithm of Bariant et al. [8, §3.1]. With this methods,
solving a fully determined polynomial system over a finite field
$\mathbb{F}_{q}$ with known DRL Gröbner basis via deterministic methods
requires

$\mathcal{O}\left(n\cdot
d^{\omega}+d\cdot\log\left(q\right)\cdot\log\left(d\right)\cdot\log\big{(}\log\left(d\right)\big{)}+d\cdot\log\left(d\right)^{2}\cdot\log\big{(}\log\left(d\right)\big{)}\right)$
(7)

field operations, and with deterministic methods

$\mathcal{O}\left(\sqrt{n}\cdot
d^{2+\frac{n-1}{n}}+d\cdot\log\left(q\right)\cdot\log\left(d\right)\cdot\log\big{(}\log\left(d\right)\big{)}+d\cdot\log\left(d\right)^{2}\cdot\log\big{(}\log\left(d\right)\big{)}\right)$
(8)

field operations, where $q$ is the size of the finite field, $n$ is the number
of variables, $d$ is the $\mathbb{F}_{q}$-vector space dimension of the
polynomial ring modulo the polynomial system and $2\leq\omega<2.3727$ is a
linear algebra constant. We conjecture that the quotient space dimension of
Arion grows or bounded by

$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{Arion}}\right)(n,r,d_{1},d_{2})=\left(d_{2}\cdot\left(d_{1}+2\right)^{n-1}\right)^{r},$
(9)

and for ArionHash we conjecture that the dimension grows or is bounded by

$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash}}\right)(n,r,d_{1},d_{2})=\Big{(}2^{n-1}\cdot
d_{2}\cdot\left(d_{1}+1\right)-d_{1}\cdot d_{2}\Big{)}^{r}.$ (10)

Round numbers for Arion & ArionHash in Table 3 are chosen to resist
deterministic as well as probabilistic Gröbner basis attacks against an ideal
adversary with $\omega=2$ within the 128 bit security target. Round numbers
for -Arion & -ArionHash in Table 3 are chosen to resist only deterministic
Gröbner basis attacks within the 128 bit security target.

For ArionHash one can set up a collision polynomial system by connecting two
preimage polynomial systems. Note that this polynomial system is in general
not fully determined, therefore an adversary has to randomly guess some
variables before solving the system. If an adversary guesses output variables
of the sponge until the collision polynomial system is fully determined, then
we conjecture that the quotient space dimension of the collision polynomial
system grows or is bounded by

$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash},coll}\right)\left(n,r,d_{1},d_{2}\right)=\left(\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash}}\right)\left(n,r,d_{1},d_{2}\right)\right)^{2}.$
(11)

Thus, we do not expect a collision Gröbner basis attack to be more
performative than a preimage attack. For more details we refer to Appendix C
in the full version of the paper [49].

##  4 Performance Evaluation

In this section, we compare various instances of ArionHash, Anemoi, Griffin
and Poseidon with respect to R1CS (Section 4.2) and Plonk (Section 4.3). For
starters, we discuss the theoretical foundation of an efficient implementation
of an ArionHash circuit. In the Anemoi proposal it was revealed that CCZ-
equivalence is a route to construct high degree permutations that can be
verified with CCZ-equivalent low degree functions [16, §4.1]. In Section 4.1
we follow this approach to prove that a ArionHash circuit can be transformed
into an efficient circuit that avoids the computation of $x^{e}$ via an affine
transformation.

###  4.1 Reducing the Number of Constraints

By definition of the Arion GTDS a prover circuit will have to verify that

$y=x^{e},$ (12)

though since $e$ induces the inverse power permutation to
$d_{2}\in\\{121,123,125,129,\allowbreak 161,193,195,257\\}$ the naive circuit
for Equation 12 will introduce many constraints. On the other hand, from a
prover’s perspective Equation 12 is equivalent to

$y^{d_{2}}=\left(x^{e}\right)^{d_{2}}=x,$ (13)

for all $x\in\mathbb{F}_{p}$. Thus, in an implementation to reduce the number
of multiplicative constraints we are well advised to implement the equivalent
circuit instead of the naive circuit. We also would like to note that the same
trick was applied in Griffin [31] to reduce the number of constraints.

In the design of Anemoi [16, §4] a new tool was introduced to reduce the
number constraints for an Anemoi circuit: CCZ-equivalence [19]. The authors
have found a high degree permutation, the open Flystel, which is CCZ-
equivalent to a low degree function, the closed Flystel. Consequently, this
can be exploited to significantly reduce the number of constraints in a prover
circuit (cf. [16, Corollary 2]). Let us now formalize the trick in Equation 13
in terms of CCZ-equivalence.

###### Definition 4.1

Let $\mathbb{F}_{q}$ be a finite field, and let
$F,G:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}^{m}$ be functions.

  1. (1)

The graph of $F$ is defined as

$\Gamma_{F}=\Big{\\{}\big{(}\mathbf{x},F(\mathbf{x})\big{)}\mid\mathbf{x}\in\mathbb{F}_{q}^{n}\Big{\\}}.$

  2. (2)

$F$ and $G$ are said to be CCZ-equivalent if there exists an affine
permutation $\mathcal{A}$ of $\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{m}$ such
that

$\Gamma_{F}=\mathcal{A}(\Gamma_{G}).$

Now let us describe a GTDS that is equivalent to the Arion GTDS.

###### Proposition 4.2

Let $\mathbb{F}_{p}$ be a prime field, and let
$n,d_{1},d_{2},e\in\mathbb{Z}_{>1}$ be integers such that

  1. (i)

$d_{1}$ is the smallest positive integer such that
$\gcd\left(d_{1},p-1\right)=1$,

  2. (ii)

$d_{2}$ is an arbitrary integer such that $\gcd\left(d_{2},p-1\right)=1$, and

  3. (iii)

$e\cdot d_{2}\equiv 1\mod p-1$.

Let $\mathcal{F}_{\textsf{Arion}}=\\{f_{1},\dots,f_{n}\\}$ be the Arion GTDS,
let $g_{i},h_{i}\in\mathbb{F}_{q}[x]$ be the polynomials that define
$\mathcal{F}_{\textsf{Arion}}$, and let the GTDS
$\mathcal{G}=\\{\hat{f}_{1},\dots,\hat{f}_{n}\\}$ be defined as

$\begin{split}\hat{f}_{i}(x_{1},\dots,x_{n})&=x_{i}^{d_{1}}\cdot
g_{i}(\tau_{i+1,n})+h_{i}(\tau_{i+1,n}),\qquad 1\leq i\leq n-1,\\\
\hat{f}_{n}(x_{1},\dots,x_{n})&=x_{n}^{d_{2}},\end{split}$

where

$\tau_{i+1,n}=\sum_{j=i+1}^{n}x_{j}+\hat{f}_{j}(x_{1},\dots,x_{n}).$

Then $\mathcal{F}_{\textsf{Arion}}$ is CCZ-equivalent to $\mathcal{G}$.

###### Proof

We consider the affine permutation
$\mathcal{A}:\mathbb{F}_{q}^{2n}\to\mathbb{F}_{q}^{2n}$ that swaps the $n$th
element with the $(2n)$th element, moreover we consider the substitution
$\mathbf{x}=\big{(}\hat{x}_{1},\dots,\hat{x}_{n-1},\hat{x}_{n}^{d_{2}}\big{)}$.
Now we apply the affine permutation to $\Gamma_{\mathcal{F}_{\textsf{Arion}}}$
which yields

$\mathcal{A}\big{(}\mathbf{x},\mathcal{F}_{\textsf{Arion}}(\mathbf{x})\big{)}=\begin{pmatrix}\\{\hat{x}_{i}\\}_{1\leq
i\leq n-1}\\\\[2.0pt] \hat{x}_{n}^{e\cdot d_{2}}\\\\[2.0pt]
\Big{\\{}f_{i}\left(\hat{x}_{i},\dots,\hat{x}_{n}^{d_{2}}\right)\Big{\\}}_{1\leq
i\leq n-1}\\\\[2.0pt] \hat{x}_{n}^{d_{2}}\end{pmatrix}.$

By construction of $d_{2}$ and $e$ we have that $x^{e\cdot d_{2}}=x$ for every
$x\in\mathbb{F}_{p}$. Let’s now investigate what happens to the $f_{i}$’s.
Starting with $f_{n-1}$, we have that

$\sigma_{n,n}\left(\hat{x}_{n}^{d_{2}}\right)=\hat{x}_{n}^{d_{2}}+\hat{x}_{n}^{e\cdot
d_{2}}=\hat{x}_{n}+\hat{x}_{n}^{d_{2}}=\tau_{n,n}(\hat{x}_{n}),$

for all $\hat{x}_{n}\in\mathbb{F}_{p}$, and therefore

$f_{n-1}\left(\hat{x}_{n-1},\hat{x}_{n}^{d_{2}}\right)=\hat{f}_{n-1}(\hat{x}_{n-1},\hat{x}_{n}).$

Inductively, we now go through all the branches to conclude that
$f_{i}\left(\hat{x}_{i},\dots,\hat{x}_{n}^{d_{2}}\right)=\hat{f}_{i}(\hat{x}_{i},\dots,\hat{x}_{n})$
for all $1\leq i\leq n-1$ which proves that
$\mathcal{A}\big{(}\mathbf{x},\mathcal{F}(\mathbf{x})\big{)}=\big{(}\boldsymbol{\hat{x}},\mathcal{G}(\boldsymbol{\hat{x}})\big{)}$.
∎

###### Corollary 4.3

Verifying that $(y_{1},\dots,y_{n})=\mathcal{F}(x_{1},\dots,x_{n})$ is
equivalent to verifying that
$(y_{1},\dots,y_{n-1},x_{n})=\mathcal{G}(x_{1},\dots,x_{n-1},y_{n})$.

Note that it follows from [48, Theorem 18, 24] that the Arion GTDS
$\mathcal{F}$ and its CCZ-equivalent GTDS $\mathcal{G}$ from Theorem 4.2 are
in the same security class with respect to differential and linear
cryptanalysis. Unlike as for Anemoi the CCZ-equivalent GTDS $\mathcal{G}$ is
not a low degree function, though when implementing it as prover circuit we
never have use multiplications to compute $\tau_{i+1,n}$.

###  4.2 R1CS Performance of ArionHash

Estimating the number of multiplicative constraints in a R1CS circuit for
ArionHash is straightforward.

###### Lemma 4.4

Let $\mathbb{F}_{p}$ be a finite field, let $r,n\geq 2$ be integers, and let
ArionHash with $r$ rounds be defined over $\mathbb{F}_{p}^{n}$. For $i=1,2$
denote with $d_{i,\text{inc}}$ the minimal number of multiplications to
compute the univariate power permutation $x^{d_{i}}$. Then a prover R1CS
circuit for ArionHash needs

$N_{\textsf{ArionHash}}=r\cdot\big{(}\left(n-1\right)\cdot\left(d_{1,\text{inc}}+2\right)+d_{2,\text{inc}}\big{)}$

multiplicative constraints.

###### Proof

By Theorem 4.3 one needs $d_{2,\text{inc}}$ constraints in the $n$th branch.
In each of the remaining $n-1$ branches one needs $d_{1,\text{inc}}$
constraints for the power permutation, $1$ constraints for the computation of
$g_{i}$ and $h_{i}$ and $1$ multiplication for the product of the power
permutation and $g_{i}$. ∎

Analog the number of R1CS constraints for Anemoi, Griffin and Poseidon (cf.
[16, §7], [31, §7.2] and [33]) are given by

$\displaystyle N_{\textsc{Griffin}}$ $\displaystyle=2\cdot
r\cdot\left(d_{inc}+n-2\right),$ (14) $\displaystyle N_{\texttt{Anemoi}}$
$\displaystyle=\frac{r\cdot n}{2}\cdot\left(d_{inc}+2\right),$ (15)
$\displaystyle N_{\textsc{Poseidon}}$ $\displaystyle=d_{inc}\cdot\left(n\cdot
r_{f}+r_{p}\right).$ (16)

In Table 4 we compiled the round numbers of the hash functions.

Table 4: Round numbers for Anemoi [16, §A.4], ArionHash (Table 3), Griffin
[31, Table 2] and Poseidon [33, Table 1] for $256$ bit prime fields and 128
bit security with $d_{2}\in\\{121,123,125,161,193,195,257\\}$.

Rounds
---
|  ArionHash |  -ArionHash |  Griffin |  Anemoi |  Poseidon
$n$ | $d_{1}=3$
$3$ |  $6$ |  $5$ |  $16$ |  |  $r_{f}=8,\ r_{p}=84$
$4$ |  $6$ |  $4$ |  $14$ |  $12$ |  $r_{f}=8,\ r_{p}=84$
$5$ |  $4$ |  |  |  |  $r_{f}=8,\ r_{p}=84$
$6$ |  $5$ |  $4$ |  |  $10$ |  $r_{f}=8,\ r_{p}=84$
$8$ |  $4$ |  $4$ |  $11$ |  $10$ |  $r_{f}=8,\ r_{p}=84$
$n$ | $d_{1}=5$
$3$ |  $6$ |  $4$ |  $12$ |  |  $r_{f}=8,\ r_{p}=56$
$4$ |  $5$ |  $4$ |  $11$ |  $12$ |  $r_{f}=8,\ r_{p}=56$
$5$ |  $5$ |  $4$ |  |  |  $r_{f}=8,\ r_{p}=56$
$6$ |  $5$ |  $4$ |  |  $10$ |  $r_{f}=8,\ r_{p}=56$
$8$ |  $4$ |  $4$ |  $9$ |  $10$ |  $r_{f}=8,\ r_{p}=56$

In Table 5 we compare the theoretical number of constraints for R1CS of
various hash functions.

Table 5: R1CS constraint comparison $256$ bit prime fields and 128 bit
security with $d_{2}\in\\{121,123,125,161,193,195,257\\}$. Round numbers for
Anemoi, Griffin and Poseidon are taken from [16, §A.4], [31, Table 1] and [33,
Table 1].

R1CS Constraints
---
|  ArionHash |  -ArionHash |  Griffin |  Anemoi |  Poseidon
$n$ | $d_{1}=3$
$3$ |  $102$ |  $85$ |  $96$ |  |  $216$
$4$ |  $126$ |  $84$ |  $112$ |  $96$ |  $232$
$5$ |  $120$ |  $100$ |  |  |  $248$
$6$ |  $145$ |  $116$ |  |  $120$ |  $264$
$8$ |  $148$ |  $148$ |  $176$ |  $160$ |  $296$
$n$ | $d_{1}=5$
$3$ |  $114$ |  $76$ |  $96$ |  |  $240$
$4$ |  $120$ |  $96$ |  $110$ |  $120$ |  $264$
$5$ |  $125$ |  $116$ |  |  |  $288$
$6$ |  $170$ |  $136$ |  |  $150$ |  $312$
$8$ |  $176$ |  $176$ |  $162$ |  $200$ |  $360$

Moreover, in Appendix D.1 of the full version of the paper [49] we compare the
performance of Arion, Griffin and Poseidon using the `C++` library libsnark
[50] that is used in the privacy-protecting digital currency Zcash [35].

###  4.3 Plonk Performance of ArionHash

Plonk [30] is a zkSNARK proof system which does not utilize R1CS constraints.
In Plonk a 2-(input)-wire constraint is of the form, see [30, §6],

$(a\cdot b)\cdot q_{M}+a\cdot q_{L}+b\cdot q_{R}+c\cdot q_{O}+q_{C}=0,$ (17)

$a$ and $b$ denote the left and right input variable, $c$ denotes the output
variable and $q_{M}$, $q_{L}$, $q_{R}$, $q_{O}$ and $q_{C}$ denote the
“selector coefficient” of the multiplication, the variables and the constant
term. The 3-(input)-wire Plonk constraint has 3 addition gates

$(a\cdot b)\cdot q_{M}+a\cdot q_{L}+b\cdot q_{R}+c\cdot q_{O}+d\cdot
q_{F}+q_{C}=0,$ (18)

where $d$ is the “fourth” variable and $q_{F}$ its selector coefficient.

Counting the number of Plonk constraints is more subtle, since we now have to
account for additions too.

###### Lemma 4.5

Let $\mathbb{F}_{p}$ be a finite field, let $r,n\geq 2$ be integers, and let
ArionHash with $r$ rounds be defined over $\mathbb{F}_{p}^{n}$. For $i=1,2$
denote with $d_{i,\text{inc}}$ the minimal number of multiplications to
compute the univariate power permutation $x^{d_{i}}$.

  1. (1)

A prover circuit needs

$(n-1)\cdot(d_{1,inc}+6)+d_{2,inc}-1$

2-wire and

$(n-1)\cdot(d_{1,inc}+4)+d_{2,inc}$

3-wire Plonk constraints for the ArionHash GTDS.

  2. (2)

A prover circuit needs

$4\cdot(n-1)$

2-wire and

$\begin{dcases}n,&n=2,3,\\\
n+2+\left\lceil\frac{n-3}{2}\right\rceil+\left\lceil\frac{n-4}{2}\right\rceil,&n\geq
4,\end{dcases}$

3-wire Plonk constraints for the affine layer of ArionHash.

Then a prover circuit needs

$N_{\textsf{ArionHash},2}=r\cdot\big{(}(n-1)\cdot(d_{1,inc}+6)+d_{2,inc}-1\big{)}+(r+1)\cdot\begin{dcases}n\cdot(n-1),&n=2,3\\\
4\cdot(n-1),&n\geq 4,\end{dcases}$

2-wire and

$\displaystyle N_{\textsf{ArionHash},3}=r$
$\displaystyle\cdot\big{(}(n-1)\cdot(d_{1,inc}+4)+d_{2,inc}\big{)}$
$\displaystyle+(r+1)\cdot\begin{dcases}n,&n=2,3,\\\
n+2+\left\lceil\frac{n-3}{2}\right\rceil+\left\lceil\frac{n-4}{2}\right\rceil,&n\geq
4,\end{dcases}$

3-wire Plonk constraints for ArionHash.

###### Proof

For (1), again we can use the CCZ-equivalent GTDS $\mathcal{G}$, see Theorem
4.2, to build the circuit for the ArionHash GTDS. For $x^{d_{i}}$ one needs
$d_{i,inc}$, so we need $(n-1)\cdot d_{1,inc}+d_{2,inc}$ constraints for the
univariate permutation polynomials. For $\tau_{n,n}$ one needs one constraint,
and for $\tau_{i+1,n}$, where $i<n-1$, one needs two 2-wire constraints, so in
total one needs $1+2\cdot(n-2)$ 2-wire constraints to compute the
$\tau_{i+1,n}$’s. On the other, hand for 3-wire constraints one can compute
all $\tau_{i+1,n}$’s with one constraint, so $n-1$ in total. To compute

$\displaystyle g_{i}$
$\displaystyle=\tau^{2}+\alpha_{i,1}\cdot\tau_{i+1,n}+\alpha_{i,2},$
$\displaystyle h_{i}$ $\displaystyle=\tau^{2}+\beta_{i}\cdot\tau_{i+1,n}$

one needs two constraints since one can build any quadratic polynomial with
the 2-wire Plonk constraint, see Equation 17. To compute $x_{i}^{d_{1}}\cdot
g_{i}+h_{i}$ one needs two 2-wire constraints and one 3-wire constraint. We
have to do this $(n-1)$ times, hence in total we need $(n-1)\cdot
d_{1,inc}+d_{2,inc}+1+2\cdot(n-2)+4\cdot(n-1)$ 2-wire and $(n-1)\cdot
d_{1,inc}+d_{2,inc}+(n-1)+(n-1)\cdot(2+1)$ 3-wire constraints.

For (2), we build the circuit with Algorithm 1. To compute a sum of $m$
elements one needs $m-1$ 2-wire constraints and
$1+\left\lceil\frac{m-3}{2}\right\rceil$ 3-wire constraints. We have to do
this for $\sigma$ and for $\sum_{i=2}^{n}(i-1)\cdot v_{i}$, so we need
$(n-1)+(n-2)+1$ 2-wire and
$1+\left\lceil\frac{n-3}{2}\right\rceil+1+\left\lceil\frac{n-4}{2}\right\rceil+1$
3-wire constraints to compute $w_{1}=\sigma+\sum_{i=2}^{n}(i-1)\cdot
v_{i}+c_{1}$, where we do constant addition in the addition of the two sums.
For the $i$th component, we have that $w_{i}=w_{i-1}-\sigma+n\cdot
v_{i}-c_{i-1}+c_{i}$, so we need two 2-wire and one 3-wire constraints. We
have to do this $n-1$ times, hence in total we need
$(n-1)+(n-2)+1+2\cdot(n-1)$ 2-wire and
$3+\left\lceil\frac{n-3}{2}\right\rceil+\left\lceil\frac{n-4}{2}\right\rceil+n-1$
3-wire constraints. ∎

Note that for $n\geq 4$ Algorithm 1 yields more efficient 2-wire and 3-wire
circuits than generic matrix multiplication which always needs $n\cdot(n-1)$
2-wire and $n\cdot\left(1+\left\lceil\frac{n-3}{2}\right\rceil\right)$ 3-wire
constraints.

For ArionHash’s main competitors Anemoi, Griffin and Poseidon we list the
formulae to compute their Plonk constraints in Table 6.

Table 6: Plonk constraints for Anemoi [16, §7.2], Griffin [31, §7.3] and
Poseidon [33].

Hash |  2-wire constraints |  3-wire constraints
---|---|---
Anemoi |  $\frac{r\cdot n}{2}\cdot(d_{inc}+5)+(r+1)\cdot\begin{cases}2,&n=2,\\\ n\cdot\left(\frac{n}{2}-1\right),&n=4,\\\ 10,&n=6,\\\ 16,&n=8\end{cases}$ |  $\frac{r\cdot n}{2}\cdot(d_{inc}+3)+(r+1)\cdot\begin{cases}(r+1)\cdot n,&n=2,4,\\\ 6,&n=6,\\\ 12,&n=8\end{cases}$
Griffin |  $r\cdot(2\cdot d_{inc}+4\cdot n-11)+(r+1)\cdot\begin{cases}5,&n=3,\\\ 8,&n=4,\\\ 24,&n=8,\\\ \frac{8\cdot n}{4}+2\cdot n-4,&n\geq 12\end{cases}$ |  $r\cdot(2\cdot d_{inc}+3\cdot n-8)+(r+1)\cdot\begin{cases}3,&n=3,\\\ 6,&n=4,\\\ 20,&n=8,\\\ \frac{6\cdot n}{4}+4\cdot\left\lfloor\frac{\frac{n}{4}-1}{2}\right\rfloor+n,&n\geq 12\end{cases}$
Poseidon |  $d_{inc}\cdot\left(n\cdot r_{f}+r_{p}\right)+(r+1)\cdot n\cdot(n-1)$ |  $d_{inc}\cdot\left(n\cdot r_{f}+r_{p}\right)+(r+1)\cdot n\cdot\begin{cases}n,&n=2,3,\\\ \left\lceil\frac{n-3}{2}\right\rceil,&n\geq 4\end{cases}$

In Table 7 we compare the theoretical number of constraints for Plonk for
various hash functions.

Table 7: Plonk constraint comparison $256$ bit prime fields and 128 bit
security with $d_{2}\in\\{121,123,125,161,193,195,257\\}$. Round numbers are
the same as in Table 4.

Plonk Constraints
---
| 2-wire constraints | 3-wire constraints
| State size $n$
|  $3$ |  $4$ |  $5$ |  $6$ |  $8$ |  $3$ |  $4$ |  $5$ |  $6$ |  $8$
Hash | $d_{1}=3$
ArionHash |  $200$ |  $276$ |  $296$ |  $360$ |  $396$ |  $147$ |  $211$ |  $219$ |  $261$ |  $279$
-ArionHash |  $168$ |  $188$ |  $240$ |  $292$ |  $396$ |  $123$ |  $143$ |  $177$ |  $211$ |  $279$
Poseidon |  $768$ |  $1336$ |  $2088$ |  $3024$ |  $5448$ |  $492$ |  $600$ |  $708$ |  $1368$ |  $2504$
Griffin |  $165$ |  $246$ |  |  |  $563$ |  $131$ |  $202$ |  |  |  $460$
Anemoi |  |  $220$ |  |  $320$ |  $456$ |  |  $172$ |  |  $216$ |  $332$
Hash | $d_{1}=5$
ArionHash |  $212$ |  $247$ |  $316$ |  $385$ |  $424$ |  $159$ |  $192$ |  $239$ |  $286$ |  $307$
-ArionHash |  $144$ |  $200$ |  $256$ |  $312$ |  $424$ |  $107$ |  $155$ |  $193$ |  $231$ |  $307$
Poseidon |  $624$ |  $1032$ |  $1568$ |  $2232$ |  $3944$ |  $432$ |  $520$ |  $608$ |  $1080$ |  $1896$
Griffin |  $173$ |  $275$ |  |  |  $561$ |  $123$ |  $182$ |  |  |  $398$
Anemoi |  |  $244$ |  |  $350$ |  $496$ |  |  $196$ |  |  $246$ |  $372$

Moreover, in Appendix D.2 of the full version of the paper [49] we compare the
performance of Arion and Poseidon using the `Rust` library Dusk Network Plonk
[23].

#### Acknowledgments.

Matthias Steiner and Stefano Trevisani were supported by the KWF under project
number KWF-3520|31870|45842.

## References

  * [1] Albrecht, M.R., Grassi, L., Perrin, L., Ramacher, S., Rechberger, C., Rotaru, D., Roy, A., Schofnegger, M.: Feistel structures for MPC, and more. In: Sako, K., Schneider, S., Ryan, P.Y.A. (eds.) ESORICS 2019: 24th European Symposium on Research in Computer Security, Part II. Lecture Notes in Computer Science, vol. 11736, pp. 151–171. Springer, Heidelberg, Germany, Luxembourg (Sep 23–27, 2019). doi:10.1007/978-3-030-29962-0_8
  * [2] Albrecht, M.R., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology – ASIACRYPT 2016, Part I. Lecture Notes in Computer Science, vol. 10031, pp. 191–219. Springer, Heidelberg, Germany, Hanoi, Vietnam (Dec 4–8, 2016). doi:10.1007/978-3-662-53887-6_7
  * [3] Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology – EUROCRYPT 2015, Part I. Lecture Notes in Computer Science, vol. 9056, pp. 430–454. Springer, Heidelberg, Germany, Sofia, Bulgaria (Apr 26–30, 2015). doi:10.1007/978-3-662-46800-5_17
  * [4] Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., Szepieniec, A.: Design of symmetric-key primitives for advanced cryptographic protocols. IACR Transactions on Symmetric Cryptology 2020(3), 1–45 (2020). doi:10.13154/tosc.v2020.i3.1-45
  * [5] Baignères, T., Stern, J., Vaudenay, S.: Linear cryptanalysis of non binary ciphers. In: Adams, C.M., Miri, A., Wiener, M.J. (eds.) SAC 2007: 14th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 4876, pp. 184–211. Springer, Heidelberg, Germany, Ottawa, Canada (Aug 16–17, 2007). doi:10.1007/978-3-540-77360-3_13
  * [6] Bardet, M., Faugère, J.C., Salvy, B.: Asymptotic behaviour of the index of regularity of semi-regular quadratic polynomial systems. In: MEGA 2005 - 8th International Symposium on Effective Methods in Algebraic Geometry. pp. 1–17. Porto Conte, Alghero, Sardinia, Italy (05 2005), https://hal.archives-ouvertes.fr/hal-01486845
  * [7] Bardet, M., Faugère, J.C., Salvy, B., Yang, B.Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: MEGA 2005 - 8th International Symposium on Effective Methods in Algebraic Geometry. Porto Conte, Alghero, Sardinia, Italy (05 2005)
  * [8] Bariant, A., Bouvier, C., Leurent, G., Perrin, L.: Algebraic attacks against some arithmetization-oriented primitives. IACR Transactions on Symmetric Cryptology 2022(3), 73–101 (2022). doi:10.46586/tosc.v2022.i3.73-101
  * [9] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. Ecrypt Hash Workshop (2007), https://keccak.team/files/SpongeFunctions.pdf
  * [10] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N.P. (ed.) Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 181–197. Springer, Heidelberg, Germany, Istanbul, Turkey (Apr 13–17, 2008). doi:10.1007/978-3-540-78967-3_11
  * [11] Beyne, T., Canteaut, A., Dinur, I., Eichlseder, M., Leander, G., Leurent, G., Naya-Plasencia, M., Perrin, L., Sasaki, Y., Todo, Y., Wiemer, F.: Out of oddity - new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology – CRYPTO 2020, Part III. Lecture Notes in Computer Science, vol. 12172, pp. 299–328. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 17–21, 2020). doi:10.1007/978-3-030-56877-1_11
  * [12] Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. In: Stern, J. (ed.) Advances in Cryptology – EUROCRYPT’99. Lecture Notes in Computer Science, vol. 1592, pp. 12–23. Springer, Heidelberg, Germany, Prague, Czech Republic (May 2–6, 1999). doi:10.1007/3-540-48910-X_2
  * [13] Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology 4(1), 3–72 (Jan 1991). doi:10.1007/BF00630563
  * [14] Bogdanov, A., Rijmen, V.: Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Cryptogr. 70(3), 369–383 (03 2014). doi:10.1007/s10623-012-9697-z
  * [15] Bogdanov, A., Wang, M.: Zero correlation linear cryptanalysis with reduced data complexity. In: Canteaut, A. (ed.) Fast Software Encryption – FSE 2012. Lecture Notes in Computer Science, vol. 7549, pp. 29–48. Springer, Heidelberg, Germany, Washington, DC, USA (Mar 19–21, 2012). doi:10.1007/978-3-642-34047-5_3
  * [16] Bouvier, C., Briaud, P., Chaidos, P., Perrin, L., Salen, R., Velichkov, V., Willems, D.: New design techniques for efficient arithmetization-oriented hash functions: Anemoi permutations and Jive compression mode. Cryptology ePrint Archive, Paper 2022/840 (2022), https://eprint.iacr.org/2022/840, Version: 20221017:092940
  * [17] Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Phd thesis, Universität Insbruck (1965)
  * [18] Caminata, A., Gorla, E.: Solving multivariate polynomial systems and an invariant from commutative algebra. In: Bajard, J.C., Topuzoğlu, A. (eds.) Arithmetic of Finite Fields. pp. 3–36. Springer International Publishing, Cham (2021). doi:10.1007/978-3-030-68869-1_1
  * [19] Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125–156 (11 1998). doi:10.1023/A:1008344232130
  * [20] Cover, T.M., Joy, T.A.: Elements of Information Theory. John Wiley & Sons, Ltd, Hoboken, New Jersey, 2 edn. (2006). doi:10.1002/0471200611
  * [21] Cox, D.A., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics, Springer International Publishing, 4 edn. (2015). doi:10.1007/978-3-319-16721-3
  * [22] Ding, J., Schmidt, D.: Solving degree and degree of regularity for polynomial systems over a finite fields. In: Fischlin, M., Katzenbeisser, S. (eds.) Number Theory and Cryptography: Papers in Honor of Johannes Buchmann on the Occasion of His 60th Birthday. pp. 34–49. Springer Berlin Heidelberg, Berlin, Heidelberg (2013). doi:10.1007/978-3-642-42001-6_4
  * [23] Dusk Network: PLONK (2022), https://github.com/dusk-network/plonk, Version: 0.13.1
  * [24] Dusk Network: Dusk-Poseidon (2023), https://github.com/dusk-network/Poseidon252, Version: 0.28.1
  * [25] Faugère, J.C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139(1), 61–88 (1999). doi:10.1016/S0022-4049(99)00005-5
  * [26] Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. p. 75–83. ISSAC ’02, Association for Computing Machinery (2002). doi:10.1145/780506.780516
  * [27] Faugère, J.C., Gaudry, P., Huot, L., Renault, G.: Sub-cubic change of ordering for Gröbner basis: A probabilistic approach. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. p. 170–177. ISSAC ’14, Association for Computing Machinery, New York, NY, USA (2014). doi:10.1145/2608628.2608669
  * [28] Faugère, J.C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993). doi:10.1006/jsco.1993.1051
  * [29] Faugère, J.C., Mou, C.: Sparse FGLM algorithms. J. Symb. Comput. 80, 538–569 (2017). doi:https://doi.org/10.1016/j.jsc.2016.07.025
  * [30] Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953 (2019), https://eprint.iacr.org/2019/953
  * [31] Grassi, L., Hao, Y., Rechberger, C., Schofnegger, M., Walch, R., Wang, Q.: Horst meets Fluid-SPN: Griffin for zero-knowledge applications. Cryptology ePrint Archive, Paper 2022/403 (2022), https://eprint.iacr.org/2022/403, Version: 20230214:131048
  * [32] Grassi, L., Khovratovich, D., Lüftenegger, R., Rechberger, C., Schofnegger, M., Walch, R.: Reinforced Concrete: A fast hash function for verifiable computation. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. p. 1323–1335. CCS ’22, Association for Computing Machinery, New York, NY, USA (2022). doi:10.1145/3548606.3560686
  * [33] Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: A new hash function for zero-knowledge proof systems. In: Bailey, M., Greenstadt, R. (eds.) USENIX Security 2021: 30th USENIX Security Symposium. pp. 519–535. USENIX Association (Aug 11–13, 2021)
  * [34] Grassi, L., Lüftenegger, R., Rechberger, C., Rotaru, D., Schofnegger, M.: On a generalization of substitution-permutation networks: The HADES design strategy. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology – EUROCRYPT 2020, Part II. Lecture Notes in Computer Science, vol. 12106, pp. 674–704. Springer, Heidelberg, Germany, Zagreb, Croatia (May 10–14, 2020). doi:10.1007/978-3-030-45724-2_23
  * [35] Hopwood, D., Bowe, S., Hornby, T., Wilcox, N.: Zcash protocol specification (2022), https://github.com/zcash/zips/blob/main/protocol/protocol.pdf, Version: 2022.3.8
  * [36] Jakobsen, T., Knudsen, L.R.: The interpolation attack on block ciphers. In: Biham, E. (ed.) Fast Software Encryption – FSE’97. Lecture Notes in Computer Science, vol. 1267, pp. 28–40. Springer, Heidelberg, Germany, Haifa, Israel (Jan 20–22, 1997). doi:10.1007/BFb0052332
  * [37] Joux, A., Peyrin, T.: Hash functions and the (amplified) boomerang attack. In: Menezes, A. (ed.) Advances in Cryptology – CRYPTO 2007. Lecture Notes in Computer Science, vol. 4622, pp. 244–263. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 19–23, 2007). doi:10.1007/978-3-540-74143-5_14
  * [38] Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) Fast Software Encryption – FSE’94. Lecture Notes in Computer Science, vol. 1008, pp. 196–211. Springer, Heidelberg, Germany, Leuven, Belgium (Dec 14–16, 1995). doi:10.1007/3-540-60590-8_16
  * [39] Knudsen, L.R., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) Fast Software Encryption – FSE 2002. Lecture Notes in Computer Science, vol. 2365, pp. 112–127. Springer, Heidelberg, Germany, Leuven, Belgium (Feb 4–6, 2002). doi:10.1007/3-540-45661-9_9
  * [40] Lai, X.: Higher order derivatives and differential cryptanalysis. In: Blahut, R.E., Costello, D.J., Maurer, U., Mittelholzer, T. (eds.) Communications and Cryptography: Two Sides of One Tapestry. pp. 227–233. Springer US, Boston, MA (1994). doi:10.1007/978-1-4615-2694-0_23
  * [41] Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: Rebound distinguishers: Results on the full Whirlpool compression function. In: Matsui, M. (ed.) Advances in Cryptology – ASIACRYPT 2009. Lecture Notes in Computer Science, vol. 5912, pp. 126–143. Springer, Heidelberg, Germany, Tokyo, Japan (Dec 6–10, 2009). doi:10.1007/978-3-642-10366-7_8
  * [42] Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: van Hulzen, J.A. (ed.) Computer Algebra. Lecture Notes in Computer Science, vol. 162, pp. 146–156. Springer Berlin Heidelberg (1983). doi:10.1007/3-540-12868-9_99
  * [43] Lidl, R., Niederreiter, H.: Finite fields. Encyclopedia of mathematics and its applications, Cambridge Univ. Press, Cambridge, 2 edn. (1997)
  * [44] Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) Advances in Cryptology – EUROCRYPT’93. Lecture Notes in Computer Science, vol. 765, pp. 386–397. Springer, Heidelberg, Germany, Lofthus, Norway (May 23–27, 1994). doi:10.1007/3-540-48285-7_33
  * [45] Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: The rebound attack: Cryptanalysis of reduced Whirlpool and Grøstl. In: Dunkelman, O. (ed.) Fast Software Encryption – FSE 2009. Lecture Notes in Computer Science, vol. 5665, pp. 260–276. Springer, Heidelberg, Germany, Leuven, Belgium (Feb 22–25, 2009). doi:10.1007/978-3-642-03317-9_16
  * [46] Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) Advances in Cryptology – EUROCRYPT’93. Lecture Notes in Computer Science, vol. 765, pp. 55–64. Springer, Heidelberg, Germany, Lofthus, Norway (May 23–27, 1994). doi:10.1007/3-540-48285-7_6
  * [47] OSCAR – open source computer algebra research system, Version: 0.12.0 (2023), https://oscar.computeralgebra.de
  * [48] Roy, A., Steiner, M.: Generalized triangular dynamical system: An algebraic system for constructing cryptographic permutations over finite fields. arXiv: 2204.01802 (2022). doi:10.48550/ARXIV.2204.01802, Version: 6
  * [49] Roy, A., Steiner, M.J., Trevisani, S.: Arion: Arithmetization-oriented permutation and hashing from generalized triangular dynamical systems. arXiv: 2303.04639 (2023). doi:10.48550/ARXIV.2303.04639, Version: 3
  * [50] SCIPR Lab: libsnark: a `c++` library for zkSNARK proofs (2017), https://github.com/scipr-lab/libsnark
  * [51] The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.3) (2022), https://www.sagemath.org
  * [52] Wagner, D.: The boomerang attack. In: Knudsen, L.R. (ed.) Fast Software Encryption – FSE’99. Lecture Notes in Computer Science, vol. 1636, pp. 156–170. Springer, Heidelberg, Germany, Rome, Italy (Mar 24–26, 1999). doi:10.1007/3-540-48519-8_12

##  Appendix 0.A Statistical Attacks on Arion

###  0.A.1 Differential Cryptanalysis

Differential cryptanalysis [13] and its variants are the most widely applied
attack vectors against symmetric-key ciphers and hash functions. It is based
on the propagation of input differences through the rounds of a block cipher.
In its base form an attacker requests the ciphertexts for large numbers of
chosen plaintexts. Then he assumes that for $r-1$ rounds the input difference
is $\boldsymbol{\Delta x}\in\mathbb{F}_{q}^{n}\setminus\\{\mathbf{0}\\}$ and
the output difference is $\boldsymbol{\Delta y}\in\mathbb{F}_{q}^{n}$. Under
the assumption that the differences in the last round are fixed the attacker
can then deduce the possible keys. The key quantity to estimate the
effectiveness of differential cryptanalysis is the so-called differential
uniformity.

######  Definition 0.A.1 (see [46])

Let $\mathbb{F}_{q}$ be a finite field, and let
$f:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}^{m}$ be a function.

  1. (1)

The differential distribution table of $f$ at
$\mathbf{a}\in\mathbb{F}_{q}^{n}$ and $\mathbf{b}\in\mathbb{F}_{q}^{m}$ is
defined as

$\delta_{f}(\mathbf{a},\mathbf{b})=\left|\\{\mathbf{x}\in\mathbb{F}_{q}^{n}\mid
f(\mathbf{x}+\mathbf{a})-f(\mathbf{x})=f(\mathbf{b})\\}\right|.$

  2. (2)

The differential uniformity of $f$ is defined as

$\delta(f)=\max_{\begin{subarray}{c}\mathbf{a}\in\mathbb{F}_{q}^{n}\setminus\\{\mathbf{0}\\},\\\
\mathbf{b}\in\mathbb{F}_{q}^{m}\end{subarray}}\delta_{f}(\mathbf{a},\mathbf{b}).$

Given the differential uniformity of a function one can upper bound the
success probability of differential cryptanalysis with input differences
$\boldsymbol{\Delta x}\in\mathbb{F}_{q}^{n}\setminus\\{\mathbf{0}\\}$ and
$\boldsymbol{\Delta y}\in\mathbb{F}_{q}^{m}$ by

$\operatorname{\mathbb{P}}\left[f\\!:\boldsymbol{\Delta
x}\to\boldsymbol{\Delta y}\right]\leq\frac{\delta(f)}{q^{n}}.$ (19)

Naturally, the lower the differential uniformity the stronger is the
resistance of a block cipher against differential cryptanalysis.

By the choice of our parameters of Arion, see Theorem 2.1 and thereafter, we
have that $d_{2}\geq d_{1}$. With [48, Theorem 18, Corollary 19] the maximal
success probability of any differential for the Arion GTDS is bounded by

$\operatorname{\mathbb{P}}\left[\mathcal{F}_{\textsf{Arion}}\\!:\boldsymbol{\Delta
x}\to\boldsymbol{\Delta
y}\right]\leq\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}\left(\boldsymbol{\Delta
x}\right)}\leq\frac{d_{2}}{p},$ (20)

where $\boldsymbol{\Delta x}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}$,
$\boldsymbol{\Delta y}\in\mathbb{F}_{p}^{n}$, and
$1\leq\operatorname{wt}\left(\boldsymbol{\Delta x}\right)\leq n$ denotes the
Hamming weight, i.e. the number of non-zero entries, of $\boldsymbol{\Delta
x}$. Since $\mathcal{R}_{\mathbf{k}}^{(i)}$ and
$\mathcal{F}_{\textsf{Arion}}^{(i)}$ are affine equivalent Equation 20 also
applies to $\mathcal{R}_{\mathbf{k}}^{(i)}$. For Arion we use a differential
in every round. If we assume that the differentials are independent among the
rounds of Arion, then

$\operatorname{\mathbb{P}}\left[\mathcal{R}_{\mathbf{k}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}}^{(1)}\\!:\boldsymbol{\Delta
x}_{1}\to\ldots\to\boldsymbol{\Delta
x}_{r+1}\right]\leq\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x}_{1})+\ldots+\operatorname{wt}(\boldsymbol{\Delta x}_{r})}.$ (21)

Therefore, we can estimate the security level $\kappa$ of Arion against any
differential trail via

$\left(\frac{d_{2}}{p}\right)^{r}\leq 2^{-\kappa}\Longrightarrow\kappa\leq
r\cdot\Big{(}\log_{2}\left(p\right)-\log_{2}\left(d_{2}\right)\Big{)}.$ (22)

In Table 8 we list the security level of Arion against a differential
characteristic for different prime sizes.

Table 8: Security level of Arion against any differential characteristic for $p\geq 2^{N}$ and $d_{2}\leq 2^{9}$. $r$ |  $N$ |  $\kappa$ (bits)
---|---|---
$3$ |  $60$ |  $153$
$2$ |  $120$ |  $222$
$1$ |  $250$ |  $241$

With Equation 21 we can also estimate the probability of the differential hull
of Arion.

######  Theorem 0.A.2 (Differential hull of Arion)

Let $p\in\mathbb{Z}$ be a prime and let $\mathbb{F}_{p}$ be the field with $p$
elements, and let $n>1$ and $r\geq 1$ be integers. Let
$\mathcal{R}_{\mathbf{k}}^{(1)},\dots,\mathcal{R}_{\mathbf{k}}^{(r)}:\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$
be Arion round functions, and let $\boldsymbol{\Delta
x}_{1},\boldsymbol{\Delta x}_{r+1}\in\mathbb{F}_{p}^{n}$ be such that
$\boldsymbol{\Delta x}_{1}\neq\mathbf{0}$. Assume that the differentials among
the rounds of Arion are independent. Then

$\operatorname{\mathbb{P}}\left[\mathcal{R}_{\mathbf{k}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}}^{(1)}\\!:\boldsymbol{\Delta
x}_{1}\to\boldsymbol{\Delta
x}_{r+1}\right]\leq\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x}_{1})}\cdot\Big{(}\left(d_{2}+1\right)^{n}-1\Big{)}^{r-1}.$

###### Proof

Let us first do some elementary rearrangements and estimations

$\displaystyle\operatorname{\mathbb{P}}\left[\mathcal{R}_{\mathbf{k}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}}^{(1)}\\!:\boldsymbol{\Delta
x}_{1}\to\boldsymbol{\Delta x}_{r}\right]$
$\displaystyle=\sum_{\boldsymbol{\Delta x}_{2},\dots,\boldsymbol{\Delta
x}_{r}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}}\operatorname{\mathbb{P}}\left[\bigcap_{i=1}^{r}\left\\{\mathcal{R}_{\mathbf{k}}^{(i)}\\!:\boldsymbol{\Delta
x}_{i}\to\boldsymbol{\Delta x}_{i+1}\right\\}\right]$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{=}}\sum_{\boldsymbol{\Delta
x}_{2},\dots,\boldsymbol{\Delta
x}_{r}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}}\operatorname{\mathbb{P}}\left[\bigcap_{i=1}^{r}\left\\{\mathcal{F}_{\textsf{Arion}}^{(i)}\\!:\boldsymbol{\Delta
x}_{i}\to\operatorname{circ}(1,\dots,n)^{-1}\boldsymbol{\Delta
x}_{i+1}\right\\}\right]$
$\displaystyle\stackrel{{\scriptstyle(2)}}{{=}}\sum_{\boldsymbol{\Delta
x}_{2},\dots,\boldsymbol{\Delta
x}_{r}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}}\operatorname{\mathbb{P}}\left[\bigcap_{i=1}^{r}\left\\{\mathcal{F}_{\textsf{Arion}}^{(i)}\\!:\boldsymbol{\Delta
x}_{i}\to\boldsymbol{\Delta x}_{i+1}\right\\}\right]$
$\displaystyle\stackrel{{\scriptstyle(3)}}{{\leq}}\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x}_{1})}\cdot\sum_{\boldsymbol{\Delta x}_{2},\dots,\boldsymbol{\Delta
x}_{r}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}}\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x}_{2})+\ldots+\operatorname{wt}(\boldsymbol{\Delta x}_{r})}.$

In $(1)$ we expanded the definition of the round function and inverted the
circulant matrix, in $(2)$ we exploited that we sum over all possible
differentials and that the affine Arion layer is invertible, moreover we
implicitly substituted $\boldsymbol{\Delta
x}_{r+1}=\operatorname{circ}(1,\dots,n)^{-1}\boldsymbol{\Delta x}_{r+1}$.
Finally, in $(3)$ we applied Equation 21. For ease of writing we compute the
sum only for one difference variable, then

$\displaystyle\sum_{\boldsymbol{\Delta
x}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}}\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x})}\stackrel{{\scriptstyle(4)}}{{=}}\sum_{i=1}^{n}(p-1)^{i}\cdot\binom{n}{i}\cdot\left(\frac{d_{2}}{p}\right)^{i}$
$\displaystyle\leq\sum_{i=1}^{n}\binom{n}{i}\cdot
d_{2}^{i}=\left(d_{2}+1\right)^{n}-1,$

where in $(4)$ we used that there are $(p-1)^{i}\cdot\binom{n}{i}$ many
vectors $\boldsymbol{\Delta x}\in\mathbb{F}_{p}^{n}$ with
$\operatorname{wt}(\boldsymbol{\Delta x})=i$. This proves the claim. ∎

###### Remark 0.A.3

This estimation can be performed over any finite field $\mathbb{F}_{q}$, any
invertible affine layer, and any primitive whose differential uniformity at
round level is in $\mathcal{O}\left(p^{-\operatorname{wt}(\boldsymbol{\Delta
x})}\right)$.

With the theorem we can now estimate the security level of Arion with respect
to differential cryptanalysis and the full differential hull via

$\displaystyle\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x}_{1})}\cdot\Big{(}\left(d_{2}+1\right)^{n}-1\Big{)}^{r-1}\leq 2^{-\kappa}$
(23)
$\displaystyle\Longrightarrow\kappa\leq\operatorname{wt}(\boldsymbol{\Delta
x}_{1})\cdot\Big{(}\log_{2}\left(p\right)-\log_{2}\left(d_{2}\right)\Big{)}-\left(r-1\right)\cdot\log_{2}\Big{(}\left(d_{2}+1\right)^{n}-1\Big{)}.$
(24)

In Table 9 report the security level for Arion against differential
cryptanalysis utilizing the full differential hull with the parameters from
Table 3 and different field sizes. Since our probability estimation from
Theorem 0.A.2 could in principle be $>1$ for some parameters combinations, we
always report the security level with respect to the smallest
$\operatorname{wt}(\boldsymbol{\Delta x}_{1})$ such that the probability
estimate is $<1$.

Table 9: Security level of Arion against any differential characteristic for
$p\geq 2^{N}$ and $d_{2}\leq 257$ with the full differential hull.

| $N=60$ | $N=120$ | $N=250$
---|---|---|---
$n$ |  $3$ |  $4$ |  $4$ |  $5$ |  $6$ |  $8$ |  $3$ |  $4$ |  $4$ |  $5$ |  $6$ |  $8$ |  $3$ |  $4$ |  $4$ |  $5$ |  $6$ |  $8$
$r$ |  $6$ |  $5$ |  $6$ |  $5$ |  $5$ |  $4$ |  $6$ |  $5$ |  $6$ |  $5$ |  $5$ |  $4$ |  $6$ |  $5$ |  $6$ |  $5$ |  $5$ |  $4$
$\operatorname{wt}(\boldsymbol{\Delta x}_{1})$ |  $3$ |  $3$ |  $4$ |  $4$ |  $4$ |  $4$ |  $2$ |  $2$ |  $2$ |  $2$ |  $1$ |  $2$ |  $1$ |  $1$ |  $1$ |  $1$ |  $1$ |  $1$
$\kappa$ (bits) |  $35$ |  $27$ |  $47$ |  $47$ |  $15$ |  $15$ |  $103$ |  $95$ |  $63$ |  $63$ |  $31$ |  $31$ |  $121$ |  $113$ |  $81$ |  $81$ |  $49$ |  $49$

Although, our target security of $128$ bit is never met we should keep in mind
that the full differential hull is of size $(p-1)^{n\cdot(r-1)}$. E.g., for
our target primes $\text{BLS}12$ and $\text{BN}254$ the smallest differential
hull is of size $\approx 2^{250\cdot 15}$, and for $60$ bit prime fields the
smallest differential hull still would be of size $2^{60\cdot 15}$. Therefore,
we do not expect that differential cryptanalysis can break Arion & ArionHash
within the $128$ bit security target.

Nevertheless, to convince skeptical readers we provide another hull estimation
for a computationally limited adversary, i.e. an adversary who can only search
a restricted number of differences within the differential hull.

######  Lemma 0.A.4 (Restricted differential hull of Arion)

Let $p\in\mathbb{Z}$ be a prime and let $\mathbb{F}_{p}$ be the field with $p$
elements, and let $n>1$ and $r\geq 1$ be integers. Let
$\mathcal{R}_{\mathbf{k}}^{(1)},\dots,\mathcal{R}_{\mathbf{k}}^{(r)}:\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$
be Arion round functions, and let $\boldsymbol{\Delta
x}_{1},\boldsymbol{\Delta x}_{r+1}\in\mathbb{F}_{p}^{n}$ be such that
$\boldsymbol{\Delta x}_{1}\neq\mathbf{0}$. Assume that the differentials among
the rounds of Arion are independent and that in every round only up to
$M<(p-1)\cdot n$ many differences $\boldsymbol{\Delta
x}_{i}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}$ can be utilized. Then

$\operatorname{\mathbb{P}}\left[\mathcal{R}_{\mathbf{k}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}}^{(1)}\\!:\boldsymbol{\Delta
x}_{1}\to\boldsymbol{\Delta
x}_{r+1}\right]\leq\left(\frac{d_{2}}{p}\right)^{\operatorname{wt}(\boldsymbol{\Delta
x}_{1})}\cdot\left(\frac{M\cdot d_{2}}{p}\right)^{r-1}.$

###### Proof

Recall that the bound for the differential uniformity of the Arion GTDS is
maximal if there is only one non-zero entry in $\boldsymbol{\Delta
x}\in\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}$, see Equation 20. In every
intermediate round there are $(p-1)\cdot n$ many differences with one non-zero
entry, hence to maximize the estimation we first sum over those elements. With
Equation 21 we then obtain the claimed inequality. ∎

Provided that $M<\frac{p}{d_{2}}$, then the inequality is always less than
$1$. For the restricted differential hull we can then estimate the security
level of Arion via

$\displaystyle M^{r-1}\cdot\left(\frac{d_{2}}{p}\right)^{r}\leq 2^{-\kappa}$
(25) $\displaystyle\Longrightarrow\kappa\leq
r\cdot\Big{(}\log_{2}\left(p\right)-\log_{2}\left(d_{2}\right)\Big{)}-\left(r-1\right)\cdot\log_{2}\left(M\right).$
(26)

In Table 10 we report round number for various field sizes that achieve at
least $128$ bit security for a restricted hull of size $\sqrt{p}$ at round
level.

Table 10: Security level of Arion against differential cryptanalysis for $p\geq 2^{N}$ and $d_{2}\leq 257$ with a restricted differential hull of size $2^{N/2}$ at round level. $r$ |  $N$ |  $\kappa$ (bits)
---|---|---
$5$ |  $60$ |  $139$
$4$ |  $120$ |  $267$
$3$ |  $250$ |  $475$

###  0.A.2 Truncated Differential and Rebound Attacks

In a truncated differential attack [38] an attacker can only predict parts of
the difference between pairs of text. We expect that the Arion GTDS admits
truncated differentials with probability $1$. For example
$\left(0,\dots,0,\alpha\right)^{\intercal}\xrightarrow{\mathcal{F}_{\textsf{Arion}}}\operatorname{circ}\left(1,\dots,n\right)\left(0,\dots,0,\beta\right)^{\intercal}$
where $\alpha,\beta\in\mathbb{F}_{p}^{\times}$. Note that for any vector
$\mathbf{v}\in\mathbb{F}_{p}^{n}$ with $\operatorname{wt}(\mathbf{v})$ one
always has that
$\operatorname{wt}\big{(}\operatorname{circ}\left(1,\dots,n\right)\mathbf{v}\big{)}=n$.
Therefore, for any truncated differential of the Arion GTDS where only one
element is active in the input and output one has that all components are
active after application of the affine layer of Arion. For truncated
differentials we then estimate the security level of Arion via

$M\cdot\left(\frac{d_{2}}{p}\right)^{n}\leq
2^{-\kappa}\Longrightarrow\kappa\leq
n\cdot\left(\log_{2}\left(p\right)-\log_{2}\left(d_{2}\right)\right)-\log_{2}\left(M\right),$
(27)

where $M$ denotes the size of the restricted differential hull available to a
computationally limited adversary. In Table 11 we report the security level
for various parameters. For primes of size $p\geq 2^{120}$ one full round is
already sufficient to achieve $128$ bit security for a restricted differential
hull of size $M\geq 2^{120}$. On the other hand for $p\geq 2^{60}$ the
security target is not met. Therefore, if one would like to instantiate Arion
& ArionHash over such a prime one also has to consider later rounds.

Table 11: Security level of Arion against truncated differential cryptanalysis with weight $1$ truncated differentials in the first round and for $p\geq 2^{N}$ and $d_{2}\leq 257$ with a restricted differential hull of size $2^{M}$. $N$ |  $n$ |  $M$ |  $\kappa$ (bits)
---|---|---|---
$60$ |  $4$ |  $100$ |  $107$
$120$ |  $3$ |  $120$ |  $215$
$250$ |  $3$ |  $250$ |  $475$

Suppose an adversary can cover two rounds with a truncated differential of
probability $1$, his best bet is to search the remaining rounds for
input/output differentials of weight $1$. For such an adversary we can then
estimate the security level as

$\left(M\cdot\frac{d_{2}}{p}\right)^{r-2}\leq
2^{-\kappa}\Longrightarrow\kappa\leq\left(r-2\right)\cdot\left(\log_{2}\left(p\right)-\log_{2}\left(d_{2}\right)-\log_{2}\left(M\right)\right),$
(28)

where $M$ denotes the size of the restricted differential hull available to a
computationally limited adversary at round level. In Table 12 we report the
security level for various parameters. For primes of size $p\geq 2^{250}$ four
rounds of Arion are sufficient to protect against two round truncated
differentials of probability $1$ within the $128$ bit security target. On the
other hand, for primes of size $p\geq 2^{60}$ one needs at least $6$ rounds to
meet the $128$ bit security target.

Table 12: Security level of Arion against two round truncated differentials for $p\geq 2^{N}$ and $d_{2}\leq 257$ with a restricted differential hull of size $2^{N/2}$ at round level. $N$ |  $r-2$ |  $\kappa$ (bits)
---|---|---
$60$ |  $4$ |  $87$
$120$ |  $3$ |  $155$
$250$ |  $2$ |  $233$

In a rebound attack [41, 45] one has to find two input/output pairs such that
the inputs satisfy a certain (truncated) input difference and the outputs
satisfy a certain (truncated) output difference. Such an attack can be split
into two phases: an inbound and an outbound phase. Let
$P_{\textsf{Arion}}:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}^{n}$ be the target
permutation, then we split it into three sub-parts
$P_{\textsf{Arion}}=P_{fw}\circ P_{in}\circ P_{out}$. The inbound phase is
placed in the middle preceded and followed by the two outbound phases. Then,
in the outbound phase two high-probability (truncated) differential trails are
constructed which are connected with the inbound phase. Since a truncated
differential with probability $1$ can only cover a single round an attacker
can cover only $r-2$ rounds with an inside-out approach. By Table 12, for our
target primes $\text{BLS}12$ and $\text{BN}254$ two inbound rounds are
sufficient to achieve the $128$ bit security target. So in total $4$ rounds
are sufficient to nullify this attack vector.

###  0.A.3 Linear Cryptanalysis

In linear cryptanalysis [44, 5] one tries to discover affine approximations of
round functions for a sample of known plaintexts. The key quantity to estimate
the effectiveness of linear cryptanalysis is the so-called correlation. We
denote with $\braket{\mathbf{a},\mathbf{b}}=\sum_{i=1}^{n}a_{i}\cdot b_{i}$
the scalar product over $\mathbb{F}_{q}^{n}$.

######  Definition 0.A.5 (see [5, Definition 6, 15])

Let $\mathbb{F}_{q}$ be a finite field, let $n\geq 1$, let
$\chi:\mathbb{F}_{q}\to\mathbb{C}$ be a non-trivial additive character, let
$F:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}^{n}$ be a function, and let
$\mathbf{a},\mathbf{b}\in\mathbb{F}_{q}^{n}$.

  1. (1)

The correlation for the character $\chi$ of the linear approximation
$(\mathbf{a},\mathbf{b})$ of $F$ is defined as

$\operatorname{CORR}_{F}(\chi,\mathbf{a},\mathbf{b})=\frac{1}{q^{n}}\cdot\sum_{\mathbf{x}\in\mathbb{F}_{q}^{n}}\chi\Big{(}\big{<}\mathbf{a},F(\mathbf{x})\big{>}+\braket{\mathbf{b},\mathbf{x}}\\!\Big{)}.$

  2. (2)

The linear probability for the character $\chi$ of the linear approximation
$(\mathbf{a},\mathbf{b})$ of $F$ is defined as

$\operatorname{LP}_{F}(\chi,\mathbf{a},\mathbf{b})=\left|\operatorname{CORR}_{F}(\chi,\mathbf{a},\mathbf{b})\right|^{2}.$

###### Remark 0.A.6

To be precise Baignères et al. [5] defined linear cryptanalysis over arbitrary
abelian groups, in particular for maximal generality they defined the
correlation with respect to two additive characters
$\chi,\psi:\mathbb{F}_{q}\to\mathbb{C}$ as

$\operatorname{CORR}_{F}(\chi,\psi,\mathbf{a},\mathbf{b})=\frac{1}{q^{n}}\cdot\sum_{\mathbf{x}\in\mathbb{F}_{q}^{n}}\chi\Big{(}\big{<}\mathbf{a},F(\mathbf{x})\big{>}\Big{)}\cdot\psi\Big{(}\big{<}\mathbf{b},\mathbf{x}\big{>}\\!\Big{)}.$
(29)

Let $\mathbb{F}_{q}$ be a finite field of characteristic $p$, and let
$\operatorname{Tr}:\mathbb{F}_{q}\to\mathbb{F}_{p}$ be the absolute trace
function, see [43, 2.22. Definition]. For all $x\in\mathbb{F}_{q}$ we define
the function $\chi_{1}$ as

$\chi_{1}(x)=\exp\left(\frac{2\cdot\pi\cdot
i}{p}\cdot\operatorname{Tr}(x)\right).$

Then for every non-trivial additive character
$\chi:\mathbb{F}_{q}\to\mathbb{C}$ there exist $a\in\mathbb{F}_{q}^{\times}$
such that $\chi(x)=\chi_{1}(a\cdot x)$, see [43, 5.7. Theorem]. Therefore,
after an appropriate rescaling that we either absorb into $\mathbf{a}$ or
$\mathbf{b}$ we can transform Equation 29 into Theorem 0.A.5 (1).

For Arion we approximate every round by affine functions, and we call the
tuple
$\Omega=(\mathbf{a}_{0},\dots,\mathbf{a}_{r})\subset\left(\mathbb{F}_{p}^{n}\right)^{r+1}$
a linear trail for Arion, where $(\mathbf{a}_{i-1},\mathbf{a}_{i})$ is the
affine approximation of the $i$th round. Note that for
$\mathbf{A}\in\mathbb{F}_{p}^{n\times n}$ and
$\mathbf{c}\in\mathbb{F}_{p}^{n}$ one has that
$\operatorname{LP}_{\mathbf{A}F+\mathbf{c}}(\chi,\mathbf{a},\mathbf{b})=\operatorname{LP}_{F}(\chi,\mathbf{A}^{\intercal}\mathbf{a},\mathbf{b})$.
I.e., to bound the correlation of a single round it suffices to bound the
correlation of the Arion GTDS. By [48, Theorem 24, Corollary 25] we have that

$\operatorname{LP}_{\mathcal{F}_{\textsf{Arion}}}(\chi,\mathbf{a},\mathbf{b})\leq\begin{dcases}1,&\mathbf{a},\mathbf{b}=\mathbf{0},\\\
\frac{\left(d_{2}-1\right)^{2}}{q},&\text{else}.\end{dcases}$ (30)

If we assume that the approximations among the rounds of Arion are
independent, then

$\operatorname{LP}_{\textsf{Arion}}(\chi,\Omega)\leq\left(\frac{\left(d_{2}-1\right)^{2}}{q}\right)^{r}.$
(31)

If a distinguisher is limited to $D$ queries, then under heuristic assumptions
Baignères et al. proved [5, Theorem 7] that the advantage of a distinguisher,
which we call success probability, for a single linear trail is lower bounded
by

$p_{success}\succeq
1-e^{-\frac{D}{4}\cdot\operatorname{LP}_{\textsf{Arion}}(\chi,\Omega)}\leq
1-e^{-\frac{D}{4}\cdot\left(\frac{\left(d_{2}-1\right)^{2}}{q}\right)^{r}}.$
(32)

For $p\geq 2^{N}$ and $d_{2}\leq 2^{M}$ we approximate $\exp(-x)\approx 1-x$
and estimate the security level $\kappa$ of Arion against a linear trail
$\Omega$ as

$\displaystyle p_{success}$
$\displaystyle\approx\frac{D}{4}\cdot\left(\frac{\left(d_{2}-1\right)^{2}}{q}\right)^{r}\leq\frac{D}{4}\cdot
2^{r\cdot(2\cdot M-N)}\leq 2^{-\kappa}$ (33)
$\displaystyle\Longrightarrow\kappa$ $\displaystyle\leq 2+r\cdot\left(N-2\cdot
M\right)-\log_{2}\left(D\right).$ (34)

Now recall that Arion is supposed to be instantiated with a $64$ bit prime
number $p\gtrsim 2^{64}$ and that
$d_{2}\in\\{121,123,125,129,161,193,195,257\\}$, then Equation 33 implies the
following security levels for Arion.

Table 13: Security level of Arion against any linear trail for $p\geq 2^{N}$, $d_{2}\leq 2^{9}$ and data amount $2^{M}$. | $N=60$ | $N=120$ | $N=250$
---|---|---|---
x$r$x | $5$ | $6$ | $8$ | $3$ | $4$ | $2$ | $3$
x$M$x | $60$ | $120$ | $180$ | $120$ | $240$ | $250$ | $500$
x$\kappa$ (bits)x |  x$152$x |  x$134$x |  x$158$x |  x$188$x |  x$170$x |  x$216$x |  x$198$x

For a computationally limited adversary we next derive an estimation of the
probability of a restricted linear hull.

######  Lemma 0.A.7 (Restricted linear hull of Arion)

Let $p\in\mathbb{Z}$ be a prime and let $\mathbb{F}_{p}$ be the field with $p$
elements, let $n>1$ and $r\geq 1$ be integers, and let
$\chi:\mathbb{F}_{p}\to\mathbb{C}$ be a non-trivial additive character. Let
$\mathcal{R}_{\mathbf{k}}^{(1)},\dots,\mathcal{R}_{\mathbf{k}}^{(r)}:\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$
be Arion round functions, and let
$(\mathbf{a}_{1},\mathbf{a}_{r})\in\left(\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}\right)^{2}\in\left(\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}\right)^{2}$.
Assume that the linear approximations among the rounds of Arion are
independent and that in every round only up to $M<(p-1)\cdot n$ many
approximations
$(\mathbf{a}_{i},\mathbf{a}_{i+1})\in\left(\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}\right)^{2}$
can be utilized. Then

$\operatorname{LP}_{\mathcal{R}_{\mathbf{k}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}}^{(1)}}(\chi,\mathbf{a}_{1},\mathbf{a}_{r})\leq
M^{r-1}\cdot\left(\frac{\left(d_{2}-1\right)^{2}}{p}\right)^{r}.$

###### Proof

By the independence of rounds we have that

$\displaystyle\operatorname{LP}_{\mathcal{R}_{\mathbf{k}}^{(r)}\circ\cdots\circ\mathcal{R}_{\mathbf{k}}^{(1)}}$
$\displaystyle=\sum_{\mathbf{a}_{2},\dots,\mathbf{a}_{r-1}}\prod_{i=1}^{r}\
\operatorname{LP}_{\mathcal{R}_{\mathbf{k}}^{(i)}}(\chi,\mathbf{a}_{i},\mathbf{a}_{i+1})$
$\displaystyle=\sum_{\mathbf{a}_{2},\dots,\mathbf{a}_{r-1}}\prod_{i=1}^{r}\
\operatorname{LP}_{\mathcal{F}^{(i)}}\left(\chi,\operatorname{circ}(1,\dots,n)^{\intercal}\mathbf{a}_{i},\mathbf{a}_{i+1}\right)$
$\displaystyle\leq\sum_{\mathbf{a}_{2},\dots,\mathbf{a}_{r-1}}\left(\frac{\left(d_{2}-1\right)^{2}}{p}\right)^{r}\leq
M^{r-1}\cdot\left(\frac{\left(d_{2}-1\right)^{2}}{p}\right)^{r}$

where the last two inequalities follow from Equation 30 and the assumption
that only $M$ approximations can be considered per round. ∎

Provided that $M<\frac{p}{\left(d_{2}-1\right)^{2}}$, then the inequality is
always less than $1$. For the restricted differential hull we can then
estimate the security level of Arion via

$\displaystyle
M^{r-1}\cdot\left(\frac{\left(d_{2}-1\right)^{2}}{p}\right)^{r}\leq
2^{-\kappa}$ (35) $\displaystyle\Longrightarrow\kappa\leq
r\cdot\Big{(}\log_{2}\left(p\right)-2\cdot\log_{2}\left(d_{2}-1\right)\Big{)}-\left(r-1\right)\cdot\log_{2}\left(M\right).$
(36)

In Table 14 we report round number for various field sizes that achieve at
least $128$ bit security for a restricted hull of size $\sqrt{p}$ at round
level.

Table 14: Security level of Arion against linear cryptanalysis for $p\geq 2^{N}$ and $d_{2}\leq 257$ with a restricted linear hull of size $2^{N/2}$ at round level. $r$ |  $N$ |  $\kappa$ (bits)
---|---|---
$5$ |  $60$ |  $139$
$4$ |  $120$ |  $267$
$3$ |  $250$ |  $475$

###  0.A.4 Other Statistical Attacks

By the definition of $\operatorname{circ}\left(1,\dots,n\right)$ a difference
in one component can affect the whole state by a single round function call.
Therefore, impossible differentials [12] and zero-correlation [15, 14] can
hardly be mounted on $3$ or more rounds.

Boomerang attacks [52, 37] search for quartets that satisfy two differential
paths simultaneously. For our target primes $\text{BLS}12$ and $\text{BN}254$
no differentials with high probability exist for more than two rounds, see
Equation 21. Therefore, a boomerang attack can hardly be mounted on $4$ rounds
of Arion & ArionHash.

##  Appendix 0.B Algebraic Attacks on Arion

###  0.B.1 Higher-Order Differential & Interpolation Attacks

Interpolation attacks [36] construct the polynomial vector representing a
cipher without knowledge of the secret key. If such an attack is successful
against a cipher, then an adversary can encrypt any plaintext without
knowledge of the secret key. For a hash function the interpolated polynomial
vector can be exploited to set up collision or forgery attacks. The cost of
interpolating a polynomial depends on the number of monomials present in the
polynomial vector representing the cipher function. Recall that any function
$F:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ can be represented by a unique
polynomial
$f\in\mathbb{F}_{q}[\mathbf{X}_{n}]=\mathbb{F}_{q}[x_{1},\dots,x_{n}]/\left(x_{1}^{q}-x_{1},\dots,x_{n}^{q}-x_{n}\right)$,
thus at most $q^{n}$ monomials can be present in $f$. Clearly, if $f$ is
dense, then an interpolation attack cannot be done faster than exhaustive
search.

Let $\mathcal{R}^{(i)}\subset\mathbb{F}_{p}[\mathbf{X}_{n}]$ denote the
polynomial vector of the Arion\- round function, we say that
$\mathcal{R}^{(i+1)}\circ\mathcal{R}^{(i)}$ has a degree overflow if we have
to reduce with at least one of the field equations to compute the unique
representation in $\mathbb{F}_{p}[\mathbf{X}_{n}]$. As we saw in Table 2, for
the fields $\text{BLS}12$ and $\text{BN}254$ some of our specified Arion
parameters already achieve a degree overflow in the first round. Moreover,
after the first round we expect that terms

$\left(\sum_{i=1}^{n}i\cdot x_{i}\right)^{e}+\sum_{i=1}^{n}i\cdot x_{i}$ (37)

are present in every branch. After another application of the round function
we expect to produce the terms

$\left(\left(\sum_{i=1}^{n}i\cdot x_{i}\right)^{e}+\sum_{i=1}^{n}i\cdot
x_{i}\right)^{e}\mod\left(x_{1}^{p}-x_{1},\dots,x_{n}^{p}-x_{n}\right)$ (38)

in every branch. By our specification $e$ is the inverse exponent of a
relatively low degree permutation, therefore we expect that the degrees of
some of the aforementioned terms are close to $p-2$. In particular, this is
the case if $e^{2}\geq p$. In addition, we also expect that a big fraction of
the monomials in $\mathbb{F}_{p}[\mathbf{X}_{n}]$ is present in the components
of the polynomial vector of Arion\- after at least two iterations. Although an
adversary can nullify the circulant matrix that is applied to the input vector
in some attack scenarios, he cannot do so for later rounds. Therefore, we
expect that at least after three rounds terms similar to Equation 38 are
present in the polynomial vector of Arion-. Further, to frustrate Meet-in-the-
Middle (MitM) attacks we require that the number of rounds $r\geq 4$.

We implemented Arion in `SageMath` [51] to compute the density of Arion\- for
small primes. Our findings in Table 15 suggest that after two rounds Arion\-
has already almost full density over $\mathbb{F}_{p}$.

Table 15: Observed minimum density for Arion\- for small primes, $n=3,4,5$ and $d_{1},d_{2}=3,5$. $p$ |  $r$ |  Minimum density after $2$ rounds |  Degree after $2$ rounds |  Univariate degree after $2$ rounds
---|---|---|---|---
$11$ |  $6$ |  $\geq 82\%$ |  $n\cdot(p-1)-1$ |  $p-1$
$13$ |  $6$ |  $\geq 91\%$ |  $n\cdot(p-1)-1$ |  $p-1$
$17$ |  $6$ |  $\geq 91\%$ |  $n\cdot(p-1)-1$ |  $p-1$
$19$ |  $6$ |  $\geq 92\%$ |  $n\cdot(p-1)-1$ |  $p-1$
$23$ |  $6$ |  $\geq 90\%$ |  $n\cdot(p-1)-1$ |  $p-1$

If after two rounds the density of Arion\- is $\geq 0.8\cdot p^{n}$, then for
$p=2^{60}$ and $n=3$ already more than $2^{128}$ terms are present in Arion-.
Therefore, we expect that Arion resists interpolation attacks with the full
key. An adversary can improve the capabilities of an interpolation attack by
guessing parts of the key. If he can guess $n-1$ parts correctly, then we
expect that all univariate polynomials in Arion have degree close to $p$. To
retrieve the remaining key an adversary has to factor at least one of the
polynomials, due to the high degree his best choice to perform a greatest
common divisor computation. We can then estimate the complexity with
$\mathcal{O}\big{(}p\cdot\log(p)\big{)}$. Therefore, for our target primes
$\text{BLS}12$ and $\text{BN}254$ this complexity always exceeds the $128$ bit
security target after two rounds.

For an interpolation attack on ArionHash we have a similar scenario as if we
guessed parts of the key of Arion. At worst only one input of ArionHash is
unknown to the adversary, he then still has to factor a polynomial of degree
close to $p$, as mentioned before we do not expect that this defeats the $128$
bit security target after two rounds.

Higher-order differential attacks [38, 40, 11] exploit that higher
differentials will vanish at some point. Since the density of Arion\- exceeds
$\geq 0.8\cdot p^{n}$ after two rounds and its univariate degrees are close to
$p$, we do not expect that higher-order differentials and distinguishers on
Arion & ArionHash can undermine the $128$ bit security target for our target
primes $\text{BLS}12$ and $\text{BN}254$ after two rounds.

###  0.B.2 Integral Attacks

The notion of integral cryptanalysis was introduced by Knudsen & Wagner [39]
and generalized to arbitrary finite fields by Beyne et al. [11]. It is based
on the following properties of polynomial valued functions.

######  Proposition 0.B.1 (see [11, Proposition 1, 2])

Let $\mathbb{F}_{q}$ be a finite field, and let
$F:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ be a polynomial valued function.

  1. (1)

Let $V\subset\mathbb{F}_{q}^{n}$ be an affine subspace of dimension $k$. If
$\deg\left(F\right)<k\cdot\left(q-1\right)$, then

$\sum_{\mathbf{x}\in V}F(\mathbf{x})=0.$

  2. (2)

Let $G_{1},\dots,G_{n}\subset\mathbb{F}_{q}^{\times}$ be multiplicative
subgroups, and let $G=\bigtimes_{i=1}^{n}G_{i}$ their product group. If
$\deg_{x_{i}}\left(F\right)<\left|G_{i}\right|$ for all $1\leq i\leq n$, then

$\sum_{\mathbf{x}\in G}F(\mathbf{x})-\left|G\right|\cdot F(\mathbf{0})=0.$

###### Proof

(1) was proven in [11, Corollary 1], for (2) we index the terms of $F$ by $j$
and then rearrange the sum

$\displaystyle\sum_{\mathbf{x}\in G}F(\mathbf{x})$
$\displaystyle=\sum_{x_{1}\in G_{1},\dots,x_{n}\in G_{n}}\ \sum_{j\geq
0}a_{j}\cdot x_{1}^{k_{1,j}}\cdots x_{n}^{k_{n,j}}$ $\displaystyle=\sum_{j\geq
0}\ \sum_{x_{1}\in G_{1},\dots,x_{n}\in G_{n}}a_{j}\cdot x_{1}^{k_{1,j}}\cdots
x_{n}^{k_{n,j}}.$

For the zero term this sums to $\left|G\right|\cdot F(\mathbf{0})$, now assume
that at least one $k_{i,j}>0$, say $k_{1,j}$, then we further rearrange

$\sum_{x_{1}\in G_{1},\dots,x_{n}\in G_{n}}a_{j}\cdot x_{1}^{k_{1,j}}\cdots
x_{n}^{k_{n,j}}=\sum_{x_{2}\in G_{1},\dots,x_{n}\in G_{n}}\left(\sum_{x_{1}\in
G_{1}}a_{j}\cdot x_{1}^{k_{1,j}}\cdots x_{n}^{k_{n,j}}\right).$

For the inner sum on the right-hand side we can consider $x_{2},\dots,x_{n}$
as non-zero field elements, by assumption $k_{1,j}<\left|G_{1}\right|$ so by
[11, Proposition 2] the sum vanishes. This proves the claim. ∎

Let us investigate the capabilities of integral distinguishers on Arion-.
Without loss of generality we can ignore the application
$\operatorname{circ}(1,\dots,n)$ before the first Arion GTDS. To minimize the
degree after the first Arion GTDS we fix all inputs except $x_{1}$, then only
the first component is non-constant in $x_{1}$, but after application of the
first affine layer all components contain the monomial $x_{1}^{d_{1}}$. With
our findings from interpolation attacks we expect that two additional rounds
of Arion\- are sufficient to increase the degree in $x_{1}$ of all components
to at least $p-2$.

Therefore, for our target fields $\text{BLS}12$ and $\text{BN}254$ we do not
expect that integral attacks can invalidate our $128$ bit security target
after two rounds of Arion & ArionHash. On the other hand, if Arion or
ArionHash are instantiated over prime fields $p<2^{128}$, then integral
attacks could be a non-negligible threat since the degree of a univariate
function can never exceed $p$.

##  Appendix 0.C Gröbner Basis Analysis

In a Gröbner basis attack [17, 21] the adversary represents a cryptographic
function as fully determined system of polynomial equations and then solves
for the solutions of the system. Since the system is fully determined at least
one solution of the polynomial system must contain the quantity of interest,
e.g. the key of a block cipher or the preimage of a hash function. In general,
a Gröbner basis attack proceeds in four steps:

  1. (1)

Model the cryptographic function with a (iterated) system of polynomials.

  2. (2)

Compute a Gröbner basis with respect to an efficient term order, e.g., the
degree reverse lexicographic (DRL) order.

  3. (3)

Perform a term order conversion to an elimination order, e.g., the
lexicographic (LEX) order.

  4. (4)

Solve the univariate equation.

Let us for the moment assume that an adversary has already found a Gröbner
basis and discuss the complexity of the remaining steps. Let $k$ be a field,
let $I\subset k[x_{1},\dots,x_{n}]$ be a zero-dimensional ideal modeling a
cryptographic function, and let
$d=\dim_{k}\left(k[x_{1},\dots,x_{n}]/I\right)$ be the $k$-vector space
dimension of the quotient space. With the original FGLM algorithm [28] the
complexity of term order conversion is $\mathcal{O}\left(n\cdot d^{3}\right)$,
but improved versions with probabilistic methods achieve
$\mathcal{O}\left(n\cdot d^{\omega}\right)$ [27], where $2\leq\omega<2.3727$,
and sparse linear algebra algorithms [29] achieve
$\mathcal{O}\left(\sqrt{n}\cdot d^{2+\frac{n-1}{n}}\right)$. To find the roots
of the univariate polynomial from the elimination Gröbner basis333 If $I$ is a
radical ideal, then the degree of the univariate polynomial in the elimination
Gröbner is indeed $d$, though for non-radical ideals the degree can be larger
than $d$. For a simple example in the non-radical case consider
$(x^{2})\subset k[x]$.  $f\in\mathbb{F}_{q}[x]$ with $d=\deg\left(f\right)$
most efficiently we perform a greatest common divisor method that has recently
been described in [8, §3.1].

  1. (1)

Compute $g=x^{q}-x\mod f$.

The computation of $x^{q}\mod f$ requires
$\mathcal{O}\Big{(}d\cdot\log\left(q\right)\cdot\log\left(d\right)\cdot\log\big{(}\log\left(d\right)\big{)}\Big{)}$
field operations with a double-and-add algorithm.

  2. (2)

Compute $h=\gcd\left(f,g\right)$.

By construction $h$ has the same roots as $f$ in $\mathbb{F}_{q}$ since
$h=\gcd\left(f,x^{q}-x\right)$, but its degree is likely to be much lower.

This step requires
$\mathcal{O}\left(d\cdot\log\left(d\right)^{2}\cdot\log\big{(}\log\left(d\right)\big{)}\right)$
field operations.

  3. (3)

Factor $h$.

In general, the polynomial $f$ coming from a $0$-dimensional Gröbner basis has
only a few roots in $\mathbb{F}_{q}$.

Thus, this step is negligible in complexity.

Note that this method is only performative if $\deg\left(f\right)<q$ else one
has to exchange the roles of $f$ and the field equation. Overall solving the
polynomial system with probabilistic methods requires

$\mathcal{O}\left(n\cdot
d^{\omega}+d\cdot\log\left(q\right)\cdot\log\left(d\right)\cdot\log\big{(}\log\left(d\right)\big{)}+d\cdot\log\left(d\right)^{2}\cdot\log\big{(}\log\left(d\right)\big{)}\right)$
(39)

field operations, and with deterministic methods

$\mathcal{O}\left(\sqrt{n}\cdot
d^{2+\frac{n-1}{n}}+d\cdot\log\left(q\right)\cdot\log\left(d\right)\cdot\log\big{(}\log\left(d\right)\big{)}+d\cdot\log\left(d\right)^{2}\cdot\log\big{(}\log\left(d\right)\big{)}\right)$
(40)

field operations.

We must stress that we are unable to quantify the success probability of the
probabilistic term order conversion. The probabilistic analysis of [29, §5.1]
requires that the ideal is radical and that the homogenization of the DRL
Gröbner basis is a regular sequence. We neither have a proof nor a disproof of
these technical requirements for the Arion and ArionHash polynomial systems.
Therefore, we cannot quantify how capable the probabilistic approach is aside
from its complexity estimate.

Let us now discuss the complexity of Gröbner basis computations. Today, the
most efficient algorithms to compute Gröbner bases are Faugère’s linear
algebra-based algorithms F4 [25] and F5 [26]. The main idea of linear algebra-
based Gröbner basis algorithms can be traced back to Lazard [42]. Let
$\mathcal{F}=\\{f_{1},\dots,f_{m}\\}\subset P=k[x_{1},\dots,x_{n}]$ be a
finite set of homogeneous polynomials over a field $k$. The homogeneous
Macaulay matrix $M_{d}$ of degree $d$ has columns indexed by monomials in
$s\in P_{d}$ and rows indexed by polynomials $t\cdot f_{j}$, where $t\in P$ is
a monomial such that $\deg\left(t\cdot f_{j}\right)=d$. The entry of row
$t\cdot f_{j}$ at column $s$ is then the coefficient of the monomial $s$ in
$t\cdot f_{j}$. If $\mathcal{F}$ is an inhomogeneous system of polynomials,
then one replaces $M_{d}$ by $M_{\leq d}$ and the degree equality by an
inequality. If one fixes a term order $>$ on $P$, then by performing Gaussian
elimination on $M_{d}$ respectively $M_{\leq d}$ for a large enough value of
$d$ one produces a $>$-Gröbner basis of $\mathcal{F}$. The least such $d$ is
called the solving degree $\operatorname{sd}_{>}\left(\mathcal{F}\right)$ of
$\mathcal{F}$. (The notion of solving degree was first introduced in [22],
though we use the definition of [18].) The main improvement of F4/5 over
Lazard’s method is the choice of efficient selection criteria. Conceptually,
the Macaulay matrix will contain many redundant rows, if one is able to avoid
many of these rows with selection criteria, then the running time of an
algorithm will improve. Nevertheless, with the notion of the solving degree it
is possible to upper bound the maximal size of the computational universe of
F4/5. It is well-known that the number of monomials in $P$ of degree $d$ is
given by the binomial coefficient

$N(n,d)=\binom{n+d-1}{d}.$ (41)

We can now upper bound the size of the Macaulay matrix by $m\cdot d\cdot
N(n,d)\times d\cdot N(n,d)$. Overall, we can bound the complexity of Gaussian
elimination on the Macaulay matrix $M_{\leq d}$ by

$\mathcal{O}\Bigg{(}\binom{n+d-1}{d}^{\omega}\Bigg{)},$ (42)

where we absorb $m$ and $d$ in the implied constant since in general
$N(n,d)\gg m,d$ and $\omega\geq 2$ is a linear algebra constant.

In the cryptographic literature a generic approach to bound the solving degree
is the so-called Macaulay bound. Assume that
$\deg\left(f_{1}\right)\geq\ldots\geq\deg\left(f_{m}\right)$ and let
$l=\min\\{m,n+1\\}$, then the Macaulay bound of $\mathcal{F}$ is given by

$\operatorname{MB}_{\mathcal{F}}=\sum_{i=1}^{l}\deg\left(f_{1}\right)+\ldots+\deg\left(f_{l}\right)-l+1.$
(43)

Up to date there are two known cases when one indeed has that
$\operatorname{sd}_{DRL}\left(\mathcal{F}\right)\leq\operatorname{MB}_{\mathcal{F}}$:

  1. (1)

$\mathcal{F}$ is regular [6, 7], or

  2. (2)

$\mathcal{F}$ is in generic coordinates [18, Theorem 9, 10].

We stress that we were unable to prove that one of the two cases applies to
Arion or ArionHash. Therefore, we can only hypothesize that the Macaulay bound
upper bounds the solving degree.

From a designer’s perspective, during all our small scale experiments the
vector space dimension of the quotient space behaved more stable with respect
to the chosen primes, branch sizes and round numbers than the observed solving
degree. Thus, all our extrapolated security claims of Arion and ArionHash with
respect to Gröbner basis attacks are expressed in the complexity of solving
for the solutions of the polynomial system after a Gröbner basis has been
found.

Moreover, in all our experiments we observed that the quotient space dimension
grows exponentially in $r$ and the base only depends on $n,d_{1}$ and $d_{2}$.
We hypothesize that this behaviour is invariant under the chosen primes and
parameters. Therefore, we will do an “educated guess” from our small scale
experiments to obtain the base and extrapolate our findings for our security
analysis.

###  0.C.1 Arion

For the security of Arion against Gröbner basis attacks we consider the
following polynomial model:

  1. (i)

We do not consider a key schedule, i.e., in every round we add the same key
$\mathbf{k}=\left(k_{1},\dots,k_{n}\right)\in\mathbb{F}_{p}^{n}$.

  2. (ii)

We use a single plain/cipher pair $\mathbf{p},\mathbf{c}\in\mathbb{F}_{p}^{n}$
given by Arion to set up a fully determined polynomial system $\mathcal{F}$.

  3. (iii)

For $1\leq i\leq r-1$ we denote with
$\mathbf{x}^{(i)}=\left(x_{1}^{(i)},\dots,x_{n}^{(i)}\right)$ the intermediate
state variables, in addition we set
$\mathbf{x}^{(0)}=\operatorname{circ}\left(1,\dots,n\right)\cdot\left(\mathbf{p}+\mathbf{k}\right)$
and $\mathbf{x}^{(r)}=\mathbf{c}$. Further, for $1\leq i\leq r$ we denote with
$z^{(i)}$ an auxiliary variable. For our polynomial model we choose a slight
modification $\tilde{\mathcal{F}}=\\{\tilde{f}_{1},\dots,\tilde{f}_{n}\\}$ of
the Arion GTDS $\mathcal{F}=\\{f_{1},\dots,f_{n}\\}$, see Theorem 2.1, where
we set $\tilde{f}_{n}(x_{n})=x_{n}$. For $1\leq i\leq n-1$ the $\tilde{f}_{i}$
follow the same iterative definition as the original polynomials in the GTDS,
and we modify
$\tilde{\sigma}_{i+1,n}=x_{n}+z_{n}+\sum_{j=i+1}^{n-1}x_{j}+\tilde{f}_{j}$. We
consider the following polynomial model as the naive model
$\mathcal{F}_{\text{naive}}$ for Arion

$\begin{split}\operatorname{circ}\left(1,\dots,n\right)\tilde{\mathcal{F}}\left(\mathbf{\hat{x}}^{(i-1)}\right)+\mathbf{c}_{i}+\mathbf{k}-\mathbf{x}^{(r)}&=\mathbf{0},\\\
\left(x_{n}^{(i-1)}\right)^{e}-z^{(i)}&=0,\end{split}$

where
$\mathbf{\hat{x}}^{(i)}=\left(x_{1}^{(i)},\dots,x_{n-1}^{(i)},z^{(i)}\right)$.

  4. (iv)

Obviously the naive polynomial system $\mathcal{F}_{\text{naive}}$ contains
high degree equations given by the power permutation $x^{e}$. Though, if we
replace the auxiliary equations by

$x_{n}^{(i)}-\left(z^{(i)}\right)^{d_{2}}=0,$

then we obtain a polynomial system $\mathcal{F}_{\textsf{Arion}}$ whose
polynomials are of small degree. Further, we expect the arithmetic of
$\mathcal{F}_{\textsf{Arion}}$ to be independent of the chosen prime, i.e.,
for primes $p,q\in\mathbb{P}$ such that
$\gcd\left(d_{i},p-1\right)=1=\gcd\left(d_{i},q-1\right)$ we expect no notable
difference for the complexity of a Gröbner basis attack.

###### Lemma 0.C.1

Let $\mathbb{F}_{p}$ be a finite field, let $\mathcal{F}_{\text{naive}}$ and
$\mathcal{F}_{\textsf{Arion}}$ be the polynomial models from (iii) and (iv),
and let $F$ be the ideal of all field equations in the polynomial ring of
$\mathcal{F}_{\text{naive}}$ and $\mathcal{F}_{\textsf{Arion}}$. Then

$\left(\mathcal{F}_{\text{naive}}\right)+F=\left(\mathcal{F}_{\textsf{Arion}}\right)+F.$

###### Proof

By definition, we have that $\left(x_{n}^{(i)}\right)^{e}\equiv
z^{(i)}\mod\left(\mathcal{F}_{\text{naive}}\right)+F$, by raising this
congruence to the $d_{2}$th power yields

$\left(\left(x_{n}^{(i)}\right)^{e}\right)^{d_{2}}\equiv
x_{n}^{(i)}\equiv\left(z^{(i)}\right)^{d_{2}}\mod\left(\mathcal{F}_{\text{naive}}\right)+F$

which proves the claim. ∎

I.e., on the solutions that solely come from the finite field
$\mathbb{F}_{p}$, which are the solutions of cryptographic interest, the
varieties corresponding to $\mathcal{F}_{\text{naive}}$ and
$\mathcal{F}_{\textsf{Arion}}$ coincide, so

$\mathcal{V}\left(\mathcal{F}_{\text{naive}}\right)\cap\mathbb{F}_{p}^{n}=\mathcal{V}\left(\mathcal{F}_{\textsf{Arion}}\right)\cap\mathbb{F}_{p}^{n}.$
(44)

Thus, $\mathcal{F}_{\textsf{Arion}}$ is indeed a well-founded model for Arion.

To compute the Macaulay bound of $\mathcal{F}_{\textsf{Arion}}$ we first apply
$\operatorname{circ}(1,\dots,n)^{-1}$ in every round to cancel the mixing of
the components, then we use Theorem 2.2 with $e=1$ to compute the degree in
the $i$th component. Further, we have to account for the auxiliary equation,
overall we yield the Macaulay bound

$\begin{split}\operatorname{MB}_{n,d_{1},d_{2}}(r)&=r\cdot\left(d_{2}+1+\sum_{i=1}^{n-1}\left(2^{n-i}\cdot(d_{1}+1)-d_{1}\right)\right)+1-r\cdot\left(n+1\right)\\\
&=r\cdot\big{(}d_{2}+2\cdot(d_{1}+1)\cdot\left(2^{n-1}-1\right)-(n-1)\cdot
d_{1}-n\big{)}+1\end{split}$ (45)

We stress that we were unable to prove or disprove that
$\mathcal{F}_{\textsf{Arion}}$ is regular or in generic coordinates, thus we
can only hypothesize the Macaulay bound as measure for the complexity of
linear algebra-based Gröbner basis algorithms.

We implemented $\mathcal{F}_{\textsf{Arion}}$ in the `OSCAR` computer algebra
system [47] and computed the Gröbner basis with its F4 implementation.
Unfortunately, the log function of F4 only prints the current working degree
of the algorithm not its current solving degree. As remedy, we estimate the
empirical solving degree as follows: We sum up all positive differences of the
working degrees between consecutive steps and add this quantity to the largest
input polynomial degree. After computing the Gröbner basis we also computed
the $\mathbb{F}_{p}$-vector space dimension of the quotient ring. We conducted
our experiments with the primes

$\underbrace{\begin{aligned} p_{1}&=1013,\\\
p_{2}&=10007,\end{aligned}}_{\gcd\left(3,p_{i}-1\right)=1}\qquad\text{and}\qquad\underbrace{\begin{aligned}
p_{3}&=1033,\\\ p_{4}&=15013.\end{aligned}}_{\gcd\left(5,p_{i}-1\right)=1}$
(46)

All computations were performed on an AMD EPYC-Rome (48) CPU with 94 GB RAM.

In Figure 1 we record our empirical results for $n=2$ and in Figure 2 we
record our empirical results for $n=3$. From experiments, we hypothesize that
for $r>1$ the solving degree is indeed bounded by the Macaulay bound and that
the quotient space dimension grows exponential in $r$.

$1$$2$$3$$0$$20$$40$$r$$\operatorname{sd}_{DRL}\left(\mathcal{F}_{\textsf{Arion}}\right)$$d_{1}=3$$d_{1}=5$$\operatorname{MB}_{2,3,7}(r)$$\operatorname{MB}_{2,5,7}(r)$$1$$2$$3$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$r$$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{Arion}}\right)$$d_{1}=3$$d_{1}=5$$35^{r}$$49^{r}$
Figure 1: Experimental solving degree and vector space dimension of the
quotient ring for Arion with $n=2$ and $d_{2}=7$.

$1$$2$$0$$40$$80$$r$$\operatorname{sd}_{DRL}\left(\mathcal{F}_{\textsf{Arion}}\right)$$d_{1}=3$$d_{1}=5$$\operatorname{MB}_{3,3,7}(r)$$\operatorname{MB}_{3,5,7}(r)$$1$$2$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$r$$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{Arion}}\right)$$d_{1}=3$$d_{1}=5$$175^{r}$
Figure 2: Experimental solving degree and vector space dimension of the
quotient ring for Arion with $n=3$ and $d_{2}=7$.

To better understand the growth of the base of the quotient space dimension we
computed the quotient space dimension for $n\leq 4$ and $r=1$, see Table 16.

Table 16: Empirical growth of the vector space dimension of the quotient space of Arion with $r=1$. $n$ |  $d_{1}$ |  $d_{2}$ |  $\dim_{\mathbb{F}_{p},\text{emp}}$
---|---|---|---
$2$ |  $3$ |  $7$ |  $35$
$2$ |  $3$ |  $257$ |  $1285$
$3$ |  $3$ |  $7$ |  $175$
$4$ |  $3$ |  $7$ |  $875$
$2$ |  $5$ |  $7$ |  $49$
$2$ |  $5$ |  $257$ |  $1799$
$3$ |  $5$ |  $7$ |  $343$

From our experiments we conjecture that the quotient space dimension grows or
is bounded via

$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{Arion}}\right)(n,r,d_{1},d_{2})=\left(d_{2}\cdot\left(d_{1}+2\right)^{n-1}\right)^{r}.$
(47)

We use two approaches to estimate the cost of Gröbner basis computations for
$\mathcal{F}_{\textsf{Arion}}$. First, note that if we exclude one polynomial
from $\mathcal{F}_{\textsf{Arion}}$, then we do not have a zero-dimensional
polynomial system anymore. Therefore, the highest non-trivial lower bound for
the solving degree of $\mathcal{F}_{\textsf{Arion}}$ has to be the highest
degree in the Arion polynomial system, i.e.,

$\max\left\\{d_{2},2^{n-1}\cdot(d_{1}+1)-d_{1}\right\\}\leq\operatorname{sd}_{DRL}\left(\mathcal{F}_{\textsf{Arion}}\right).$
(48)

We combine this lower bound with Equation 42 to derive the “minimal possible“
Gröbner basis complexity estimate. Second, under the assumption that the
Macaulay bound always upper bounds the solving degree of Arion we can combine
Equations 42 and 43 to derive the “maximal possible” Gröbner basis complexity
estimate. For ease of computation we approximated the binomial coefficient
with

$\binom{n}{k}\approx\sqrt{\frac{n}{\pi\cdot k\cdot(n-k)}}\cdot 2^{n\cdot
H_{2}(k/n)},$ (49)

where
$H_{2}(p)=-p\cdot\log_{2}\left(p\right)-\left(1-p\right)\cdot\log_{2}\left(1-p\right)$
denotes the binary entropy (cf. [20, Lemma 17.5.1]). To estimate the cost of
system solving we plug Equation 47 into Equations 39 and 40. For all estimates
we assume that our adversary has an optimal Gaussian elimination algorithm
with $\omega=2$.

We base the security of Arion against Gröbner basis attacks solely on the
complexity of solving the polynomial system. I.e., even if an adversary can
compute a Gröbner basis in $\mathcal{O}(1)$ it must be computationally
infeasible to find a solution of the polynomial system. Thus, we estimate the
security level $\kappa$ of Arion against a Gröbner basis attack via

$\kappa\leq\log_{2}\big{(}\mathcal{O}\left(\text{System
solving}\right)\big{)}.$ (50)

Table 17: Empirical cost estimation of Gröbner basis attacks on Arion for
primes $p\geq 2^{60}$ and $d_{2}\geq 121$. The column GB min contains the
complexity of Gröbner basis computations estimated with the highest polynomial
degree in the Arion polynomial system. The column GB MB contains the
complexity Gröbner basis computations estimated via the Macaulay bound. We
assume that the adversary has an optimal Gaussian elimination algorithm with
$\omega=2$.

$n$ |  $r$ |  GB min (bits) |  GB MB (bits) |  Deterministic Solving (bits) |  Probabilistic Solving (bits)
---|---|---|---|---|---
$d_{1}=3$
$3$ |  $4$ |  $123$ |  $129$ |  $137$ |  $96$
$3$ |  $6$ |  $162$ |  $170$ |  $207$ |  $143$
$4$ |  $4$ |  $143$ |  $160$ |  $165$ |  $115$
$4$ |  $5$ |  $166$ |  $186$ |  $207$ |  $143$
$5$ |  $3$ |  $134$ |  $164$ |  $145$ |  $101$
$5$ |  $4$ |  $162$ |  $201$ |  $194$ |  $134$
$6$ |  $3$ |  $150$ |  $208$ |  $166$ |  $115$
$6$ |  $4$ |  $181$ |  $257$ |  $222$ |  $153$
$8$ |  $2$ |  $204$ |  $244$ |  $138$ |  $96$
$8$ |  $3$ |  $279$ |  $338$ |  $208$ |  $143$
$d_{1}=5$
$3$ |  $4$ |  $123$ |  $131$ |  $149$ |  $104$
$3$ |  $5$ |  $143$ |  $153$ |  $187$ |  $129$
$4$ |  $3$ |  $118$ |  $135$ |  $136$ |  $95$
$4$ |  $5$ |  $166$ |  $195$ |  $229$ |  $158$
$5$ |  $3$ |  $134$ |  $174$ |  $162$ |  $113$
$5$ |  $4$ |  $162$ |  $215$ |  $217$ |  $149$
$6$ |  $3$ |  $172$ |  $225$ |  $187$ |  $130$
$8$ |  $2$ |  $225$ |  $263$ |  $158$ |  $110$
$8$ |  $3$ |  $309$ |  $366$ |  $238$ |  $164$

###  0.C.2 ArionHash

In a preimage attack on ArionHash we are given a given hash value
$\alpha\in\mathbb{F}_{p}$ and we have to find
$\mathbf{x}\in\mathbb{F}_{p}^{r^{\prime}}$ such that
$\textsf{ArionHash}(\mathbf{x})=\alpha$. In a second-preimage attack we assume
that we are given a message that consists of two input blocks, i.e.
$\mathbf{y}=\left(\mathbf{y}_{1},\mathbf{y}_{2}\right)\in\left(\mathbb{F}_{p}^{r^{\prime}}\right)^{2}$.
Now we again have to find $\mathbf{x}\in\mathbb{F}_{p}^{r^{\prime}}$ such that
$\textsf{ArionHash}(\mathbf{y})=\textsf{ArionHash}(\mathbf{x})$. Consequently,
both preimage attacks on ArionHash reduce to the same equation

$\text{{Arion}-}\pi\begin{pmatrix}\mathbf{x}_{\text{in}}\\\
\texttt{IV}\end{pmatrix}=\begin{pmatrix}\alpha\\\
\mathbf{x}_{\text{out}}\end{pmatrix},$ (51)

where $\alpha\in\mathbb{F}_{p}$ is the output of ArionHash,
$\texttt{IV}\in\mathbb{F}_{p}^{c}$ is the initial value, and
$\mathbf{x}_{\text{in}}=\left(x_{\text{in},1},\dots,x_{\text{in},r^{\prime}}\right)$
and
$\mathbf{x}_{\text{out}}=\left(x_{\text{out},2},\dots,x_{\text{out},n}\right)$
are indeterminates. Analog to Arion we construct an iterated polynomial system
where each round is modeled with a polynomial vector. Note that Equation 51 is
not fully determined if $n\geq 3$ and $r^{\prime}>1$, in such a case we have
$n-1+r^{\prime}>n$ many variables for $\mathbf{x}_{\text{in}}$ and
$\mathbf{x}_{\text{out}}$ and $(r-1)\cdot n$ many intermediate state
variables, but we only have $r\cdot n$ many equations. In order to obtain a
fully determined system the adversary either has to guess some values for
$\mathbf{x}_{\text{in}}$ or $\mathbf{x}_{\text{out}}$, but each guess has
success probability $1/p$, so we can neglect this approach, or he has to add
additional equations. If an adversary is unable to exploit additional
algebraic structures of Arion\- (which are unknown to us), then he has just
one generic choice: he has to add field equations until the system is fully
determined. This approach introduces polynomials of very high degree, thus we
do not expect this attack to be feasible below our $128$ bit Gröbner basis
security claim. Therefore, in the analysis of this section we always choose
$c=n-1$ to obtain a fully determined system. Note that the Macaulay bound for
ArionHash is identical to the one for Arion, see Equation 45.

We implemented ArionHash in the `OSCAR` [47] computer algebra system and
computed the Gröbner basis of $\mathcal{F}_{\textsf{ArionHash}}$ with F4. As
initial value we chose $\texttt{IV}=\mathbf{0}^{c}$. Further, we computed the
$\mathbb{F}_{p}$-vector space dimension of the quotient space for ArionHash.
We used the same primes as for Arion, see Equation 46. In Figure 3 we record
our empirical results for $n=2$ and in Figure 4 we record our empirical
results for $n=3$. From experiments, we hypothesize that the solving degree is
indeed bounded by the Macaulay bound and that the quotient space dimension
grows exponential in $r$.

$1$$2$$3$$0$$20$$40$$r$$\operatorname{sd}_{DRL}\left(\mathcal{F}_{\textsf{ArionHash}}\right)$$d_{1}=3$$d_{1}=5$$\operatorname{MB}_{2,3,7}(r)$$\operatorname{MB}_{2,5,7}(r)$$1$$2$$3$$10^{2}$$10^{4}$$r$$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash}}\right)$$d_{1}=3$$d_{1}=5$$35^{r}$$49^{r}$
Figure 3: Experimental solving degree and vector space dimension of the
quotient ring for ArionHash with $n=2$ and $d_{2}=7$.
$1$$2$$0$$40$$80$$r$$\operatorname{sd}_{DRL}\left(\mathcal{F}_{\textsf{ArionHash}}\right)$$d_{1}=3$$d_{1}=5$$\operatorname{MB}_{3,3}(r)$$\operatorname{MB}_{3,5}(r)$$1$$2$$10^{2}$$10^{3}$$10^{4}$$r$$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash}}\right)$$d_{1}=3$$d_{1}=5$$91^{r}$$133^{r}$
Figure 4: Experimental solving degree and vector space dimension of the
quotient ring for ArionHash with $n=3$ and $d_{2}=7$.

To better understand the growth of the base of the quotient space dimension we
computed the quotient space dimension for $n\leq 5$ and $r=1$, see Table 18.

Table 18: Empirical growth of the vector space dimension of the quotient space of ArionHash. $n$ |  $d_{1}$ |  $d_{2}$ |  $\dim_{\mathbb{F}_{p},\text{emp}}$
---|---|---|---
$2$ |  $3$ |  $7$ |  $35$
$2$ |  $3$ |  $257$ |  $1285$
$3$ |  $3$ |  $7$ |  $91$
$3$ |  $3$ |  $257$ |  $3341$
$4$ |  $3$ |  $7$ |  $203$
$5$ |  $3$ |  $7$ |  $427$
$2$ |  $5$ |  $7$ |  $49$
$2$ |  $5$ |  $257$ |  $1799$
$3$ |  $5$ |  $7$ |  $133$
$3$ |  $5$ |  $257$ |  $4833$
$4$ |  $5$ |  $7$ |  $301$
$5$ |  $5$ |  $7$ |  $637$

From our experiments we conjecture that the quotient space dimension grows or
is bounded via

$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash}}\right)(n,r,d_{1},d_{2})=\Big{(}2^{n-1}\cdot
d_{2}\cdot\left(d_{1}+1\right)-d_{1}\cdot d_{2}\Big{)}^{r}.$ (52)

As for Arion, we apply this equation in Equations 40 and 39 to estimate the
cost of solving the ArionHash polynomial system.

Since the polynomial degrees of ArionHash coincide with the ones for Arion
also the Gröbner basis complexity estimates of ArionHash and Arion coincide.

Table 19: Empirical cost estimation of preimage Gröbner basis attacks on
ArionHash for primes $p\geq 2^{60}$ and $d_{2}\geq 121$. The column GB min
contains the complexity of Gröbner basis computations estimated with the
highest polynomial degree in the Arion polynomial system. The column GB MB
contains the complexity Gröbner basis computations estimated via the Macaulay
bound. We assume that the adversary has an optimal Gaussian elimination
algorithm with $\omega=2$.

$n$ |  $r$ |  GB min (bits) |  GB MB (bits) |  Deterministic Solving (bits) |  Probabilistic Solving (bits)
---|---|---|---|---|---
$d_{1}=3$
$3$ |  $5$ |  $143$ |  $150$ |  $158$ |  $110$
$3$ |  $6$ |  $162$ |  $170$ |  $190$ |  $132$
$4$ |  $4$ |  $143$ |  $160$ |  $141$ |  $98$
$4$ |  $6$ |  $187$ |  $210$ |  $212$ |  $146$
$5$ |  $4$ |  $162$ |  $201$ |  $154$ |  $107$
$5$ |  $5$ |  $187$ |  $235$ |  $193$ |  $133$
$6$ |  $4$ |  $181$ |  $257$ |  $167$ |  $115$
$6$ |  $5$ |  $208$ |  $301$ |  $208$ |  $143$
$8$ |  $3$ |  $279$ |  $338$ |  $143$ |  $100$
$8$ |  $4$ |  $345$ |  $423$ |  $191$ |  $132$
$d_{1}=5$
$3$ |  $4$ |  $123$ |  $131$ |  $133$ |  $93$
$3$ |  $6$ |  $162$ |  $173$ |  $200$ |  $138$
$4$ |  $4$ |  $143$ |  $143$ |  $167$ |  $103$
$4$ |  $5$ |  $179$ |  $166$ |  $195$ |  $128$
$5$ |  $3$ |  $162$ |  $215$ |  $161$ |  $111$
$5$ |  $5$ |  $187$ |  $251$ |  $201$ |  $139$
$6$ |  $3$ |  $172$ |  $225$ |  $130$ |  $91$
$6$ |  $5$ |  $244$ |  $328$ |  $217$ |  $149$
$8$ |  $3$ |  $309$ |  $366$ |  $148$ |  $103$
$8$ |  $4$ |  $385$ |  $461$ |  $198$ |  $137$

An adversary can also set up a collision attack via the equation

$\textsf{ArionHash}(\mathbf{x})=\textsf{ArionHash}(\mathbf{y}),$ (53)

where $\mathbf{x},\mathbf{y}\in\mathbb{F}_{p}^{\ast}$ are variables. We can
construct the corresponding collision polynomial system by first preparing two
preimage polynomial systems $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, then we
connect the last round of both systems via

$\displaystyle\begin{pmatrix}0&0&\ldots&0\\\ n&1&\ldots&n-1\\\ &&\ddots&\\\
2&3&\ldots&1\end{pmatrix}\tilde{\mathcal{F}}\left(\mathbf{\hat{x}}^{(r-1)}\right)+\mathbf{c}_{r}$
$\displaystyle=\begin{pmatrix}0\\\ \mathbf{x}_{out}\end{pmatrix},$ (54)
$\displaystyle x_{n}^{(r-1)}-\left(z^{(r)}\right)^{d_{2}}$ $\displaystyle=0,$
(55) $\displaystyle\begin{pmatrix}0&0&\ldots&0\\\ n&1&\ldots&n-1\\\
&&\ddots&\\\
2&3&\ldots&1\end{pmatrix}\tilde{\mathcal{F}}\left(\mathbf{\hat{y}}^{(r-1)}\right)+\mathbf{c}_{r}$
$\displaystyle=\begin{pmatrix}0\\\ \mathbf{y}_{out}\end{pmatrix},$ (56)
$\displaystyle y_{n}^{(r-1)}-\left(z^{(r)}\right)^{d_{2}}$ $\displaystyle=0,$
(57) $\displaystyle\begin{pmatrix}1&2&\ldots&n\\\ 0&0&\ldots&0\\\ &&\ddots&\\\
0&0&\ldots&0\end{pmatrix}\left(\tilde{\mathcal{F}}\left(\mathbf{\hat{x}}^{(r-1)}\right)-\tilde{\mathcal{F}}\left(\mathbf{\hat{y}}^{(r-1)}\right)\right)$
$\displaystyle=\mathbf{0}.$ (58)

Note that the collision polynomial system consists of $2\cdot
r\cdot\left(n+1\right)-1$ many equations in $2\cdot r\cdot\left(n+1\right)$
many variables, hence it is not fully determined. Therefore, one has to guess
at least one variable in the collision polynomial system. In all our
experiments we guessed one value of $\mathbf{y}_{out}$ and then computed the
DRL Gröbner basis of the system. We observed that the position of our guess in
$\mathbf{y}_{out}$ did never affect the dimension of the quotient space
dimension. In Table 20 we record the observed quotient space dimension in our
experiments.

Table 20: Empirical growth of the vector space dimension of the quotient space of the collision polynomial system of ArionHash. $n$ |  $r$ |  $d_{1}$ |  $d_{2}$ |  $\dim_{\mathbb{F}_{p},\text{emp}}$
---|---|---|---|---
$2$ |  $1$ |  $3$ |  $3$ |  $225$
$2$ |  $2$ |  $3$ |  $3$ |  $50625$
$2$ |  $1$ |  $5$ |  $5$ |  $1225$
$2$ |  $1$ |  $3$ |  $7$ |  $1225$
$3$ |  $1$ |  $3$ |  $7$ |  $8281$
$2$ |  $1$ |  $5$ |  $7$ |  $2401$
$3$ |  $1$ |  $3$ |  $3$ |  $1521$
$3$ |  $1$ |  $5$ |  $5$ |  $9025$
$3$ |  $1$ |  $3$ |  $7$ |  $8281$
$3$ |  $1$ |  $5$ |  $7$ |  $17689$
$4$ |  $1$ |  $3$ |  $3$ |  $7569$
$4$ |  $1$ |  $3$ |  $7$ |  $41209$

From our experiments we conjecture that the quotient space dimension grows or
is bounded via

$\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash},coll}\right)\left(n,r,d_{1},d_{2}\right)=\left(\dim_{\mathbb{F}_{p}}\left(\mathcal{F}_{\textsf{ArionHash}}\right)\left(n,r,d_{1},d_{2}\right)\right)^{2}$
(59)

Hence, the complexity estimate for the collision attack corresponds to the one
for the preimage attack with doubled number of rounds. In particular, Table 19
implies at least $128$ bit security against a collision Gröbner basis attack.

##  Appendix 0.D Performance Evaluation

###  0.D.1 libsnark Implementation

We implemented ArionHash, Griffin and Poseidon using the `C++` library
libsnark [50] that is used in the privacy-protecting digital currency Zcash
[35]. The comparative result of our experiment is given in Table 21. All
experiments were run on a system with an Intel Core i7-11800H CPU and 32 GB
RAM on a Clear Linux instance, using the g++-12 compiler with -O3
-march=native flags. Our result shows that ArionHash significantly outperforms
Poseidon showing 2x efficiency improvement, and the -ArionHash is considerably
faster than Griffin for practical parameter choices e.g. $n=3$ or $4$ in
Merkle tree hashing mode.

Table 21: Performance of various hash functions for proving the membership of
a Merkle tree accumulator over $\text{BN}254$ with $d_{2}=257$. Proving times
are in ms. For all hash functions verification requires less than
$20\text{\,}\mathrm{ms}$.

| Time (ms)
---|---
Height | ArionHash |  -ArionHash | Griffin | Poseidon
$d=5$ |  $n=3$ |  $n=4$ |  $n=8$ |  $n=3$ |  $n=4$ |  $n=8$ |  $n=3$ |  $n=4$ |  $n=8$ |  $n=3$ |  $n=4$ |  $n=8$
$4$ |  $101$ |  $103$ |  $142$ |  $73$ |  $87$ |  $143$ |  $88$ |  $99$ |  $133$ |  $186$ |  $212$ |  $274$
$8$ |  $211$ |  $216$ |  $294$ |  $145$ |  $177$ |  $294$ |  $181$ |  $209$ |  $270$ |  $386$ |  $417$ |  $566$
$16$ |  $392$ |  $401$ |  $554$ |  $278$ |  $334$ |  $553$ |  $338$ |  $387$ |  $505$ |  $745$ |  $805$ |  $1095$
$32$ |  $730$ |  $751$ |  $1046$ |  $509$ |  $646$ |  $1047$ |  $622$ |  $727$ |  $980$ |  $1422$ |  $1550$ |  $2111$

###  0.D.2 Dusk Network Plonk

We implemented ArionHash in `Rust` using the Dusk Network Plonk [23] library
which uses 3-wire constraints, and compared its performance to the Dusk
Network Poseidon [24] reference implementation. We note that for ArionHash we
only implemented a generic affine layer, i.e., ArionHash needs $n\cdot(n-1)$
constraints for matrix multiplication and $n$ constraints for constant
addition. The comparative result of our experiment is given in Table 22. All
experiments were run on a system with a Intel Core i7-10700 and 64 GB RAM. Our
result shows that ArionHash outperforms Poseidon showing 2x efficiency
improvement in Merkle tree hashing mode.

Table 22: Performance of various hash functions for proving the membership of
a Merkle tree accumulator over $\text{BLS}12$ for $d_{1}=5$ and $n=5$. For
each hash function and each Merkle tree height $1000$ samples were collected.
Average times plus-minus the standard deviation are given in the table. All
timings are in ms. For all hash functions verification requires less than
$10\text{\,}\mathrm{ms}$.

Time (ms)
---
| ArionHash | Poseidon
Native sponge | $0.121\pm 0.001$ | $0.101\pm 0.001$
Proof generation | $167\pm 1$ | $313\pm 4$
Merkle Tree
Height |  $4$ |  $8$ |  $16$ |  $32$ |  $4$ |  $8$ |  $16$ |  $32$
Proof generation |  $323\pm 4$ |  $533\pm 5$ |  $1011\pm 13$ |  $2034\pm 16$ |  $524\pm 6$ |  $1008\pm 14$ |  $1975\pm 27$ |  $4015\pm 57$