A duality between one-way functions and average-case symmetry of information

Cites work

A note on computational indistinguishability
A Pseudorandom Generator from any One-way Function
An introduction to Kolmogorov complexity and its applications
Average-case hardness of NP from exponential worst-case hardness assumptions
Bit commitment using pseudorandomness
Extracting all the randomness and reducing the error in Trevisan's extractors
Foundations of Cryptography
Hardness magnification near state-of-the-art lower bounds
Hardness of KT characterizes parallel cryptography
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 7701424 (Why is no real title available?)
Kolmogorov Complexity and Algorithmic Randomness
Language compression and pseudorandom generators
On symmetry of information and polynomial time invertibility
On the Complexity of Learning Minimum Time-Bounded Turing Machines
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
Power from Random Strings
Probabilistic encryption
Pseudodeterministic algorithms and the structure of probabilistic time
Pseudorandomness and average-case complexity via uniform reductions
Randomness and intractability in Kolmogorov complexity
Resource bounded symmetry of information revisited
Resource-bounded Kolmogorov complexity revisited
Symmetry of information and one-way functions
THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

Cited in

(9)

Quantum cryptography and meta-complexity
Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
Exact search-to-decision reductions for time-bounded Kolmogorov complexity
Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
A meta-complexity characterization of quantum cryptography
Space-bounded online Kolmogorov complexity is additive
Computable one-way functions on the reals
One-way functions and pKt complexity
SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: A duality between one-way functions and average-case symmetry of information

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