Capturing one-way functions via NP-hardness of meta-complexity

Cites work

A Pseudorandom Generator from any One-way Function
An Unconditional Study of Computational Zero Knowledge
Average Case Complete Problems
Average-case hardness of NP from exponential worst-case hardness assumptions
Bit commitment using pseudorandomness
Circuit lower bounds from NP-hardness of MCSP under turing reductions
Circuit minimization problem
Computational depth: Concept and applications
Conditional complexity and codes
Cryptography from Information Loss.
Designing programs that check their work
Foundations of Cryptography
scientific article; zbMATH DE number 4179276 (Why is no real title available?)
scientific article; zbMATH DE number 5081744 (Why is no real title available?)
scientific article; zbMATH DE number 7515768 (Why is no real title available?)
scientific article; zbMATH DE number 7561748 (Why is no real title available?)
scientific article; zbMATH DE number 7650416 (Why is no real title available?)
If NP languages are hard on the worst-case, then it is easy to find their hard instances
Limitations of Hardness vs. Randomness under Uniform Reductions
On basing one-way functions on NP-hardness
On basing size-verifiable one-way functions on NP-hardness
On nonadaptive reductions to the set of random strings and its dense subsets
On the average-case complexity of MCSP and its variants
On the Complexity of Learning Minimum Time-Bounded Turing Machines
On the Cryptographic Applications of Random Functions (Extended Abstract)
On Worst‐Case to Average‐Case Reductions for NP Problems
Pseudorandomness and average-case complexity via uniform reductions
Random-Self-Reducibility of Complete Sets
Randomness vs time: Derandomization under a uniform assumption
Super-logarithmic depth lower bounds via the direct sum in communication complexity
The Shrinkage Exponent of de Morgan Formulas is 2
Theory of Cryptography
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Worst-Case to Average-Case Reductions Revisited

Cited in

(7)

Quantum cryptography and meta-complexity
Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
A meta-complexity characterization of quantum cryptography
Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
NP-hardness of approximating meta-complexity: a cryptographic approach
Lower bounds for Levin-Kolmogorov complexity
SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Capturing one-way functions via NP-hardness of meta-complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499280)