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 On the One-Way Function Candidate Proposed by Goldreich JAMES COOK, University of California, Berkeley OMID ETESAMI, Institute for Research in Fundamental Sciences (IPM) RACHEL MILLER, MIT LUCA TREVISAN, University of California, Berkeley 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 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-3oar0eUkJl

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 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2633602
Publisher site
See Article on Publisher Site

Abstract

On the One-Way Function Candidate Proposed by Goldreich JAMES COOK, University of California, Berkeley OMID ETESAMI, Institute for Research in Fundamental Sciences (IPM) RACHEL MILLER, MIT LUCA TREVISAN, University of California, Berkeley 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

Journal

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

Published: Jul 1, 2014

There are no references for this article.