Abstract
Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1}n → {0, 1}m where each bit of output is a fixed predicate P of a constant number d of (random) input bits. We investigate the security of this construction in the regime m = Dn, where D(d) is a sufficiently large constant. We prove that for any predicate P that correlates with either one or two of its inputs, f can be inverted with high probability.
We also prove an amplification claim regarding Goldreich’s construction. Suppose we are given an assignment \({x' \in \{0, 1\}^n}\) that has correlation \({\varepsilon > 0}\) with the hidden assignment \({x \in \{0, 1\}^n}\) . Then, given access to x′, it is possible to invert f on x with high probability, provided \({D = D(d, \varepsilon)}\) is sufficiently large.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon Noga., Kahale Nabil (1997) A Spectral Technique for Coloring Random 3-Colorable Graphs. SIAM J. Comp 26(6): 1733–1748 ISSN 0097-5397
Benny Applebaum, Boaz Barak & Avi Wigderson (2010). Public-key cryptography from different assumptions. In STOC ’10: Proceedings of the 42nd ACM symposium on Theory of computing, 171–180. ACM, New York, NY, USA. ISBN 978-1-4503-0050-6.
Benny Applebaum, Yuval Ishai & Eyal Kushilevitz (2004). Cryptography in NC 0. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science, 166–175.
Benny Applebaum, Yuval Ishai & Eyal Kushilevitz (2006). On Pseudorandom Generators with Linear Stretch in NC 0. In Proceedings of the 10th International Workshop on Randomization and Computation (RANDOM 2006), 260–271.
Andrej Bogdanov & Youming Qiao (2009). On the Security of Goldreich’s One-Way Function. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), 392–405.
Moses Charikar & Anthony Wirth (2004). Maximizing Quadratic Programs: Extending Grothendieck’s Inequality. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science, 54–60.
James Cook, Omid Etesami, Rachel Miller & Luca Trevisan (2009). Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms. In Proceedings of the 6th Theory of Cryptography Conference (TCC), 521–538.
Abraham Flaxman (2003). A spectral technique for random satisfiable 3CNF formulas. In SODA ’03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 357–363. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. ISBN 0-89871-538-5.
Goemans Michel X., Williamson David P. (1995) Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115–1145
Oded Goldreich (2000a). Candidate one-way functions based on expander graphs. Technical report, Electronic Colloquium on Computational Complexity (ECCC).
Goldreich Oded (2000) Foundations of Cryptography: Basic Tools. Cambridge University Press, New York, NY, USA ISBN0-52-179172-3
Michael Krivelevich & Dan Vilenchik (2006). Solving random satisfiable 3CNF formulas in expected polynomial time. In SODA ’06: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, 454–463. ACM, New York, NY, USA. ISBN 0-89871-605-5.
Elchanan Mossel, Amir Shpilka & Luca Trevisan (2003). On \({\varepsilon}\) -Biased Generators in NC 0. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 136–145.
Schmidt Jeanette P., Shamir Eli (1985) Component structure in the evolution of random hypergraphs. Combinatorica 5(1): 81–94
G. W. Stewart & Ji-guang Sun (1990). Matrix Perturbation Theory. Academic Press, Inc. ISBN 0-12-670230-6.
Vilenchik Danny (2007) It’s all about the support: a new perspective on the satisfiability problem. Journal on Satisfiability, Boolean Modeling, and Computation 3: 125–139
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bogdanov, A., Qiao, Y. On the security of Goldreich’s one-way function. comput. complex. 21, 83–127 (2012). https://doi.org/10.1007/s00037-011-0034-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-011-0034-0