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.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.FOCS 2018
Keywords
Hash familieshardness amplificationmulti-instance security
Contact author(s)
alexjl @ mit edu
History
2018-08-06: revised
See all versions
Short URL
https://ia.cr/2018/385

CC BY

BibTeX

@misc{cryptoeprint:2018/385,
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{https://eprint.iacr.org/2018/385}},
url = {https://eprint.iacr.org/2018/385}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.