The complexity of inversion of explicit Goldreich's function by DPLL algorithms

DOI10.1007/978-3-642-20712-9_11MaRDI QIDQ3007623zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson, Dmitry Sokolov

Publication date 17 June 2011

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20712-9_11

zbMATH Keywords

DPLL algorithmexpanderlower boundsone-way function

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Recommendations

• The complexity of inverting explicit Goldreich's function by DPLL algorithms
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• On the one-way function candidate proposed by Goldreich

Cites work

• Candidate one-way functions based on expander graphs
• Expander graphs and their applications
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Randomness conductors and constant-degree lossless expanders
• Short proofs are narrow—resolution made simple

Cited in

(8)

• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• The complexity of inverting explicit Goldreich's function by DPLL algorithms
• Resolution over linear equations modulo two
• DPLL+ROBDD derivation applied to inversion of some cryptographic functions
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• On the Security of Goldreich’s One-Way Function
• On the security of Goldreich's one-way function

This page was built for publication: The complexity of inversion of explicit Goldreich's function by DPLL algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007623)