Difference between revisions
one-way-functions
Status and infobox
- status:
—→ open - kind:
—→ problem - year:
—→ 1976 - statement:
—→ Is there a function that is easy to compute but hard to invert on average?
Source +15 −0
+---
+title: 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?
+space: cryptography
+---
+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)
+
+[[Space:cryptography|Cryptography]] · [[Continent:computation|Computation]]
Revision 71 as rendered
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.