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

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 , but also over large fields of prime characteristic . 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: Anemoi Flystel Jive Arithmetization-oriented hash function CCZ-equivalence Plonk R1CS Merkle tree Zero-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: 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},
      url = {https://eprint.iacr.org/2022/840}
}