On the security of Goldreich's one-way function

DOI10.1007/S00037-011-0034-0MaRDI QIDQ430847zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the Security of Goldreich’s One-Way Function
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• On the one-way function candidate proposed by Goldreich
• The complexity of inverting explicit Goldreich's function by DPLL algorithms
• The complexity of inversion of explicit Goldreich's function by DPLL algorithms

Cites work

• scientific article; zbMATH DE number 5287580 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 2079359 (Why is no real title available?)
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Candidate one-way functions based on expander graphs
• Component structure in the evolution of random hypergraphs
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On Pseudorandom Generators with Linear Stretch in NC0
• On the Security of Goldreich’s One-Way Function
• On ε‐biased generators in NC⁰
• Public-key cryptography from different assumptions
• Solving random satisfiable 3CNF formulas in expected polynomial time

Cited in

(21)

• Fast pseudorandom functions based on expander graphs
• Computational wiretap coding from indistinguishability obfuscation
• Expander-based cryptography meets natural proofs
• Algebraic attacks against random local functions and their countermeasures
• Lossy cryptography from code-based assumptions
• From golden to unimodular cryptography
• On the one-way function candidate proposed by Goldreich
• The GGM construction does NOT yield correlation intractable function ensembles
• Expander-Based Cryptography Meets Natural Proofs
• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• On the Security of Goldreich’s One-Way Function
• Security-preserving hardness-amplification for any regular one-way function
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Minimizing locality of one-way functions via semi-private randomized encodings
• scientific article; zbMATH DE number 2009956 (Why is no real title available?)
• Indistinguishability obfuscation
• 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
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)

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

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