**Cryptographic Hashing From Strong One-Way Functions**

*Justin Holmgren and Alex Lombardi*

**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 one-way functions that are $2^{-(1-o(1))n}$-secure against polynomial time adversaries (Simon, EUROCRYPT '98) and even from 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 at most $2^{-n - \omega(\log(n))}$ probability of inverting two independent challenges.

More generally, we consider the problem of simultaneously inverting $k$ functions $f_1,\ldots, 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 all sparse (bounded arity) output relations. Additionally assuming indistinguishability obfuscation, we construct hash families that achieve a broader notion of correlation intractability, extending the recent work of Kalai, Rothblum, and Rothblum (CRYPTO '17). 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 potential new avenue for bypassing black-box separations. In particular, proving (with necessarily non-black-box techniques) that parallel repetition amplifies the hardness of specific one-way functions -- for example, all one-way permutations -- suffices to directly bypass Simon's impossibility result.

**Category / Keywords: **foundations / Hash families, hardness amplification, multi-instance security

**Original Publication**** (with major differences): **FOCS 2018

**Date: **received 27 Apr 2018, last revised 5 Aug 2018

**Contact author: **alexjl at mit edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20180806:014730 (All versions of this report)

**Short URL: **ia.cr/2018/385

[ Cryptology ePrint archive ]