Alex Lombardi (MIT): Cryptographic Hashing From Strong One-Way Functions
Friday, April 13, 2018 - 10:30am to 12:00pm
Location:
Hewlett, G882
Speaker:
Alex Lombardi, MIT
Seminar group:
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.
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.