Paper 2024/047

On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing

Elena Andreeva, TU Wien
Rishiraj Bhattacharyya, University of Birmingham
Arnab Roy, Universität Innsbruck
Stefano Trevisani, TU Wien

ZK-SNARKs, a fundamental component of privacy-oriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed. One of the most important computations that is run through SNARK systems is the verification of Merkle tree (MT) opening proofs, which relies on the evaluation of a fixed-input-length (FIL) cryptographic compression function over binary MTs. As classical, bit-oriented hash functions like SHA-2 are not compactly representable in SNARK frameworks, Arithmetization-Oriented (AO) cryptographic designs have emerged as an alternative, efficient solution. Today, the majority of AO compression functions are built from the Sponge permutation-based hashing mode. While this approach allows cost savings, compared to blockcipher-based modes, as it does not require key-scheduling, AO blockcipher schedulers are often cheap to compute. Furthermore, classical bit-oriented cryptography has long studied how to construct provably secure compression functions from blockciphers, following the Preneel-Govaerts-Vandewalle (PGV) framework. The potential efficiency gains together with the strong provable security foundations in the classic setting, motivate the study of AO blockcipher-based compression functions. In this work, we propose PGV-LC and PGV-ELC, two AO blockcipher-based FIL compression modes inspired by and extending the classical PGV approach, offering flexible input and output sizes and coming with provable security guarantees in the AO setting. We prove the collision and preimage resistance in the ideal cipher model, and give bounds for collision and opening resistance over MTs of arbitrary arity. We compare experimentally the AO PGV-ELC mode over the Hades blockcipher with its popular and widely adopted Sponge instantiation, Poseidon, and its improved variant Poseidon2. Our resulting constructions are up to \(3\times \) faster than Poseidon and \(2\times \) faster than Poseidon2 in native x86 execution, and up to \(50\% \) faster in the Groth16 SNARK framework. Finally, we study the benefits of using MTs of arity wider than two, proposing a new strategy to obtain a compact R1CS constraint system in such case. In fact, by combining an efficient parametrization of the Hades blockcipher over the PGV-ELC mode, together with an optimal choice of the MT arity, we measured an improvement of up to \(9\times \) in native MT construction time, and up to \(2.5\times \) in proof generation time, compared to Poseidon over binary MTs.

Note: Updated to match IEEE CSF 2024 publication.

Available format(s)
Secret-key cryptography
Publication info
Hash functionBlock cipherArithmetization-OrientedMerkle treeZero-KnowledgeSNARKPoseidon
Contact author(s)
elena andreeva @ tuwien ac at
rishiraj bhattacharyya @ gmail com
Arnab Roy @ uibk ac at
stefano trevisani @ tuwien ac at
2024-05-23: last of 3 revisions
2024-01-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elena Andreeva and Rishiraj Bhattacharyya and Arnab Roy and Stefano Trevisani},
      title = {On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2024/047},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.