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

DOI10.1007/978-3-642-00457-5_31zbMath1213.94092OpenAlexW2125046124MaRDI QIDQ3611786

No author found.

Publication date: 3 March 2009

Published in: Theory of Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00457-5_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Related Items (16)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ A dichotomy for local small-bias generators ⋮ Locally computable UOWHF with linear shrinkage ⋮ Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Non-interactive zero-knowledge from non-interactive batch arguments ⋮ Indistinguishability obfuscation ⋮ Input locality and hardness amplification ⋮ The complexity of inverting explicit Goldreich's function by DPLL algorithms ⋮ On the security of Goldreich's one-way function ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms ⋮ Lossy cryptography from code-based assumptions ⋮ On linear-size pseudorandom generators and hardcore functions ⋮ Candidate One-Way Functions Based on Expander Graphs ⋮ The Complexity of Public-Key Cryptography

Uses Software

• Unnamed Item

This page was built for publication: Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms