What is a one-way function, and why is the word "impossible" in its definition not mathematically exact?
A one-way function is easy to compute in one direction (y = f(x)) but computationally infeasible to invert (finding x from y).
* Easy one way, practically impossible the other — a trapdoor (like RSA's prime factors) is the only shortcut back. *
The formal definition:
- Computing $y = f(x)$ is computationally easy (polynomial time)
- Computing $x = f^{-1}(y)$ is technically impossible — meaning it would take the best algorithms with massive resources over 100,000 years
The terms "easy" and "impossible" aren't mathematically rigorous — they're practical statements about computational effort. Mathematically, "easy" means polynomial time, and "impossible" means the inverse computation time grows exponentially per bit.
Tip: Think of a blender — turning fruit into a smoothie is easy, but reconstructing the original fruit from the smoothie is practically impossible.
Go deeper:
One-way function (Wikipedia) — the formal easy-to-compute / hard-to-invert definition and why their very existence is still an open problem (it would imply P ≠ NP).- Trapdoor function (Wikipedia) — the special case where a secret makes inversion easy, the engine behind RSA.