A duality between one-way functions and average-case symmetry of information
From MaRDI portal
Publication:6499281
DOI10.1145/3564246.3585138MaRDI QIDQ6499281
Rahul Ilango, Shuichi Hirahara, Igor C. Oliveira, Zhenjian Lu, Mikito Nanashima
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bit commitment using pseudorandomness
- Language compression and pseudorandom generators
- A note on computational indistinguishability
- Probabilistic encryption
- Symmetry of information and one-way functions
- On symmetry of information and polynomial time invertibility
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- Pseudorandomness and average-case complexity via uniform reductions
- Resource bounded symmetry of information revisited
- Resource-Bounded Kolmogorov Complexity Revisited
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- A Pseudorandom Generator from any One-way Function
- Foundations of Cryptography
- Kolmogorov Complexity and Algorithmic Randomness
- Randomness and Intractability in Kolmogorov Complexity
- Hardness magnification near state-of-the-art lower bounds
- Power from Random Strings
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- An introduction to Kolmogorov complexity and its applications
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Average-case hardness of NP from exponential worst-case hardness assumptions
- Pseudodeterministic algorithms and the structure of probabilistic time
- Hardness of KT characterizes parallel cryptography
This page was built for publication: A duality between one-way functions and average-case symmetry of information
