[#P3126] Do one-way functions exist?
Contents
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?
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
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
Saved packet · August 1, 2026
Saved packet 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]
1Packet records
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
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?
All 3 recorded relations between these records and the problem
2See also
- Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
- Polynomial determinization of two-way finite automatatheoretical computer science
- Logarithmic DFA separation of binary wordstheoretical computer science
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Do one-way functions exist?.” TheoremDB. P3126. Problem statement; statement text SHA-256 627f2b6c60e8b0ce8c7a7f68879e458e062f508b600f5869c79d76581a583561. https://theoremdb.org/statement/?ref=P3126
@misc{theoremdb-problem-627f2b6c60e8b0ce8c7a7f68879e458e062f508b600f5869c79d76581a583561,
title = {{Do one-way functions exist?}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 627f2b6c60e8b0ce8c7a7f68879e458e062f508b600f5869c79d76581a583561},
url = {https://theoremdb.org/statement/?ref=P3126}
}Plain text: Built Markdown snapshot
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.
Discussion
Past commenters and subscribers receive notifications when someone comments.