## 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |

Editors | Mikkel Thorup |

Publisher | IEEE Computer Society |

Pages | 850-858 |

Number of pages | 9 |

ISBN (Electronic) | 9781538642306 |

DOIs | |

State | Published - Nov 30 2018 |

Externally published | Yes |

Event | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: Oct 7 2018 → Oct 9 2018 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2018-October |

ISSN (Print) | 0272-5428 |

### Other

Other | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
---|---|

Country/Territory | France |

City | Paris |

Period | 10/7/18 → 10/9/18 |

## All Science Journal Classification (ASJC) codes

- General Computer Science