# P3126: Do one-way functions exist?

- ID: `P3126`
- Reference: `one-way-functions-exist`
- Page: https://theoremdb.org/statements/P3126
- Record maturity: Reviewed problem with recorded work

## 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?

### Context

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.

### Problem setup

- **Definition (negligible).** Smaller than n^{-c} for every constant c>0 for all sufficiently large n.
- **Definition (preimage resistance).** Efficient inversion succeeds with negligible probability over uniform input and algorithm randomness.
- **Remark.** 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.

### What 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.

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives.

The exact unresolved remainder is: No unconditional construction or impossibility theorem is known.

A complete resolution must meet the following acceptance conditions:
- 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.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Candidate constructions follow from factoring, lattice, coding, and other assumptions; black-box and structural equivalences connect OWFs to cryptographic primitives. Unresolved remainder: No unconditional construction or impossibility theorem is known. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): No unconditional construction or impossibility theorem is known.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `one-way-functions-exist`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.1109/SFCS.1989.63483
   - Also cited at R. Impagliazzo and M. Luby, One-way functions are essential for complexity based cryptography, FOCS 1989. main equivalence theorems
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Shows why one-way functions form a minimal foundation for broad cryptographic goals.
   - 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.
2. <a id="reference-2"></a>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 https://eprint.iacr.org/2020/1487
   - journal_article; primary source; IACR ePrint 2020/1487 record checked 2026-08-01; checked 2026-08-01
   - Source 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.