On the security of Goldreich's one-way function

DOI10.1007/S00037-011-0034-0zbMATH Open1280.68092OpenAlexW2002676260MaRDI QIDQ430847FDOQ430847

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

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

zbMATH Keywords

one-way functionparallel cryptography

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

• Expander-Based Cryptography Meets Natural Proofs
• On the one-way function candidate proposed by Goldreich
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Computational wiretap coding from indistinguishability obfuscation
• Expander-based cryptography meets natural proofs
• Fast pseudorandom functions based on expander graphs
• A dichotomy for local small-bias generators
• Security-preserving hardness-amplification for any regular one-way function
• Indistinguishability obfuscation
• Cryptographic hardness of random local functions. Survey
• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Lossy cryptography from code-based assumptions
• The Complexity of Public-Key Cryptography
• From golden to unimodular cryptography
• Title not available (Why is that?)
• Minimizing locality of one-way functions via semi-private randomized encodings
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Algebraic attacks against random local functions and their countermeasures
• The GGM construction does NOT yield correlation intractable function ensembles
• On the Security of Goldreich’s One-Way Function

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)