International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Clémence Bouvier , Inria, Sorbonne University
Pierre Briaud , Inria, Sorbonne University
Pyrros Chaidos , National & Kapodistrian University of Athens, IOG
Léo Perrin , Inria
Robin Salen , Toposware, Inc.
Vesselin Velichkov , Clearmatics, University of Edinburgh
Danny Willems , LIX, Nomadic Labs
Download:
DOI: 10.1007/978-3-031-38548-3_17 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
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 \F2, but also over large fields of prime characteristic \Fp. 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, Poseidon, ReinforcedConcrete 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 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, 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.
BibTeX
@inproceedings{crypto-2023-33096,
  title={New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi Permutations and Jive Compression Mode},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38548-3_17},
  author={Clémence Bouvier and Pierre Briaud and Pyrros Chaidos and Léo Perrin and Robin Salen and Vesselin Velichkov and Danny Willems},
  year=2023
}