We introduce a new notion of multi-collision resistance for keyless hash functions. This is a natural relaxation of collision resistance where it is hard to find multiple inputs with the same hash in the following sense. The number of colliding inputs that a polynomial-time non-uniform adversary can find is not much larger than its advice. We discuss potential candidates for this notion and study its applications.

Assuming the existence of such hash functions, we resolve the long-standing question of the round complexity of zero knowledge protocols --- we construct a 3-message zero knowledge argument against arbitrary polynomial-size non-uniform adversaries. We also improve the round complexity in several other central applications, including a 3-message succinct argument of knowledge for NP, a 4-message zero-knowledge proof, and a 5-message public-coin zero-knowledge argument. Our techniques can also be applied in the keyed setting, where we match the round complexity of known protocols while relaxing the underlying assumption from collision-resistance to keyed multi-collision resistance.

The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property. The transformation is based on a combination of classical domain extension techniques, together with new information-theoretic tools. In particular, we define and construct a new variant of list-recoverable codes, which may be of independent interest.

We study the notion of multi-collision resistance of hash functions --- a natural relaxation of collision-resistance that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. Specifically, in the keyless setting, we only require that the size of collisions an adversarial algorithm can find is not much larger than its description size, or non-uniform advice.

We show how to replace collision resistance with multi-collision resistance in several foundational applications. Relying on such keyless functions, we improve on the best known round complexity for these applications. This includes:
\begin{itemize}
\item
3-message zero-knowledge arguments for NP.

\item
3-message succinct arguments of knowledge for NP.

\item
4-message $\varepsilon$-zero-knowledge proofs for NP.
\item
5-message public-coin zero-knowledge arguments for NP.
\end{itemize}

These results are obtained in the standard model of non-uniform adversaries of arbitrary polynomial size. Our techniques can also be applied in the keyed setting, at the cost of adding another message. In this case, we relax the known complexity assumptions for the last three applications, while still matching the state of the art in terms of round complexity.

The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property.

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. In the unkeyed setting we only require that the size of collisions an adversarial algorithm can find is not much larger than its description size, or non-uniform advice.

We show how to replace collision resistance with multi-collision resistance in several foundational applications. Relying on such unkeyed functions, we improve on the best known round complexity for these applications. This includes:

* 3-message zero-knowledge arguments for NP.
* 3-message succinct arguments of knowledge for NP.
* 4-message $\epsilon$-zero-knowledge proofs for NP.
* 5-message public-coin zero-knowledge arguments for NP.

These results are obtained in the standard model of non-uniform adversaries of arbitrary polynomial size. Our techniques can also be applied in the keyed setting, at the cost of adding another message. In this case, we weaken the known complexity assumptions for the last three applications, while still matching the state of the art in terms of round complexity.

The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property.