Do Worst-Case Complexity Separations Imply One-Way Functions? (Impagliazzo's Heuristica-Pessiland Question)

It remains open whether worst-case computational hardness suffices for cryptography: no proof is known that $\mathsf{P}\neq\mathsf{NP}$, or any weaker standard worst-case separation such as $\mathsf{EXP}\neq\mathsf{BPP}$, implies the existence of one-way functions (OWFs), and it is equally open whether the failure of this implication - Impagliazzo's Heuristica and Pessiland worlds - is consistent. The meta-complexity program has reduced the weakest standard form to a precise transfer question: by results of Liu and Pass, infinitely-often OWFs exist iff MKtP (the Levin-Kolmogorov complexity problem) is mildly hard on average in the two-sided sense, while $\mathsf{EXP}\neq\mathsf{BPP}$ holds iff MKtP is mildly hard on average in the errorless sense, so $\mathsf{EXP}\neq\mathsf{BPP}$ implying infinitely-often OWFs is exactly the errorless-to-two-sided average-case transfer for MKtP. Hirahara and Nanashima's 2026 sharp characterization reduces ruling out Pessiland to closing a small approximation gap - $\ell/\mathrm{polylog}(\ell)$ (originally $\ell^{1-o(1)}$) versus $O(\ell)$ - for the minimum description length of programs in agnostic learning. The question - in its natural generality, unrestricted OWFs from unrestricted standard worst-case assumptions - remains open as of August 2026.

Background

A one-way function (OWF) is a polynomial-time computable function $f:\{0,1\}^*\to\{0,1\}^*$ such that every probabilistic polynomial-time algorithm, given $f(x)$ for a uniformly random input $x$, fails to find any preimage with non-negligible probability. OWFs are the minimal computational assumption of cryptography: their existence is equivalent to that of pseudorandom generators (deterministic algorithms whose output is computationally indistinguishable from truly random strings), pseudorandom functions, private-key encryption, digital signatures, and commitment schemes. An infinitely-often OWF (ioOWF) is the weaker variant whose inversion hardness is required only for infinitely many input lengths rather than all of them.

Whether OWFs exist is open, and every known candidate is justified by average-case hardness - hardness of a problem on random instances drawn from an efficiently samplable distribution - rather than by worst-case hardness, which only asserts hardness on some instances. Impagliazzo's influential five-worlds taxonomy classifies the possible relationships between these notions: Algorithmica ($\mathsf{P}=\mathsf{NP}$), Heuristica ($\mathsf{P}\neq\mathsf{NP}$ but every NP problem is easy on average), Pessiland (NP problems are hard on average, yet OWFs do not exist), Minicrypt (OWFs exist), and Cryptomania (public-key cryptography exists). The question of whether worst-case hardness suffices for cryptography is precisely the question of whether Heuristica and Pessiland are consistent worlds: if $\mathsf{P}\neq\mathsf{NP}$ (or a weaker standard separation such as $\mathsf{EXP}\neq\mathsf{BPP}$, where $\mathsf{EXP}$ is deterministic $2^{n^{O(1)}}$-time and $\mathsf{BPP}$ is bounded-error randomized polynomial time) implied OWFs, both worlds would be empty.

The meta-complexity program - the study of problems whose subject matter is itself complexity, such as MKtP, the problem of deciding whether the Levin-Kolmogorov complexity $Kt(x)$ (the minimum of program length plus the logarithm of running time, over programs that print $x$) is at most $k$ - has produced sharp equivalences that localize exactly what is missing. Liu and Pass proved that ioOWFs exist if and only if MKtP is mildly hard on average in the two-sided sense (no polynomial-time heuristic decides it correctly on more than a $1-1/\mathrm{poly}$ fraction of instances, where the heuristic may give wrong answers), and that MKtP is mildly hard on average in the errorless sense (the heuristic must output either the correct answer or a 'don't know' symbol on every instance) if and only if $\mathsf{EXP}\neq\mathsf{BPP}$. Thus the weakest standard form of the question - does $\mathsf{EXP}\neq\mathsf{BPP}$ imply ioOWFs? - is exactly the question of whether errorless average-case hardness of MKtP can be boosted to two-sided average-case hardness. Recent work has mapped the surrounding terrain: worst-case hardness plus an additional average-case-flavored primitive suffices (non-trivial zero-knowledge protocols for NP - interactive proofs that convince a verifier of a statement while revealing nothing beyond its truth - under $\mathsf{NP}\not\subseteq\mathsf{ioP/poly}$, the assumption that NP is not solvable by polynomial-size advice-taking machines even on infinitely many input lengths, by Hirahara-Nanashima and 2026 follow-ups); worst-case hardness of meta-complexity problems at the 'boundary' between random and almost-random strings suffices under derandomization assumptions (Liu-Pass); and under the Exponential Time Hypothesis (ETH, the assumption that 3-SAT requires $2^{\Omega(n)}$ time), mild-lossiness conditions on reductions suffice (Fallahpour et al.). Hirahara and Nanashima's sharp characterization shows that ruling out Pessiland is equivalent to closing a small quantitative gap ($\ell/\mathrm{polylog}(\ell)$, improved from $\ell^{1-o(1)}$ in the original April 2026 version, versus $O(\ell)$, where $\ell$ is the 'advice complexity of sampling' of the distribution) in the approximability of the minimum description length of programs in agnostic learning (the PAC learning setting in which the target function need not be exactly representable by the learner's hypothesis class), and identifies a matching coAM barrier. What no work achieves is the unconditional transfer from a standard worst-case separation to one-way functions.

Problem Statement

Determine whether worst-case computational hardness alone implies the existence of one-way functions. The strongest standard form, and the target of the task: prove or refute that $\mathsf{P}\neq\mathsf{NP}$ implies that one-way functions exist. The weakest standard form in which the question has been studied is whether $\mathsf{EXP}\neq\mathsf{BPP}$ implies that infinitely-often one-way functions exist; by the Liu-Pass equivalences this is identical to deciding whether mild errorless average-case hardness of MKtP implies mild two-sided average-case hardness of MKtP. A positive answer supplies an unconditional worst-case-to-average-case transfer and empties Impagliazzo's Heuristica and Pessiland, while a negative answer demonstrates the consistency, in the standard unrelativized model, of the relevant worst-case separation with the non-existence of one-way functions; oracle constructions relativize and settle only the corresponding relativized question. The natural generality of the problem - unrestricted one-way functions derived from unrestricted standard worst-case assumptions - is part of the statement.

References

1. Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of Structure in Complexity Theory, Tenth Annual IEEE Conference (SCT 1995), 1995. DOI: 10.1109/SCT.1995.514853, https://doi.org/10.1109/SCT.1995.514853
2. Yanyi Liu and Rafael Pass. On one-way functions and Kolmogorov complexity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020. DOI: 10.1109/FOCS46700.2020.00118, arXiv:2009.11514, https://arxiv.org/abs/2009.11514
3. Yanyi Liu and Rafael Pass. Toward basing cryptography on the hardness of EXP. Communications of the ACM, 66(5):91-99, 2023. DOI: 10.1145/3587167, https://doi.org/10.1145/3587167
4. Shuichi Hirahara and Mikito Nanashima. One-way functions and zero knowledge. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024. DOI: 10.1145/3618260.3649701, https://doi.org/10.1145/3618260.3649701
5. Shuichi Hirahara and Mikito Nanashima. Learning in Pessiland via inductive inference. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023. DOI: 10.1109/FOCS57990.2023.00033, https://doi.org/10.1109/FOCS57990.2023.00033
6. Shuichi Hirahara and Mikito Nanashima. A sharp characterization of Pessiland. ECCC Technical Report TR26-052, April 2026, revised June 2026 (STOC 2026). DOI: 10.1145/3798129.3800755, https://eccc.weizmann.ac.il/report/2026/052/
7. Shuichi Hirahara, Zhenjian Lu, and Mikito Nanashima. Optimal coding for randomized Kolmogorov complexity and its applications. arXiv:2409.12744, 2024 (FOCS 2024), https://arxiv.org/abs/2409.12744
8. Fabio F. G. Buono. The Observer World: A cryptographic extension of Impagliazzo's five worlds. arXiv:2606.27139, 2026, https://arxiv.org/abs/2606.27139
9. Yanyi Liu and Rafael Pass. Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity. ECCC Technical Report TR25-125, 2025 (CRYPTO 2025). DOI: 10.1007/978-3-032-01855-7_20, https://eccc.weizmann.ac.il/report/2025/125/
10. Yanyi Liu and Rafael Pass. One-way functions and boundary hardness of randomized time-bounded Kolmogorov complexity. ECCC Technical Report TR25-202, 2025 (ITCS 2026). DOI: 10.4230/LIPIcs.ITCS.2026.97, https://eccc.weizmann.ac.il/report/2025/202/
11. Yanyi Liu and Rafael Pass. One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions. In Advances in Cryptology - CRYPTO 2023. DOI: 10.1007/978-3-031-38545-2_21, https://doi.org/10.1007/978-3-031-38545-2_21
12. Pouria Fallahpour, Alex B. Grilo, Garazi Muguruza, and Mahshid Riahinia. Cryptography from lossy reductions: towards OWFs from ETH, and beyond. arXiv:2505.21442, 2025, https://arxiv.org/abs/2505.21442
13. Suvradip Chakraborty, James Hulett, Dakshita Khurana, and Kabir Tomer. Non-trivial zero-knowledge implies one-way functions. arXiv:2602.17651, 2026, https://arxiv.org/abs/2602.17651
14. Rohit Chatterjee, Yunqi Li, and Prashant Nalini Vasudevan. Weak zero-knowledge and one-way functions. arXiv:2602.16156, 2026, https://arxiv.org/abs/2602.16156