Existence of one-way functions
Do functions exist that are easy to compute but hard to invert?
Summary
Why it is open
Whitfield Diffie and Martin Hellman defined the idea in 1976: a function f is one-way if f(x) is easy to compute for every x, yet for almost all y in its range it is "computationally infeasible" to find any x with f(x) = y; they credit R. M. Needham with first using such functions in login procedures, where a computer stores f(password) instead of the password [1]. In the modern definition, f is computable in polynomial time and no probabilistic polynomial-time algorithm can invert it with inverse-polynomial probability for infinitely many input lengths [8]. Inverting means finding any preimage, not necessarily the original input [1].
A resolution is either a proof that some function meets this definition, or a proof that every efficiently computable function can be inverted on average. The first would settle more than cryptography. As Shuichi Hirahara puts it, "no one-way function exists if NP is easy"; more strongly, the existence of a one-way function implies that NP cannot be computed by polynomial-size circuits almost everywhere, so a proof that one exists would also prove P ≠ NP [10] (see the Papex page P versus NP). The converse is the open part: proving that P ≠ NP, a statement about the worst case, is not known to yield one-way functions, which need hardness on average [10]. Diffie and Hellman already noted that NP-completeness describes only worst-case difficulty, whereas cryptography depends on typical cases [1].
The Wikipedia list on which this page's status rests asks "Do one-way functions exist?" and, beneath it, "Is public-key cryptography possible?" [14]. Leonid Levin calls the existence of one-way functions "arguably the most important problem in computer theory" [6].
What is known
Candidates (1976–2020). Diffie and Hellman based their key exchange on the apparent difficulty of computing logarithms modulo a prime: "The security of our technique depends crucially on the difficulty of computing logarithms mod q" [1] (see the Papex page Complexity of the discrete logarithm). Levin notes that RSA and much of modern cryptography assume that recovering the prime factors of a product pq is infeasible [6] (see Complexity of integer factorisation). Yanyi Liu and Rafael Pass name factoring, the discrete logarithm and lattice problems as the most notable bases for candidates, and note that the factoring and discrete-logarithm candidates can be broken by a quantum computer, citing Peter Shor's algorithm [8].
What one-way functions are equivalent to (1989–1999). Russell Impagliazzo and Michael Luby showed in 1989 that any secure protocol for several standard tasks, among them private-key encryption, authentication, bit commitment and coin flipping, can be converted into a one-way function [3]. Johan Håstad, Impagliazzo, Levin and Luby showed that a pseudorandom generator can be built from any one-way function, so one exists if and only if the other does [5]. One-way functions also suffice for pseudorandom functions, digital signatures and commitment schemes; these "private-key" primitives exclude public-key encryption [8].
Universal one-way functions. Levin constructed a single function that is one-way if any one-way function exists [2, 8]. An algorithm that inverts it would therefore show that no one-way functions exist [4]. Liu and Pass call the construction artificial, since it relies on an enumeration argument [8]. In 2003 Levin gave a combinatorial version, Tiling Expansion, and proved that it "is a owf if and only if owfs exist" [6].
Five worlds (1995). Impagliazzo described five possible outcomes, "not currently known to be false": Algorithmica, where P = NP or an equivalent holds; Heuristica, where NP problems are hard in the worst case but easy on average for any samplable distribution; Pessiland, "the worst of all possible worlds", with hard average-case problems but no one-way functions; Minicrypt, where one-way functions exist but public-key cryptography is impossible; and Cryptomania, where public-key cryptography is possible [4]. Basing one-way functions on the worst-case hardness of NP means ruling out both Heuristica and Pessiland [10].
Kolmogorov complexity (2020–2024). The Kolmogorov complexity of a string is the length of the shortest program that prints it; the time-bounded version K^t only counts programs that finish within time t [8]. Liu and Pass proved in 2020 that, for every polynomial t(n) ≥ (1 + ε)n, one-way functions exist if and only if K^t is mildly hard on average: for some polynomial p, no probabilistic polynomial-time algorithm computes it on more than a 1 − 1/p(n) fraction of n-bit strings [8]. They later considered MKtP, the problem of deciding whether a string's Levin–Kolmogorov complexity Kt is at most a given bound. It is mildly hard on average for algorithms that may err exactly when infinitely-often one-way functions exist, and for algorithms that never err exactly when EXP ≠ BPP, that is, when exponential time is not contained in randomised polynomial time [9]. Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima and Igor Oliveira proved that one-way functions exist if and only if time-bounded symmetry of information, which "relates the complexity of a pair of strings and their conditional complexities", fails on average [11]. Hirahara gave in 2023 what he calls the first characterisation by worst-case hardness: one-way functions exist if and only if approximating "distributional Kolmogorov complexity" is NP-hard under randomised reductions and NP is hard in the worst case [10]. Hirahara and Nanashima added that one-way functions exist if and only if every NP problem has a computational zero-knowledge proof, an interactive proof that reveals nothing to an efficient verifier beyond the statement's truth, and NP is hard in the worst case [13]. For public-key cryptography, Marshall Ball, Liu, Noam Mazor and Pass characterised key agreement by the worst-case hardness of a promise problem about interactive Kolmogorov complexity [12].
These equivalences do not decide the question. Hirahara wrote in 2023 that Heuristica and Pessiland "are consistent with our current knowledge of complexity theory and cryptography" [10]. On 14 October 2026 the Wikipedia list still included the question [14].
Main approaches
Basing one-way functions on NP. Show that if NP is hard in the worst case, one-way functions exist. Strongest evidence: the 2023 and 2024 characterisations reduce the question to NP-hardness of a natural problem or to zero knowledge for NP [10, 13]; Hirahara uses non-black-box reductions and non-relativizing techniques, which he argues are unlikely to be subject to the known limits [10]. Main difficulty: Andrej Bogdanov and Luca Trevisan proved that non-adaptive reductions cannot base the security of a one-way function on the worst-case complexity of an NP-complete problem unless the polynomial hierarchy collapses [7]; relativizing proofs cannot rule out Pessiland, and a result of Michael Saks and Rahul Santhanam makes NP-hardness of time-bounded Kolmogorov complexity under efficient reductions unlikely [10]. The conditions in the new characterisations are themselves unproven [10, 13].
Meta-complexity. Study problems that ask how complex a string or function is, such as computing K^t. Strongest evidence: unconditional equivalences with one-way functions [8, 11]; Liu and Pass describe the remaining step from EXP ≠ BPP to one-way functions as the "seemingly 'minor' technical gap" between errorless and error-prone hardness [9]. Main difficulty: whether errorless and error-prone average-case complexities of NP are equivalent is, in Hirahara's words, "a long-standing open question" [10].
Complete one-way functions. Find natural functions that are one-way if any function is. Strongest evidence: Levin's universal function and Tiling Expansion [2, 6]. Main difficulty: Levin wrote that his appeal "to produce even one clean example remained unanswered for two decades", and he left reducing Tiling Expansion to other natural one-way functions as an open problem [6].
From Minicrypt to Cryptomania. Show that one-way functions give public-key cryptography. Strongest evidence: Ball, Liu, Mazor and Pass show that this "boils down to demonstrating a worst-case reduction between two closely related promise problems" [12]. Main difficulty: in 1995 Impagliazzo saw no nice characterisation of secret-key agreement protocols [4], and Hirahara counts excluding Minicrypt among four central challenges in theoretical computer science [10].
Open sub-questions
- Errorless to error-prone. Can errorless mild average-case hardness of MKtP be upgraded to hardness against algorithms that may err? By Liu and Pass, this would derive infinitely-often one-way functions from EXP ≠ BPP [9].
- NP-hardness of meta-complexity. Is approximating distributional Kolmogorov complexity NP-hard under randomised polynomial-time reductions? If NP is hard in the worst case, this is equivalent to the existence of one-way functions [10].
- Padding. Is distributional Kolmogorov complexity paddable by an approximation-preserving reduction, as Hirahara's Meta-Complexity Padding Conjecture states? If so, worst-case hardness of approximating the Minimum Circuit Size Problem (the size of the smallest circuit computing a given function) characterises one-way functions [10].
- A natural complete function. Can Tiling Expansion be reduced to a more familiar one-way function candidate, proving that candidate complete, as Levin hoped [6]?
- Key agreement. Is there a worst-case reduction between the two interactive Kolmogorov complexity problems of Ball, Liu, Mazor and Pass, which would base key agreement on one-way functions [12]?
- Laconic zero knowledge. Does NP have a laconic zero-knowledge argument system? Hirahara and Nanashima show that this would give public-key encryption based on the worst-case hardness of NP [13].
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Diffie, W. & Hellman, M. E. (1976). New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654. 10.1109/TIT.1976.1055638 · Checked 14 Oct 2026
- Levin, L. A. (1987). One-way functions and pseudorandom generators. Combinatorica 7(4), 357–363. 10.1007/BF02579323 · Checked 14 Oct 2026
- Impagliazzo, R. & Luby, M. (1989). One-way functions are essential for complexity based cryptography. In 30th Annual Symposium on Foundations of Computer Science (FOCS), 230–235. 10.1109/SFCS.1989.63483 · Checked 14 Oct 2026
- Impagliazzo, R. (1995). A personal view of average-case complexity. In Proceedings of Structure in Complexity Theory, Tenth Annual IEEE Conference, 134–147. 10.1109/SCT.1995.514853 · Checked 14 Oct 2026
- Håstad, J., Impagliazzo, R., Levin, L. A. & Luby, M. (1999). A pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396. 10.1137/S0097539793244708 · Checked 14 Oct 2026
- Levin, L. A. (2003). The tale of one-way functions. Problems of Information Transmission 39(1), 92–103. 10.1023/A:1023634616182 · Checked 14 Oct 2026
- Bogdanov, A. & Trevisan, L. (2006). On worst-case to average-case reductions for NP problems. SIAM Journal on Computing 36(4), 1119–1159. 10.1137/S0097539705446974 · Checked 14 Oct 2026
- Liu, Y. & Pass, R. (2020). On one-way functions and Kolmogorov complexity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 1243–1254. 10.1109/FOCS46700.2020.00118 · Checked 14 Oct 2026
- Liu, Y. & Pass, R. (2023). Toward basing cryptography on the hardness of EXP. Communications of the ACM 66(5), 91–99. 10.1145/3587167 · Checked 14 Oct 2026
- Hirahara, S. (2023). Capturing one-way functions via NP-hardness of meta-complexity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC '23), 1027–1038. 10.1145/3564246.3585130 · Checked 14 Oct 2026
- Hirahara, S., Ilango, R., Lu, Z., Nanashima, M. & Oliveira, I. C. (2023). A duality between one-way functions and average-case symmetry of information. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC '23), 1039–1050. 10.1145/3564246.3585138 · Checked 14 Oct 2026
- Ball, M., Liu, Y., Mazor, N. & Pass, R. (2023). Kolmogorov comes to Cryptomania: on interactive Kolmogorov complexity and key-agreement. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 458–483. 10.1109/FOCS57990.2023.00034 · Checked 14 Oct 2026
- Hirahara, S. & Nanashima, M. (2024). One-way functions and zero knowledge. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC '24), 1731–1738. 10.1145/3618260.3649701 · Checked 14 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 14 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 29 Sep 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.