Unveiling the NP-Hardness of Meta-Complexity in One-Way Functions 🔐

Shuichi Hirahara (National Institute of Informatics, Tokyo)
https://simons.berkeley.edu/talks/shuichi-hirahara-national-institute-informatics-tokyo-2023-05-02
Minimal Complexity Assumptions for Cryptography

We present the first characterization of a one-way function by worst-case hardness assumptions: A one-way function exists iff NP is hard in the worst case and "distributional Kolmogorov complexity" is NP-hard under randomized reductions. Here, the t-time bounded distributional Kolmogorov complexity of a string x given a distribution D is defined to be the length of a shortest t-time program that outputs x given as input y drawn from the distribution D with high probability. The characterization suggests that the recent approaches of using meta-complexity to exclude Heuristica and Pessiland from Impagliazzo's five worlds are both sufficient and necessary.