Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms

DOI10.1007/978-3-642-13182-0_19zbMATH Open1285.68056OpenAlexW1605794802MaRDI QIDQ3569744FDOQ3569744

Authors Dmitry Itsykson

Publication date 22 June 2010

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-13182-0_19

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

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

Cited in

(8)

• On the one-way function candidate proposed by Goldreich
• The complexity of inversion of explicit Goldreich's function by DPLL algorithms
• 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
• A dichotomy for local small-bias generators
• Cryptographic hardness of random local functions. Survey
• The Complexity of Public-Key Cryptography
• Locally computable UOWHF with linear shrinkage

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms

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