On the One-Way Function Candidate Proposed by Goldreich

DOI10.1145/2633602zbMath1347.94029OpenAlexW2077484581MaRDI QIDQ2828220

No author found.

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2633602

zbMATH Keywords

random bipartite graphone-way functionproof complexityaverage preimage sizeDPLL elimination rulesrestricted backtracking algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Expander-based cryptography meets natural proofs ⋮ 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 ⋮ On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator ⋮ Oblivious transfer with constant computational overhead ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Minimizing locality of one-way functions via semi-private randomized encodings ⋮ Expander-Based Cryptography Meets Natural Proofs

Uses Software

• MiniSat

Cites Work

• Unnamed Item
• Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5--8, 2011. Proceedings
• Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21--23, 2009. Proceedings
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Theory of cryptography. 6th theory of cryptography conference, TCC 2009, San Francisco, CA, USA, March 15--17, 2009. Proceedings
• The complexity of inverting explicit Goldreich's function by DPLL algorithms
• Public-key cryptography from different assumptions
• Candidate One-Way Functions Based on Expander Graphs
• Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms
• Short proofs are narrow—resolution made simple
• Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
• Theory and Applications of Satisfiability Testing
• Cryptography in $NC^0$

This page was built for publication: On the One-Way Function Candidate Proposed by Goldreich