Cryptographic hashing from strong one-way functions (Or: One-way product functions and their applications)

Justin Holmgren, Alex Lombardi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

46 Scopus citations

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 indistin-guishability 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 · negl(n) 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 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 oneway permutations - suffices to directly bypass Simon's impossibility result.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages850-858
Number of pages9
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Externally publishedYes
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Country/TerritoryFrance
CityParis
Period10/7/1810/9/18

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Cryptographic hashing from strong one-way functions (Or: One-way product functions and their applications)'. Together they form a unique fingerprint.

Cite this