Reinforced Concrete: Fast Hash Function for Zero Knowledge Proofs and Verifiable Computation

Abstract

We propose a new hash function Reinforced Concrete for the proof systems that support lookup tables, concretely Plookup based on KZG commitments or FRI. It has two solid advantages over predecessors: (a) Table lookups instead of (big) modular reductions are much faster both in ZK and plain computations thus making verifiable computation protocols based on recursive proofs (current trend) much more efficient; (b) the security is no longer solely based on (high) algebraic degree but rather on more traditional AES-like components inheriting decades of public scrutiny. Our design also employs a novel and fast field-to-tables conversion, which is of independent interest and can be used in other Plookup-friendly constructions. The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

Publication
IACR Cryptol. ePrint Arch.