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

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)

Cited In (8)

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

Uses Software

• MiniSat

   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 👍 👎

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)