New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi Permutations and Jive Compression Mode

Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, Danny Willems

2022 · Full Version · eprint 2022/840

Paper (eprint) →

Disclaimer

This content was automatically converted from the original PDF and may have undergone post-processing. None of these steps have been reviewed or approved by the authors. Errors in formulas, definitions, proofs, or text may have been introduced during conversion. The authoritative version is the original paper on ePrint. Always cite and verify against the original publication.

Converted with: marker · 2026-02-13

Abstract

Advanced cryptographic protocols such as Zero-knowledge (ZK) proofs of knowledge, widely used in cryptocurrency applications such as Zcash, Monero, Filecoin, Tezos, Topos, demand new cryptographic hash functions that are efficient not only over the binary field \mathbb{F}_2, but also over large fields of prime characteristic \mathbb{F}_p. This need has been acknowledged by the wider community and new so-called Arithmetization-Oriented (AO) hash functions have been proposed, e.g. MiMC-Hash, Rescue–Prime, Poseidon, Reinforced Concrete and Griffin to name a few.

In this paper we propose Anemoi: a new family of ZK-friendly permutations, that can be used to construct efficient hash functions and compression functions. The main features of these algorithms are that 1) they are designed to be efficient within multiple proof systems (e.g. Groth16, Plonk, etc.), 2) they contain dedicated functions optimised for specific applications (namely Merkle tree hashing and general purpose hashing), 3) they have highly competitive performance e.g. about a factor of 2 improvement over Poseidon and Rescue–Prime in terms of R1CS constraints, a 21%–35% Plonk constraint reduction over a highly optimized Poseidon implementation, as well as competitive native performance, running between two and three times faster than Rescue–Prime, depending on the field size.

On the theoretical side, Anemoi pushes further the frontier in understanding the design principles that are truly entailed by arithmetization-orientation. In particular, we identify and exploit a previously unknown relationship between CCZ-equivalence and arithmetization-orientation. In addition, we propose two new standalone components that can be easily reused in new designs. One is a new S-box called Flystel, based on the well-studied butterfly structure, and the second is Jive – a new mode of operation, inspired by the “Latin dance” symmetric algorithms (Salsa, ChaCha and derivatives).

Keywords: Anemoi · Flystel · Jive · Arithmetization-oriented · Hash functions · CCZ-equivalence · Plonk · R1CS · AIR · Merkle tree · Zero-knowledge · Arithmetic circuits

1. Introduction

In recent years we have seen a rapid surge of interest in the practical application of zero-knowledge (ZK) proofs of knowledge. Such protocols allow a prover P to convince a verifier V that a certain statement x is true without revealing any additional information. ZK proof systems have been introduced with the seminal work of Micali, Goldwasser and Rackoff back in 1989 [GMR89]. The increased interest today is largely driven by digital currencies such as Bitcoin, Ethereum, Tezos, Topos, etc.

The computation performed by P and verified by V is often expressed as an arithmetic circuit composed of gates connected by wires over a field \mathbb{F}_q. Cryptographic hash functions are fundamental to practical ZK applications, often used for Merkle tree membership testing. Modern hash functions (SHA2, SHA3, BLAKE) are designed over \mathbb{F}_2, while ZK protocols operate over \mathbb{F}_q for large q, necessitating new Arithmetization-Oriented (AO) designs.

Evaluation vs. Verification. The most crucial efficiency requirement is verification: checking y = f(x) given both x and y.

b-to-1 compression. AO hash functions in Merkle trees need compression with factor b (often b = 2).

Primitive Factories. AO hash functions are defined for many field sizes and security levels. Algorithms like Poseidon are primitive factories.

Outline. Section 2: theoretical background. Section 3: the Jive mode. Section 4: the Flystel S-box via CCZ-equivalence. Section 5: Anemoi specification. Section 6: cryptanalysis. Section 7: benchmarks. Section 8: conclusion.

2. Theoretical Background

Let q be the size of \mathbb{F}_q (q = p prime or q = 2^n). Let m \geq 1 be the number of field elements.

Differential Properties. The DDT of F is \delta_F[a,b] = \#\{x \in \mathbb{F}_q^m \mid F(x+a) - F(x) = b\}. The maximum for a \neq 0 is the differential uniformity [Nyb94].

Linear Properties. For q = 2^n, the Walsh transform is

\mathcal{W}_{\langle b,F\rangle}(a) = \sum_{x \in \mathbb{F}_{2^n}^m} (-1)^{\langle a,x\rangle + \langle b,F(x)\rangle}.

For q = p, the Fourier transform is

\mathcal{W}_f(a) = \sum_{x \in \mathbb{F}_p^m} \exp\!\left(\frac{2\pi i(\langle a,x\rangle - f(x))}{p}\right).
Definition 1 (CCZ-Equivalence)

Let F and G be functions of \mathbb{F}_q^m. They are CCZ-equivalent if there exists an affine permutation \mathcal{L} : (\mathbb{F}_q^m)^2 \to (\mathbb{F}_q^m)^2 such that \Gamma_F = \mathcal{L}(\Gamma_G).

CCZ-equivalence preserves the differential spectrum and squared Walsh coefficients, but does not preserve the degree of the function.

3. Modes of Operation

Hash functions serve two purposes: emulating a random oracle, and as a compression function in Merkle trees.

3.1 Random Oracle: the Sponge Structure

The sponge construction [BDPVA07] uses a permutation P on \mathbb{F}_q^{r+c} with rate r and capacity c. It provides c\lfloor\log_2 q\rfloor/2 bits of security via padding, absorption, and squeezing phases.

3.2 Merkle Compression Function: the Jive Mode

Definition 2 (Jive)

Consider a permutation P on (\mathbb{F}_q^m)^b. The Jive mode defines:

\mathsf{Jive}_b(P) : (x_0, \ldots, x_{b-1}) \mapsto \sum_{i=0}^{b-1} \bigl(x_i + P_i(x_0, \ldots, x_{b-1})\bigr)

This is a permutation-based variant of Davies-Meyer, inspired by ChaCha and Salsa [Ber08]. With b = 2, \mathsf{Jive}_2 only needs a permutation of (\mathbb{F}_q^m)^2 instead of (\mathbb{F}_q^m)^3 for a sponge.

4. The Flystel Structure

4.1 On CCZ-Equivalence and Arithmetization-Orientation

For AO, verifying y = F(x) must use few multiplications. Rescue–Prime [AAB+20] observed that checking y = F(x) is equivalent to x = F^{-1}(y). The authors generalize: a subfunction is AO if it is CCZ-equivalent to an efficiently verifiable function.

4.2 High Level View of the Flystel Structure

Let Q_\gamma, Q_\delta : \mathbb{F}_q \to \mathbb{F}_q be quadratic and E : \mathbb{F}_q \to \mathbb{F}_q a permutation. The open Flystel \mathcal{H} on \mathbb{F}_q^2 is a 3-round Feistel:

1.\; x \leftarrow x - Q_\gamma(y),\quad 2.\; y \leftarrow y - E^{-1}(x),\quad 3.\; x \leftarrow x + Q_\delta(y),\quad 4.\; u \leftarrow x,\; v \leftarrow y.

The closed Flystel \mathcal{V} has R_\gamma(y,v) = E(y-v) + Q_\gamma(y) and R_\delta(y,v) = E(y-v) + Q_\delta(v).

Proposition 1

The closed and open Flystel are CCZ-equivalent.

Corollary 1

The open and closed Flystel have identical differential and linear properties.

Corollary 2

Verifying (u,v) = \mathcal{H}(x,y) is equivalent to verifying (x,u) = \mathcal{V}(y,v).

4.3 Characteristic 2

Proposition 2 ([LTYW18])

Let q = 2^n (n odd), E = x \mapsto x^\alpha with \alpha = 2^i+1, \gcd(i,n)=1, and Q_\gamma = Q_\delta = x \mapsto \beta x^\alpha (\beta \neq 0). The \text{Flystel}_2 has differential uniformity 4, linearity 2^{n+1}, and degree n.

In practice: Q_\gamma(x) = gx^3 + g^{-1} and Q_\delta(x) = gx^3.

4.4 Odd Characteristic

When q = p: Q_\gamma : x \mapsto gx^2 + g^{-1}, E : x \mapsto x^\alpha, Q_\delta : x \mapsto gx^2.

Proposition 3

\text{Flystel}_p has differential uniformity \alpha - 1.

The linearity is conjectured at most p \log p. The degree is lower bounded by \alpha^{-1} \bmod (p-1).

4.5 Implementation Aspects

Direct computation uses the open Flystel. Verification can use the closed Flystel, costing one multiplication each for Q_\gamma and Q_\delta, plus the cost of x \mapsto x^\alpha via addition chains [BC90].

5. Description of Anemoi

Anemoi permutations operate on \mathbb{F}_q^{2\ell} for q prime or power of two, and positive \ell.

5.1 Round Function

The state is a 2 \times \ell rectangle with rows X = (x_0, \ldots, x_{\ell-1}) and Y = (y_0, \ldots, y_{\ell-1}). Let g be the smallest generator of \mathbb{F}_q^*. The round function is a classical SPN with:

Constant Additions \mathcal{A}. Constants derived from \pi:

c_j^i = g(\pi_0^i)^2 + (\pi_0^i + \pi_1^j)^\alpha, \quad d_j^i = g(\pi_1^j)^2 + (\pi_0^i + \pi_1^j)^\alpha + g^{-1}

Diffusion Layer \mathcal{M}. Operates on X and Y separately. For \ell \in \{2,3,4\}, low-addition MDS matrices from [DL18]. For larger \ell, circulant MDS matrices. \mathcal{M}_y = \mathcal{M}_x \circ \rho (word rotation).

Pseudo-Hadamard transform \mathcal{P}. Y \leftarrow Y + X, then X \leftarrow X + Y.

S-box Layer. Column-wise open Flystel:

\mathcal{S}(X,Y) = (\mathcal{H}(x_0,y_0), \ldots, \mathcal{H}(x_{\ell-1}, y_{\ell-1}))

5.2 Higher Level Algorithms

Anemoi iterates n_r rounds then applies \mathcal{M}:

\text{Anemoi}_{q,\alpha,\ell} = \mathcal{M} \circ R_{n_r-1} \circ \cdots \circ R_0

The number of rounds satisfies:

n_r \geq \max\!\left\{8,\; \min(5, 1+\ell) + 2 + \min\left\{r \in \mathbb{N} \mid \mathcal{C}_{\text{alg}(r)} \geq 2^s\right\}\right\}

Table 1: Number of Rounds (s = 128).

\alpha35711
\ell=121212019
\ell=214141313
\ell=312121211
\ell=412121111
\ell=610101010
\ell=8101099

AnemoiSponge: Sponge-based with Anemoi on \mathbb{F}_q^{r+c} (r+c even). AnemoiJive: \mathsf{Jive}_b with Anemoi on bm elements (bm even).

5.3 Specific Instances

Instances for BLS12-381 (\alpha=5, g=7) and BN-254 (\alpha=5, g=2), both at 127-bit security with \ell=1 and 19 rounds.

6. Security Analysis

6.1 “Classical” Attacks

Statistical attacks (differential and linear cryptanalysis) exploit S-box patterns propagated through linear layers. The Flystel has low differential uniformity and MDS diffusion ensures many active S-boxes. Integral attacks and invariant subspaces are prevented by the non-aligned round structure.

6.2 Algebraic Attacks

Definition 3 (CICO)

Let P : \mathbb{F}_q^2 \to \mathbb{F}_q^2 be a permutation. Find (\text{in}, \text{out}) such that P(0, \text{in}) = (0, \text{out}).

6.2.1 Intermediate variables. Modeling 1 introduces 2n_r equations. The standard zero-dimensional strategy: compute a DRL Gröbner basis, then FGLM to LEX.

Estimate 1 (Even characteristic)

Cost estimated by FGLM: \mathcal{O}(\ell n_r \cdot 9^{\omega \ell n_r}).

6.2.2 Odd characteristic.

Conjecture 1

d_{\text{exp}} \geq 2n_r + \kappa_\alpha, where \kappa_3 = 1, \kappa_5 = 2, \kappa_7 = 4, \kappa_9 = 7, \kappa_{\alpha \geq 11} = 9.

Estimate 2 (Odd characteristic)

Cost estimated by Gröbner basis: \mathcal{O}\!\left(\binom{d_{\text{exp}} + 2n_r}{2n_r}^\omega\right).

Two extra rounds are added as a conservative measure.

7. Benchmarks

7.1 R1CS Systems

One Anemoi S-Box costs \mathcal{C}_\alpha + 2 constraints. Total for sponge mode: (\mathcal{C}_\alpha + 2) \cdot \frac{t}{2} \cdot n_r. Anemoi is about 2x more efficient than Poseidon and Rescue–Prime.

Table 2: R1CS, Plonk, AIR costs (s=128, \alpha=3).

tRescue′PoseidonGriffinAnemoi
R1CS2208198–76
422423211296
8256296176160
Plonk2312380–189
4560824260308
811521920574624
AIR2156300–126
4168348168168
8192480264288

7.2 Plonk

With a custom x^5 gate, AnemoiJive achieves 86 constraints (3 wires) or 64 constraints (4 wires). This is a 21%–35% reduction over optimized Poseidon [ASTW22]. With an additional quadratic custom gate, only 56 constraints total.

Table 3: Plonk with custom gate (s=128, \alpha=5).

t3 wires4 wires
Poseidon3 / 2110 / 8898 / 82
Reinforced Concrete3 / 2378 / 236267 / 174
Griffin3125111
AnemoiJive28664

7.3 AIR

Total AIR cost is w \cdot T \cdot d_{\max}. For Anemoi: w=t, T=n_r, d_{\max}=\alpha. Performance is close to Griffin and Rescue–Prime.

7.4 Native Performance

Table 4: Native 2-to-1 compression (p = 2^{64} - 2^{32} + 1, times in \mu s).

RP-12RP-8Poseidon-12Poseidon-8Griffin-12Griffin-8Anemoi-8
15.679.135.872.692.872.594.21

Table 5: Native permutation over BLS12-381 (times in \mu s).

Rescue–PrimePoseidonGriffinAnemoi
2069.274.18128.29

8. Conclusion

Anemoi is a family of permutations efficient across various arithmetization methods, yielding gains from 10% to more than 50% over existing designs. The Flystel structure exploits CCZ-equivalence and arithmetization-orientation. The Jive mode provides efficient b-to-1 compression. AnemoiJive requires only 56 Plonk constraints (3 wires, 2 custom gates), compared to optimized Poseidon at 98 constraints (4 wires).

Acknowledgements

The authors thank the CRYPTO 2023 reviewers, Markulf Kohlweiss, Antoine Rondelet, Duncan Tebbs, Tomer Ashur, Miguel Ambrona, and Raphaël Toledo. Léo Perrin is supported by the ERC (grant 101041545 “ReSCALE”).

Appendix A. Details of our Security Analysis

A.1 Differential and Linear Attacks

Differential uniformity is 4 (\text{Flystel}_2) or \alpha - 1 (\text{Flystel}_p). Best differential probability per S-box: (\alpha-1)/q^2. With q > 2^{63}, 3 active S-boxes suffice for 128-bit security. Linearity is conjectured at most p \log p.

A.2 Integral Attacks

The open Flystel is a 3-round Feistel with a permutation in the center round, so word-level patterns cannot propagate past two full rounds. Subgroup-based attacks are prevented by the internal additions and constants.

A.3 Invariant Subspaces

The invariant set has probability 1/q per column. The non-linear pattern is broken by the constant addition and linear layer.

Appendix B. Details on Algebraic Attacks

B.1 Algebraic Attacks in Characteristic 2

Lemma 1

For \ell = 1, the leading monomials in the reduced Gröbner basis of \{f_i, g_i\} are \{y_{i+1}^5, x_i y_{i+1}^3, x_i^3, x_i y_{i+1}\}, obtained in degree 5.

By Buchberger’s Second Criterion, the full basis terminates in degree 5. FGLM complexity: \mathcal{O}(\ell n_r \cdot 3^{2\ell n_r}).

B.2 Algebraic Attacks in Odd Characteristic

Modeling 2 introduces one unknown per round with degrees increasing only linearly.

Conjecture 2

\deg(I_{\text{CICO}}) = (\alpha + 2)^{n_r}.

Table 6: Gröbner Basis computation (odd characteristic, \ell = 1).

\alphan_rd_{\text{solv}}(\mathcal{F})Time (s)d_{\text{solv}}(\mathcal{P})Time (s)
3370.0170.01
5110.55110.33
81714450.51610575.6
5380.04110.05
4102.60150.88
512226.31919.13
73100.24120.19
41255.41716.87
51423042.2223903.3

Appendix C. Reference Implementation

A full reference implementation is available at github.com/anemoi-hash/anemoi-hash. It includes linear layers, round number computation, and both Jive and sponge modes.

References

  1. [AAB+20] A. Aly, T. Ashur, E. Ben-Sasson, S. Dhooghe, A. Szepieniec. “Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols”. IACR Trans. Symm. Cryptol., 2020(3).
  2. [add22] Polygon Miden. Repository, 2022.
  3. [AGR+16] M. Albrecht, L. Grassi, C. Rechberger, A. Roy, T. Tiessen. “MiMC”. ASIACRYPT 2016.
  4. [ASTW22] M. Ambrona, A.-L. Schmitt, R. Toledo, D. Willems. “New Optimization Techniques for Plonk’s Arithmetization”. ePrint 2022/462.
  5. [BBC+20] C. Beierle et al. “Lightweight AEAD and Hashing Using the Sparkle Permutation Family”. IACR Trans. Symm. Cryptol., 2020(S1).
  6. [BBHR18] E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev. “Scalable, Transparent, and Post-Quantum Secure Computational Integrity”. ePrint 2018/046.
  7. [BC90] J. Bos, M. Coster. “Addition Chain Heuristics”. CRYPTO 1989.
  8. [BCD+20] T. Beyne et al. “Out of Oddity”. CRYPTO 2020.
  9. [BCG+14] E. Ben-Sasson et al. “Zerocash”. IEEE S&P 2014.
  10. [BCP06] L. Budaghyan, C. Carlet, A. Pott. IEEE Trans. Inf. Theory, 52(3), 2006.
  11. [BDPA13] G. Bertoni et al. “Keccak”. EUROCRYPT 2013.
  12. [BDPVA07] G. Bertoni et al. “Sponge Functions”. ECRYPT 2007.
  13. [Ber08] D. Bernstein. “The Salsa20 Family of Stream Ciphers”. 2008.
  14. [BS01] A. Biryukov, A. Shamir. “Structural Cryptanalysis of SASAS”. EUROCRYPT 2001.
  15. [BS10] A. Biryukov, A. Shamir. J. Cryptology, 23(4), 2010.
  16. [BSGL20] E. Ben-Sasson, L. Goldberg, D. Levit. ePrint 2020/948.
  17. [BSV07] T. Baignères, J. Stern, S. Vaudenay. SAC 2007.
  18. [CCZ98] C. Carlet, P. Charpin, V. Zinoviev. Designs, Codes and Cryptography, 15(2), 1998.
  19. [CDL+20] A. Canteaut et al. “Saturnin”. IACR Trans. Symm. Cryptol., 2020(S1).
  20. [CDP17] A. Canteaut, S. Duval, L. Perrin. IEEE Trans. Inf. Theory, 63(11), 2017.
  21. [CLO15] D. Cox, J. Little, D. O’Shea. Ideals, Varieties, and Algorithms. Springer.
  22. [CP19] A. Canteaut, L. Perrin. Finite Fields and Their Applications, 56, 2019.
  23. [DGGK21] C. Dobraunig et al. “Ciminion”. 2021.
  24. [DL18] S. Duval, G. Leurent. “MDS Matrices with Lightweight Circuits”. IACR Trans. Symm. Cryptol., 2018(2).
  25. [Dwo15] M. Dworkin. “SHA-3 Standard”. NIST, 2015.
  26. [Fau99] J.-C. Faugère. “F4”. 1999.
  27. [Fau02] J.-C. Faugère. “F5”. ISSAC 2002.
  28. [FGLM93] J.C. Faugère et al. J. Symbolic Computation, 16(4), 1993.
  29. [GHR+22] L. Grassi et al. “Griffin for Zero-Knowledge Applications”. ePrint 2022/403.
  30. [GKL+22] L. Grassi et al. “Reinforced Concrete”. CCS 2022.
  31. [GKR+21] L. Grassi et al. “Poseidon”. USENIX Security 2021.
  32. [GMR89] S. Goldwasser, S. Micali, C. Rackoff. SIAM J. Computing, 18(1), 1989.
  33. [GOSW23] L. Grassi et al. “From Farfalle to Megafono via Ciminion”. EUROCRYPT 2023.
  34. [Gro16] J. Groth. “On the Size of Pairing-Based Non-Interactive Arguments”. EUROCRYPT 2016.
  35. [GW20] A. Gabizon, Z. Williamson. “plookup”. ePrint 2020/315.
  36. [Hir16] S. Hirose. “Sequential Hashing with Minimum Padding”. NIST 2016.
  37. [Knu95] L. Knudsen. “Truncated and Higher Order Differentials”. FSE 1994.
  38. [Lou94] W.W.A.P. Loustaunau. An Introduction to Gröbner Bases. AMS, 1994.
  39. [LPP+22] J. Liu et al. “An Efficient Verifiable State for ZK-EVM”. ePrint 2022/1487.
  40. [LTYW18] Y. Li, S. Tian, Y. Yu, M. Wang. IACR Trans. Symm. Cryptol., 2018(1).
  41. [McL21] M. McLoughlin. “addchain”. 2021.
  42. [MRR+] I. Meckler et al. “Mina Book, Kimchi Specification”.
  43. [Nyb94] K. Nyberg. “Differentially Uniform Mappings for Cryptography”. EUROCRYPT 1993.
  44. [PUB16] L. Perrin, A. Udovenko, A. Biryukov. CRYPTO 2016.
  45. [SAD20] A. Szepieniec, T. Ashur, S. Dhooghe. “Rescue-Prime”. ePrint 2020/1143.
  46. [SLST23] A. Szepieniec et al. “The Tip5 Hash Function”. ePrint 2023/107.
  47. [Zer22] Polygon Zero. “Plonky2”. 2022.

History

  • 2026-02-17Add disclaimer: content not author-approved, eprint is authoritative6638546
  • 2026-02-16Add CONVERTED_DATE to existing 47 paper pages7191c14
  • 2026-02-16Add crawler metadata to all 47 paper pagesc6638f2
  • 2026-02-14Replace HTML sub/sup with KaTeX math environmentsa020da2
  • 2026-02-13Add 10 new paper pages and update papers index0debc7b