Alex Lombardi (MIT): Cryptographic Hashing From Strong One-Way Functions

Friday, April 13, 2018 - 10:30am to 12:00pm
Hewlett, G882
Alex Lombardi, MIT
Abstract: Constructing collision-resistant hash families (CRHFs) from one-way functions is a long-standing open problem and source of frustration in theoretical cryptography. In fact, there are strong negative results: black-box separations from exponentially secure one-way functions (Simon, EUROCRYPT '98) and even indistinguishability obfuscation (Asharov and Segev, FOCS '15).

In this work, we formulate a mild strengthening of exponentially secure one-way functions, and we
construct CRHFs from such functions.  Specifically, our security notion requires that every
polynomial-time algorithm has exponentially small probability of inverting two independent
challenges.  More generally, we consider the problem of simultaneously inverting $k$ functions
(f_1, ..., f_k), which we say constitute a "one-way product function" (OWPF).  We show that
sufficiently hard OWPFs yield hash families that are multi-input correlation intractable
(Canetti, Goldreich, and Halevi, STOC '98) with respect to a restricted class of relations.

Additionally assuming indistinguishability obfuscation, we construct hash families that achieve a
broader notion of correlation intractability.  In particular, these families are
sufficient to instantiate the Fiat-Shamir heuristic in the plain model for a natural
class of interactive proofs.

An interesting consequence of our results is a new avenue for bypassing black-box
separations: proving (with necessarily non-black-box techniques) that parallel repetition amplifies the
hardness of a specific one-way function.
Joint work with Justin Holmgren.