The Unreasonable Effectiveness of Almost Optimal Hardness

What properties of random oracles are achievable by concrete hash families, and under what assumptions? In this talk I will discuss new results that cast light on two seemingly unrelated specializations of this question. Specifically, I will focus on the tasks of (1) constructing collision-resistant hash families from generic assumptions, and (2) constructing hash families that suffice for publicly verifiable delegation (via the Fiat-Shamir transform).

I will first present a collision-resistant hash family from any one-way function that satisfies a strong notion of security similar to exponential hardness. This provides a potential route to bypassing Simon's black-box separation through (necessarily non-black-box) hardness amplification. Our security property, while strong, differs from previous sufficient conditions for collision-resistant hashing in that it does not obviously imply hardness in SZK.

I will then describe how similar techniques combined with structured assumptions (e.g., the extreme hardness of Search LWE) yield hash families that satisfy general notions of correlation intractability, namely that for any "simple" relation R it is difficult, given a hash function H, to find x such that (x, H(x)) is in R. These hash families imply new results on non-interactive zero knowledge and delegation of computation that until now were not known from any comparably "falsifiable" assumption.

Based on joint works with Ran Canetti, Yilei Chen, Alex Lombardi, Guy Rothblum, and Ron Rothblum.