Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

DOI10.1007/978-3-642-13182-0_19zbMath1285.68056OpenAlexW1605794802MaRDI QIDQ3569744

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)

Related Items (8)

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

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