Paper 2022/840

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

Clémence Bouvier, Sorbonne University, French Institute for Research in Computer Science and Automation
Pierre Briaud, Sorbonne University, French Institute for Research in Computer Science and Automation
Pyrros Chaidos, National and Kapodistrian University of Athens
Léo Perrin, French Institute for Research in Computer Science and Automation
Robin Salen, Toposware
Vesselin Velichkov, Clearmatics, University of Edinburgh
Danny Willems, Nomadic Labs, Computer Science Laboratory of the École Polytechnique
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). Our design is a conservative one: it uses a very classical Substitution-Permutation Network structure, and our detailed analysis of algebraic attacks highlights can be of independent interest.

Note: Revised submission before publication in CRYPTO 2023

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
AnemoiFlystelJiveArithmetization-oriented hash functionCCZ-equivalencePlonkR1CSMerkle treeZero-knowledge
Contact author(s)
clemence bouvier @ inria fr
pierre briaud @ inria fr
pyrros chaidos @ iohk io
leo perrin @ inria fr
salen @ toposware com
vvelichk @ exseed ed ac uk
danny @ badaas be
History
2023-05-31: last of 2 revisions
2022-06-24: received
See all versions
Short URL
https://ia.cr/2022/840
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/840,
      author = {Clémence Bouvier and Pierre Briaud and Pyrros Chaidos and Léo Perrin and Robin Salen and Vesselin Velichkov and Danny Willems},
      title = {New Design Techniques for Efficient Arithmetization-Oriented Hash Functions:Anemoi Permutations and Jive Compression Mode},
      howpublished = {Cryptology ePrint Archive, Paper 2022/840},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/840}},
      url = {https://eprint.iacr.org/2022/840}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.