International Association
for Cryptologic Research

Conventional hash functions are often inefficient in zero-knowledge proof settings, leading to design of several ZK-friendly hash functions. On the other hand, lookup arguments have recently been incorporated into zero-knowledge protocols, allowing for more efficient handling of ``ZK-unfriendly'' operations, and hence ZK-friendly hash functions based on lookup tables. In this paper, we propose a new ZK-friendly hash function, dubbed Polocolo, that employs an S-box constructed using power residues. Our approach reduces the numbers of gates required for table lookups, in particular, when combined with Plonk, allowing one to use such nonlinear layers over multiple rounds. We also propose a new MDS matrix for the linear layer of Polocolo. In this way, Polocolo requires fewer Plonk gates compared to the state-of-the-art ZK-friendly hash functions. For example, when t = 8, Polocolo requires 21% less Plonk gates compared to Anemoi, which is currently the most efficient ZK-friendly hash function, where t denotes the size of the underlying permutation in blocks of F_p. For t = 3, Polocolo requires 24% less Plonk gates than Reinforced Concrete, which is one of the recent lookup-based ZK-friendly hash functions.