On the security of Goldreich's one-way function

DOI10.1007/s00037-011-0034-0zbMath1280.68092OpenAlexW2002676260MaRDI QIDQ430847

Andrej Bogdanov, Youming Qiao

Publication date: 26 June 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0034-0

zbMATH Keywords

one-way functionparallel cryptography

Mathematics Subject Classification ID

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

Related Items (13)

Expander-based cryptography meets natural proofs ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Cryptographic hardness of random local functions. Survey ⋮ Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms ⋮ Computational wiretap coding from indistinguishability obfuscation ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Indistinguishability obfuscation ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Minimizing locality of one-way functions via semi-private randomized encodings ⋮ Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ The Complexity of Public-Key Cryptography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Component structure in the evolution of random hypergraphs
• Public-key cryptography from different assumptions
• Candidate One-Way Functions Based on Expander Graphs
• Solving random satisfiable 3CNF formulas in expected polynomial time
• On Pseudorandom Generators with Linear Stretch in NC0
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• On the Security of Goldreich’s One-Way Function
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• On ε‐biased generators in NC⁰

This page was built for publication: On the security of Goldreich's one-way function