One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions

DOI10.1007/978-3-031-38545-2_21OpenAlexW4385654457MaRDI QIDQ6145928

Yanyi Liu, Rafael Pass

Publication date: 2 February 2024

Published in: Advances in Cryptology – CRYPTO 2023 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-38545-2_21

Mathematics Subject Classification ID

Cryptography (94A60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Bit commitment using pseudorandomness
• Probabilistic encryption
• On the notion of infinite pseudorandom sequences
• Universal classes of hash functions
• The tale of one-way functions
• On the Cryptographic Applications of Random Functions (Extended Abstract)
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Simple extractors for all min-entropies and a new pseudorandom generator
• New directions in cryptography
• A method for obtaining digital signatures and public-key cryptosystems
• A Pseudorandom Generator from any One-way Function
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Three approaches to the quantitative definition of information^*
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part I
• Robustness of average-case meta-complexity via pseudorandomness