Cryptographic hardness of random local functions. Survey
From MaRDI portal
(Redirected from Publication:332271)
Recommendations
Cites work
- scientific article; zbMATH DE number 1559544 (Why is no real title available?)
- scientific article; zbMATH DE number 1834654 (Why is no real title available?)
- A Better Algorithm for Random k-SAT
- A dichotomy for local small-bias generators
- A method for obtaining digital signatures and public-key cryptosystems
- A spectral technique for coloring random 3-colorable graphs (preliminary version)
- A spectral technique for random satisfiable 3CNF formulas
- Approximation resistant predicates from pairwise independence
- Bounded Independence Fools Halfspaces
- Candidate one-way functions based on expander graphs
- Computationally private randomizing polynomials and their applications
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
- Cryptographic limitations on learning Boolean formulae and finite automata
- Cryptography in $NC^0$
- Cryptography with constant computational overhead
- Every 2-CSP allows nontrivial approximation
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Foundations of Cryptography
- Foundations of Cryptography
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Input locality and hardness amplification
- Locally computable UOWHF with linear shrinkage
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
- New directions in cryptography
- On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
- On the complexity of random satisfiability problems with planted solutions (extended abstract)
- On the one-way function candidate proposed by Goldreich
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- On the power of unique 2-prover 1-round games
- On the security of Goldreich's one-way function
- On the solution-space geometry of random constraint satisfaction problems
- On ε‐biased generators in NC0
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Pseudorandom bits for polynomials
- Pseudorandom generators with long stretch and low locality from random local one-way functions
- Pseudorandomness for Read-Once Formulas
- Pseudorandomness for network algorithms
- Public-key cryptography from different assumptions
- Relations between average case complexity and approximation complexity
- Robust pseudorandom generators
- SDP gaps from pairwise independence
- Selection of relevant features and examples in machine learning
- Short proofs are narrow—resolution made simple
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Sum of squares lower bounds from pairwise independence (extended abstract)
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- Unconditional pseudorandom generators for low degree polynomials
Cited in
(15)- Cryptography with Constant Input Locality
- Expander-based cryptography meets natural proofs
- On the complexity of random satisfiability problems with planted solutions
- Algebraic attacks against random local functions and their countermeasures
- Compressing unit-vector correlations via sparse pseudorandom generators
- Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
- Learning polynomial transformations via generalized tensor decompositions
- Expander-Based Cryptography Meets Natural Proofs
- Cryptography in constant parallel time
- Actively secure arithmetic computation and VOLE with constant computational overhead
- scientific article; zbMATH DE number 7650354 (Why is no real title available?)
- Minimizing locality of one-way functions via semi-private randomized encodings
- Cryptographic hardness of random local functions -- survey
- Oblivious transfer with constant computational overhead
- scientific article; zbMATH DE number 7758323 (Why is no real title available?)
This page was built for publication: Cryptographic hardness of random local functions. Survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q332271)
