Welcome to the resource topic for 2024/047
Title:
On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing
Authors: Elena Andreeva, Rishiraj Bhattacharyya, Arnab Roy, Stefano Trevisani
Abstract:ZK-SNARKs are advanced cryptographic protocols used in private verifiable computation: modern
SNARKs allow to encode the invariants of an arithmetic circuit over some large prime field
in an appropriate NP language, from which a zero-knowlege short non-interactive argument of
knowledge is built.
Due to the high cost of proof generation, ZK-SNARKs for large constraint systems are inpractical.
ZK-SNARKs are used in privacy-oriented blockchains such as Filecoin, ZCash and Monero, to
verify Merkle tree opening proofs, which in turn requires computing a fixed-input-length (FIL)
cryptographic compression function.
As classical, bit-oriented hash functions like SHA-2 require huge constraint systems,
Arithmetization-Oriented (AO) compression functions have emerged to fill the gap.
Usually, AO compression functions are obtained by applying the Sponge hashing mode
on a fixed-key permutation: while this avoids the cost of dynamic key scheduling, AO schedulers
are often cheap to compute, making the exploration of AO compression functions based directly
on blockciphers a topic of practical interest.
In this work, we first adapt notions related to classical hash functions and their security
notions to the AO syntax, and inspired by the classical PGV modes, we propose
AO PGV-LC and AO PGV-ELC, two blockcipher-based FIL compression modes with parametrizable
input and output sizes.
In the ideal cipher model, we prove the collision and preimage resistance of both our modes, and
give bounds for collision and opening resistance over Merkle trees of arbitrary arity.
We then experimentally compare the AO PGV-LC mode over the Hades-MiMC blockcipher
with its popular Sponge instantiation, Poseidon.
The resulting construction, called Poseidon-DM, is 2-5\times faster than Poseidon
in native computations, and 15-35\% faster in generating Merkle tree proofs over the
Groth16 SNARK framework, depending on the tree arity.
In particular, proof generation for an 8-ary tree over Poseidon-DM is 2.5\times
faster than for a binary tree with the same capacity over Poseidon.
Finally, in an effort to further exploit the benefits of wide trees, we propose a new
strategy to obtain a compact R1CS constraint system for Merkle trees with arbitrary arity.
ePrint: https://eprint.iacr.org/2024/047
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .