Cryptographic hardness of random local functions. Survey

DOI10.1007/S00037-015-0121-8zbMATH Open1360.94293OpenAlexW2284855724MaRDI QIDQ332271FDOQ332271

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

Recommendations

Cryptographic hardness of random local functions -- survey
Cryptography in constant parallel time
Algebraic attacks against random local functions and their countermeasures
Cryptography with constant input locality
Cryptography with Constant Input Locality

cryptography local functions public-key encryption hash functions one-way functions pseudorandom generators NC0 constant-depth circuits

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

Selection of relevant features and examples in machine learning
Relations between average case complexity and approximation complexity
A method for obtaining digital signatures and public-key cryptosystems
Small-Bias Probability Spaces: Efficient Constructions and Applications
New directions in cryptography
Title not available (Why is that?)
Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
Foundations of Cryptography
Foundations of Cryptography
On the power of unique 2-prover 1-round games
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Pseudorandomness for network algorithms
Computationally private randomizing polynomials and their applications
Public-key cryptography from different assumptions
Pseudorandom bits for polynomials
Candidate One-Way Functions Based on Expander Graphs
Cryptography with constant computational overhead
Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
On the security of Goldreich's one-way function
Title not available (Why is that?)
Bounded Independence Fools Halfspaces
Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
On ε‐biased generators in NC⁰
Pseudorandomness for Read-Once Formulas
Cryptography in $NC^0$
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
On pseudorandom generators with linear stretch in $\mathrm{NC}^{0}$
A spectral technique for coloring random 3-colorable graphs (preliminary version)
On the one-way function candidate proposed by Goldreich
A Dichotomy for Local Small-Bias Generators
SDP gaps from pairwise independence
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
Title not available (Why is that?)
A spectral technique for random satisfiable 3CNF formulas
Polylogarithmic independence fools $\mathrm{AC}^{0}$ circuits
A Better Algorithm for Random k-SAT
Cryptographic limitations on learning Boolean formulae and finite automata
Short proofs are narrow—resolution made simple
Locally Computable UOWHF with Linear Shrinkage
Robust Pseudorandom Generators
On the solution-space geometry of random constraint satisfaction problems
Every 2-CSP allows nontrivial approximation
Approximation resistant predicates from pairwise independence
The sum of $D$ small-bias generators fools polynomials of degree $D$

Cited In (14)

Expander-Based Cryptography Meets Natural Proofs
Oblivious transfer with constant computational overhead
Cryptography in constant parallel time
Title not available (Why is that?)
Cryptography with Constant Input Locality
Expander-based cryptography meets natural proofs
On the Complexity of Random Satisfiability Problems with Planted Solutions
Title not available (Why is that?)
Actively secure arithmetic computation and VOLE with constant computational overhead
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
Algebraic Attacks against Random Local Functions and Their Countermeasures
Compressing unit-vector correlations via sparse pseudorandom generators
Learning polynomial transformations via generalized tensor decompositions
Minimizing locality of one-way functions via semi-private randomized encodings

Uses Software

McEliece

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)