NDLI: On the One-Way Function Candidate Proposed by Goldreich

Please wait, while we are loading the content...

On the One-Way Function Candidate Proposed by Goldreich

Content Provider	ACM Digital Library
Author	Cook, James Miller, Rachel Trevisan, Luca Etesami, Omid
Copyright Year	2014
Abstract	Goldreich [2000] proposed a candidate one-way function based on a bipartite graph of small right-degree $\textit{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 $\textit{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 $\textit{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 $\textit{myopic}$ and $\textit{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.
Starting Page	1
Ending Page	35
Page Count	35
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2633602
Volume Number	6
Issue Number	3
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	DPLL elimination rules One-way function Average preimage size Proof complexity Random bipartite graph Restricted backtracking algorithm
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The complexity of inversion of explicit goldreich’s function by dpll algorithms (2010).

Exponential lower bounds for a dpll attack against a one-way function based on expander graphs (2008).

Goldreich ’ s One-Way Function Candidate and Drunken Backtracking Algorithms

Formula Caching in DPLL

Short lists for shortest descriptions in short time

The Resolution Complexity of Random Graph k-Colorability (2004)

Parameterized Complexity of DPLL Search Procedures

Space complexity of random formulae in resolution

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

On the One-Way Function Candidate Proposed by Goldreich

Similar Documents

The complexity of inversion of explicit goldreich’s function by dpll algorithms (2010).

Exponential lower bounds for a dpll attack against a one-way function based on expander graphs (2008).

Goldreich ’ s One-Way Function Candidate and Drunken Backtracking Algorithms

Formula Caching in DPLL

Short lists for shortest descriptions in short time

The Resolution Complexity of Random Graph k-Colorability (2004)

Parameterized Complexity of DPLL Search Procedures

Space complexity of random formulae in resolution

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

On the One-Way Function Candidate Proposed by Goldreich