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

(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.