research-article

On the One-Way Function Candidate Proposed by Goldreich

Authors:

Luca TrevisanAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 6, Issue 3

Article No.: 14, Pages 1 - 35

https://doi.org/10.1145/2633602

Published: 01 July 2014 Publication History

Abstract

Goldreich [2000] proposed a candidate one-way function based on a bipartite graph of small right-degree d, where the vertices on the left (resp. right) represent input (resp. output) bits of the function. Each output bit is computed by evaluating a fixed d-ary binary predicate on the input bits adjacent to that output bit. We study this function when the predicate is random or depends linearly on many of its input bits. We assume that the graph is a random balanced bipartite graph with right-degree d.

Inverting this function as a one-way function by definition means finding an element in the preimage of output of this function for a random input. We bound the expected size of this preimage.

Next, using the preceding bound, we prove that two restricted types of backtracking algorithms called myopic and drunk backtracking algorithms with high probability take exponential time to invert the function, even if we allow the algorithms to use DPLL elimination rules. (For drunk algorithms, a similar result was proved by Itsykson [2010].)

We also ran a SAT solver on the satisfiability problem equivalent to the problem of inverting the function, and experimentally observed an exponential increase in running time as a function of the input length.

References

[1]

Alekhnovich, M., Hirsch, E. A., and Itsykson, D. 2005. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason. 35, 51--72.

Digital Library

[2]

Applebaum, B. 2013. Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput. 42, 5, 2008--2037.

[3]

Applebaum, B., Barak, B., and Wigderson, A. 2010. Public-key cryptography from different assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, (STOC’10). L. J. Schulman Ed., ACM, 171--180.

Digital Library

[4]

Applebaum, B., Ishai, Y., and Kushilevitz, E. 2006a. Cryptography in NC0. SIAM J. Comput. 36, 4, 845--888.

Digital Library

[5]

Applebaum, B., Ishai, Y., and Kushilevitz, E. 2006b. On pseudorandom generators with linear stretch in NC0. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 10th International Workshop on Randomization and Computation (APPROX-RANDOM’06). Lecture Notes in Computer Science, vol. 4110, Spring, Berlin, 260--271.

Digital Library

[6]

Ben-Sasson, E. and Wigderson, A. 2001. Short proofs are narrow -- resolution made simple. J. ACM 48, 2, 149--169.

Digital Library

[7]

Bogdanov, A. and Qiao, Y. 2009. On the security of Goldreich’s one-way function. In Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 13th International Workshop on Randomization and Computation (APPROX-RANDOM’09). I. Dinur, K. Jansen, J. Naor, and J. D. P. Rolim Eds., Lecture Notes in Computer Science Series, vol. 5687, Springer, 392--405.

Digital Library

[8]

Cook, J., Etesami, O., Miller, R., and Trevisan, L. 2009. Goldreich’s one-way function candidate and myopic backtracking algorithms. In Proceedings of the 6th Theory of Cryptography Conference (TCC’09). O. Reingold Ed., Lecture Notes in Computer Science Series, vol. 5444, Springer, 521--538.

Digital Library

[9]

Eén, N. and Biere, A. 2005. Effective preprocessing in SAT through variable and clause elimination. In Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing (SAT’05). F. Bacchus and T. Walsh Eds., Lecture Notes in Computer Science Series, vol. 3569, Springer, 61--75.

Digital Library

[10]

Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT’03). E. Giunchiglia and A. Tacchella Eds., Lecture Notes in Computer Science Series, vol. 2919, Springer, 502--518.

[11]

Goldreich, O. 2000. Candidate one-way functions based on expander graphs. Electron. Colloq. Computat. Complex. 7, 90. http://eccc.hpi-web.de/eccc-reports/2000/TR00-090/index.html.

[12]

Itsykson, D. 2010. Lower bound on average-case complexity of inversion of Goldreich’s function by drunken backtracking algorithms. In Proceedings of the 5th International Computer Science Symposium in Russia (CSR’10). F. M. Ablayev and E. W. Mayr Eds., Lecture Notes in Computer Science Series, vol. 6072, Springer, 204--215.

Digital Library

[13]

Itsykson, D. and Sokolov, D. 2011. Lower bounds for myopic DPLL algorithms with a cut heuristic. In Proceedings of the 22nd International Symposium on Algorithms and (ISAAC’11). T. Asano, S.-I. Nakano, Y. Okamoto, and O. Watanabe Eds., Lecture Notes in Computer Science Series, vol. 7074, Springer, 464--473.

Digital Library

[14]

Itsykson, D. and Sokolov, D. 2012. The complexity of inversion of explicit Goldreich’s function by DPLL algorithms. Zapiski Nauchnykh Seminarov POMI 399, 88--108.

[15]

Itsykson, D. and Sokolov, D. 2013. The complexity of inversion of explicit Goldreich’s function by DPLL algorithms. J. Math. Sci. 188, 1, 47--58. http://link.springer.com/article/10.1007&percnt;2Fs10958-012-1105-8.

[16]

Iwama, K. and Miyazaki, S. 1999. Tree-like resolution is superpolynomially slower than dag-like resolution for the pigeonhole principle. In Proceedings of 19th International Symposium on Algorithms and Computation (ISAAC’99). Lecture Notes in Computer Science Series, vol. 1741, 133--142.

Digital Library

[17]

Miller, R. 2009. Goldreich’s one-way function candidate and drunken backtracking algorithms. Distinguished Majors Thesis. http://people.csail.mit.edu/rmiller/ram9a-dmp-thesis.pdf.

[18]

Panjwani, S. K. 2001. An experimental evaluation of Goldreich’s one-way function. Technical Report, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay.

Cited By

Gonczarowski YThomas CMohar BShinkar IO'Donnell R(2024)Structural Complexities of Matching MechanismsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649737(455-466)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649737
Bui DCouteau GMeyer PPasselègue ARiahinia M(2024)Fast Public-Key Silent OT and More from Constrained Naor-ReingoldAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_4(88-118)Online publication date: 29-Apr-2024
https://doi.org/10.1007/978-3-031-58751-1_4
Dupin AMéaux PRossi M(2023)On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generatorDesigns, Codes and Cryptography10.1007/s10623-023-01220-w91:9(3035-3079)Online publication date: 25-May-2023
https://doi.org/10.1007/s10623-023-01220-w
Show More Cited By

Index Terms

On the One-Way Function Candidate Proposed by Goldreich

Recommendations

Pseudorandomness against depth-2 circuits and analysis of goldreich's candidate one-way function
The complexity of inversion of explicit goldreich's function by DPLL algorithms
CSR'11: Proceedings of the 6th international conference on Computer science: theory and applications

The Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by the fixed predicate of arity d. Every Goldreich's function is defined by it's dependency graph G and predicate P. In 2000 O. ...
Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms
TCC '09: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography

Goldreich (ECCC 2000) proposed a candidate one-way function construction which is parameterized by the choice of a small predicate (over <em>d</em> = <em>O</em> (1) variables) and of a bipartite expanding graph of right-degree <em>d</em> . The function ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 6, Issue 3

Special issue on innovations in theoretical computer science 2012 - Part II

July 2014

107 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/2663945

Editor:
Eric Allender
Rutgers University, NJ, USA

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2014

Published in TOCT Volume 6, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

PGS award
European Research Council
NDSEG fellowship
Division of Computing and Communication Foundations
Natural Sciences and Engineering Research Council of Canada
National Science Foundation
IPM (Institute for Research in Fundamental Sciences, Tehran)
BSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
163
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gonczarowski YThomas CMohar BShinkar IO'Donnell R(2024)Structural Complexities of Matching MechanismsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649737(455-466)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649737
Bui DCouteau GMeyer PPasselègue ARiahinia M(2024)Fast Public-Key Silent OT and More from Constrained Naor-ReingoldAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_4(88-118)Online publication date: 29-Apr-2024
https://doi.org/10.1007/978-3-031-58751-1_4
Dupin AMéaux PRossi M(2023)On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generatorDesigns, Codes and Cryptography10.1007/s10623-023-01220-w91:9(3035-3079)Online publication date: 25-May-2023
https://doi.org/10.1007/s10623-023-01220-w
Oliveira ISanthanam RTell R(2022)Expander-Based Cryptography Meets Natural ProofsComputational Complexity10.1007/s00037-022-00220-x31:1Online publication date: 16-Mar-2022
https://dl.acm.org/doi/10.1007/s00037-022-00220-x
Applebaum BIshai YKushilevitz E(2018)Minimizing Locality of One-Way Functions via Semi-private Randomized EncodingsJournal of Cryptology10.1007/s00145-016-9244-631:1(1-22)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s00145-016-9244-6
Applebaum B(2017)Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2017.82(836-847)Online publication date: Oct-2017
https://doi.org/10.1109/FOCS.2017.82
Applebaum BLovett SWichs DMansour Y(2016)Algebraic attacks against random local functions and their countermeasuresProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897554(1087-1100)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2897518.2897554
Applebaum B(2016)Cryptographic Hardness of Random Local FunctionsComputational Complexity10.1007/s00037-015-0121-825:3(667-722)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s00037-015-0121-8
Applebaum BRaykov P(2016)Fast Pseudorandom Functions Based on Expander GraphsProceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 998510.1007/978-3-662-53641-4_2(27-56)Online publication date: 31-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-662-53641-4_2

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents