Cryptographic hardness of random local functions. Survey
From MaRDI portal
Publication:332271
DOI10.1007/s00037-015-0121-8zbMath1360.94293OpenAlexW2284855724MaRDI 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
cryptographypseudorandom generatorspublic-key encryptionlocal functionshash functionsone-way functionsNC0constant-depth circuits
Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
Expander-based cryptography meets natural proofs ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ 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 ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Unnamed Item ⋮ 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
This page was built for publication: Cryptographic hardness of random local functions. Survey
