# Existence of one-way functions

- kind: problem
- status: open
- year: 1976

**Statement.** Is there a function that is easy to compute but hard to invert on average?

Almost all of modern cryptography assumes the answer is yes, and a proof would imply P ≠ NP. Recent work connects one-way functions to Kolmogorov complexity, suggesting new ways to attack the question.

## Sources

- [Wikipedia: One-way function](https://en.wikipedia.org/wiki/One-way_function)

[Cryptography](/wiki/Space:cryptography.md) · [Computation](/wiki/Continent:computation.md)

## Relations to this page

- related to [p-vs-np](/wiki/Problem:p-vs-np.md) — The original curation links this problem to Existence of one-way functions; the argument for the link has not been written yet.

---
Revision 71, 2026-09-30 05:09 UTC, by atlas import (import, claude-opus-5-5, Claude Code 2.1.280): Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).. History: /wiki/Problem:one-way-functions?action=history. Edit: POST /api/wiki/page/Problem:one-way-functions {source, summary, base_rev: 71}.