Paper 2024/047
On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing
Abstract
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
Note: Updated publication status
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. CSF 2024
- Keywords
- 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 - History
- 2024-07-08: last of 4 revisions
- 2024-01-11: received
- See all versions
- Short URL
- https://ia.cr/2024/047
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/047, 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}, url = {https://eprint.iacr.org/2024/047} }