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 - Funding Information:
We thank Zvika Brakerski, Yael Kalai, Omer Paneth, and Vinod Vaikuntanathan for helpful discussions and comments. We also thank the anonymous FOCS reviewers for their useful feedback. This work was done in part while the authors were visiting the Weizmann Institute of Science in January 2018, supported by the Binational Science Foundation (Grants No. 2016726, 2014276) and European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482) and Project PROMETHEUS (Grant 780701). JH was supported in part by NSF Grant CNS-1413920. AL was supported in part by NSF Grants CNS-1350619 and CNS-1414119, and by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236.
Funding Information:
This work was done in part while the authors were visiting the Weizmann Institute of Science in January 2018, supported by the Binational Science Foundation (Grants No. 2016726, 2014276) and European Union Horizon 2020 Research and Innovation Program via ERC Project REACT(Grant 756482) and Project PROMETHEUS(Grant 780701).
Funding Information:
JH was supported in part by NSF Grant CNS-1413920. AL was supported in part by NSF Grants CNS-1350619 and CNS-1414119, and by the Defense AdvancedResearch Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236.
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 -