Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity

DOI10.1145/3406325.3451121MaRDI QIDQ6087039zbMATH OpenOpenAlexFDO

Authors Yanyi Liu, Rafael Pass

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3406325.3451121

zbMATH Keywords

Kolmogorov complexityone-way functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(12)

• Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• A meta-complexity characterization of quantum cryptography
• On black-box meta complexity and function inversion
• NP-hardness of approximating meta-complexity: a cryptographic approach
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Lower bounds for Levin-Kolmogorov complexity
• Towards general-purpose program obfuscation via local mixing
• Learning algorithms from circuit lower bounds
• A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity

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