International Association
for Cryptologic Research

The rising popularity of computational integrity protocols has led to an increased focus on efficient domain-specific hash functions, which are one of the core components in these use cases. For example, they are used for polynomial commitments or membership proofs in the context of Merkle trees. Indeed, in modern proof systems the computation of hash functions is a large part of the entire proof's complexity. In the recent years, authors of these hash functions have focused on components which are verifiable with low-degree constraints. This led to constructions like Poseidon, Rescue, Griffin, Reinforced Concrete, and Tip5, all of which showed significant improvements compared to classical hash functions such as SHA-3 when used inside the proof systems. In this paper, we focus on lookup-based computations, a specific component which allows to verify that a particular witness is contained in a lookup table. We work over 31-bit and 64-bit finite fields $\mathbb F_p$, both of which are used in various modern proof systems today and allow for fast implementations. We propose a new 2-to-1 compression function and a SAFE hash function, instantiated by the Monolith permutation. The permutation is significantly more efficient than its competitors, both in terms of circuit friendliness and plain performance, which has become one of the main bottlenecks in various use cases. This includes Reinforced Concrete and Tip5, the first two hash functions using lookup computations internally. Moreover, in Monolith we instantiate the lookup tables as functions defined over $\mathbb F_2$ while ensuring that the outputs are still elements in $\mathbb F_p$. Contrary to Reinforced Concrete and Tip5, this approach allows efficient constant-time plain implementations which mitigates the risk of side-channel attacks potentially affecting competing lookup-based designs. Concretely, our constant time 2-to-1 compression function is faster than a constant time version of Poseidon2 by a factor of 7. Finally, it is also the first arithmetization-oriented function with a plain performance comparable to SHA3-256, essentially closing the performance gap between circuit-friendly hash functions and traditional ones.