Paper 2018/385

Cryptographic Hashing From Strong One-Way Functions

Justin Holmgren and Alex Lombardi


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.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.FOCS 2018
Hash familieshardness amplificationmulti-instance security
Contact author(s)
alexjl @ mit edu
2018-08-06: revised
2018-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Justin Holmgren and Alex Lombardi},
      title = {Cryptographic Hashing From Strong One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/385},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.