TY - GEN
T1 - Cryptographic hashing from strong one-way functions (Or: One-way product functions and their applications)
AU - Holmgren, Justin
AU - Lombardi, Alex
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/11/30
Y1 - 2018/11/30
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85059810536&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059810536&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2018.00085
DO - 10.1109/FOCS.2018.00085
M3 - Conference contribution
AN - SCOPUS:85059810536
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 850
EP - 858
BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
A2 - Thorup, Mikkel
PB - IEEE Computer Society
T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Y2 - 7 October 2018 through 9 October 2018
ER -