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

##### Abstract

Advanced cryptographic protocols such as Zero-knowledge (ZK) proofs of knowledge, widely used in cryptocurrency applications such as Zcash, Monero, Filecoin, 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 28%-48% 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).

Note: Revised submission with better implementations provided by our new co-authors.

Available format(s)
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
History
2022-10-17: revised
See all versions
Short URL
https://ia.cr/2022/840

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.