Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On the One-Way Function Candidate Proposed by Goldreich

On the One-Way Function Candidate Proposed by Goldreich 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

On the One-Way Function Candidate Proposed by Goldreich

Download PDF
35 pages

Loading next page...
 
/lp/association-for-computing-machinery/on-the-one-way-function-candidate-proposed-by-goldreich-mO7xdz0FO0

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2014 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/2633602
Publisher site
See Article on Publisher Site

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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jul 1, 2014

Keywords: DPLL elimination rules

References

  • Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
    Alekhnovich, ; M., ; Hirsch, ; A., E.; Itsykson, ; D.,
  • Pseudorandom generators with long stretch and low locality from random local one-way functions
    Applebaum, ; B.,
  • Public-key cryptography from different assumptions
    Applebaum, ; B., ; Barak, ; B., ; Wigderson, ; A.,
  • Cryptography in NC0
    Applebaum, ; B., ; Ishai, ; Y., ; Kushilevitz, ; E.,
  • On pseudorandom generators with linear stretch in NC0
    Applebaum, ; B., ; Ishai, ; Y., ; Kushilevitz, ; E.,
  • Short proofs are narrow -- resolution made simple
    Ben-Sasson, ; E., ; Wigderson, ; A.,
  • On the security of Goldreich’s one-way function
    Bogdanov, ; A., ; Qiao, ; Y.,
  • Goldreich’s one-way function candidate and myopic backtracking algorithms
    Cook, ; J., ; Etesami, ; O., ; Miller, ; R., ; Trevisan, ; L.,
  • Effective preprocessing in SAT through variable and clause elimination
    Eén, ; N., ; Biere, ; A.,
  • An extensible SAT-solver
    Eén, ; N., ; Sörensson, ; N.,
  • Candidate one-way functions based on expander graphs
    Goldreich, ; O.,
  • Lower bound on average-case complexity of inversion of Goldreich’s function by drunken backtracking algorithms
    Itsykson, ; D.,
  • Lower bounds for myopic DPLL algorithms with a cut heuristic
    Itsykson, ; D., ; Sokolov, ; D.,
  • The complexity of inversion of explicit Goldreich’s function by DPLL algorithms
    Itsykson, ; D., ; Sokolov, ; D.,
  • The complexity of inversion of explicit Goldreich’s function by DPLL algorithms
    Itsykson, ; D., ; Sokolov, ; D.,
  • Tree-like resolution is superpolynomially slower than dag-like resolution for the pigeonhole principle
    Iwama, ; K., ; Miyazaki, ; S.,
  • Goldreich’s one-way function candidate and drunken backtracking algorithms
    Miller, ; R.,
  • An experimental evaluation of Goldreich’s one-way function
    Panjwani, ; K., S.