[#P3126] Do one-way functions exist?
Problem. Does there exist a polynomial-time computable family \(f_n:\{0,1\}^n\to\{0,1\}^{\operatorname{poly}(n)}\) such that every probabilistic polynomial-time algorithm, given \(f_n(x)\) for uniform \(x\), finds any preimage with only negligible probability?
1Context
Known frontier: Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives. Open boundary: No unconditional construction or impossibility theorem is known.
2Problem setup
Definition 1 (negligible). Smaller than n^{-c} for every constant c>0 for all sufficiently large n.
Definition 2 (preimage resistance). Efficient inversion succeeds with negligible probability over uniform input and algorithm randomness.
Remark 1. This average-case hardness primitive is equivalent to the existence of many basic cryptographic constructions. Worst-case assumptions such as P≠NP alone do not currently yield it.
3What counts as a solution
- Construct such a family and prove security unconditionally.
- Or prove every polynomial-time computable function family can be inverted with nonnegligible probability in probabilistic polynomial time.
1Status
Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives. Exact unresolved remainder: No unconditional construction or impossibility theorem is known.[1][2]
1Records
Notes and companion material
Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives. Exact unresolved remainder: No unconditional construction or impossibility theorem is known.
- Equivalent-formulation queries: unconditional existence one way functions open problem 2026; one-way functions exist average case complexity open
- Strongest checked neighboring result: Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives.
- Exact unresolved remainder: No unconditional construction or impossibility theorem is known.
How the 4 records connect
ProblemDo one-way functions exist?
2See also
- Is VP equal to VNP?theoretical computer science
- Is there a truly subcubic algorithm for weighted APSP?theoretical computer science
- Strong Exponential Time Hypothesistheoretical computer science
How to cite
TheoremDB contributors, “Do one-way functions exist?,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/one-way-functions-existThis page as plain text: one-way-functions-exist.md
This problem includes 4 records joined by 3 typed links, sourced from doi.org[1], current as of August 1, 2026.
1References
- Packet source. R. Impagliazzo and M. Luby, “One-way functions are essential for complexity based cryptography”. 30th Annual Symposium on Foundations of Computer Science (1989), 230-235. DOI 10.1109/SFCS.1989.63483. main equivalence theorems. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Shows why one-way functions form a minimal foundation for broad cryptographic goals.Also cited at R. Impagliazzo and M. Luby, One-way functions are essential for complexity based cryptography, FOCS 1989. main equivalence theorems.Source used to assess the problem's recorded status.For Do one-way functions exist?: This is the dated publication status for the canonical target Do one-way functions exist?.Source named by the research packet.
- James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma, “One-Way Functions Imply Secure Computation in a Quantum World,” IACR ePrint 2020/1487; CRYPTO 2021. abstract and introduction. ↗journal article · primary source · IACR ePrint 2020/1487 record checked 2026-08-01 · checked 2026-08-01Source use: original summary.Shows that assuming one-way functions yields secure computation against quantum adversaries, illustrating the primitive's modern consequences without claiming an unconditional construction.Source used to assess the problem's recorded status.For Do one-way functions exist?: Shows that assuming one-way functions yields secure computation against quantum adversaries, illustrating the primitive's modern consequences without claiming an unconditional construction.
Original TheoremDB editorial statement and source synthesis; external works are used for citation only.