Cryptographic hardness of random local functions. Survey
From MaRDI portal
Publication:332271
DOI10.1007/s00037-015-0121-8zbMath1360.94293MaRDI QIDQ332271
Publication date: 28 October 2016
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-015-0121-8
cryptography; pseudorandom generators; public-key encryption; local functions; hash functions; one-way functions; NC0; constant-depth circuits
94A60: Cryptography
68P25: Data encryption (aspects in computer science)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
On the Complexity of Random Satisfiability Problems with Planted Solutions, Algebraic Attacks against Random Local Functions and Their Countermeasures, Expander-Based Cryptography Meets Natural Proofs, Unnamed Item, Actively secure arithmetic computation and VOLE with constant computational overhead, Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error, Oblivious transfer with constant computational overhead, Minimizing locality of one-way functions via semi-private randomized encodings, Expander-based cryptography meets natural proofs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the security of Goldreich's one-way function
- Approximation resistant predicates from pairwise independence
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
- Selection of relevant features and examples in machine learning
- Computationally private randomizing polynomials and their applications
- A spectral technique for coloring random 3-colorable graphs (preliminary version)
- Pseudorandomness for network algorithms
- On the One-Way Function Candidate Proposed by Goldreich
- Public-key cryptography from different assumptions
- A Dichotomy for Local Small-Bias Generators
- On the Complexity of Random Satisfiability Problems with Planted Solutions
- Sum of Squares Lower Bounds from Pairwise Independence
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- Input Locality and Hardness Amplification
- Pseudorandom Bits for Polynomials
- Candidate One-Way Functions Based on Expander Graphs
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
- A spectral technique for random satisfiable 3CNF formulas
- Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms
- Relations between average case complexity and approximation complexity
- On the power of unique 2-prover 1-round games
- Polylogarithmic independence fools AC 0 circuits
- A Better Algorithm for Random k-SAT
- New directions in cryptography
- A method for obtaining digital signatures and public-key cryptosystems
- Cryptographic limitations on learning Boolean formulae and finite automata
- Foundations of Cryptography
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Short proofs are narrow—resolution made simple
- Foundations of Cryptography
- Locally Computable UOWHF with Linear Shrinkage
- Robust Pseudorandom Generators
- Bounded Independence Fools Halfspaces
- Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
- On ε‐biased generators in NC0
- Pseudorandomness for Read-Once Formulas
- Cryptography in $NC^0$
- On the solution-space geometry of random constraint satisfaction problems
- Every 2-CSP allows nontrivial approximation
