LOGBOOK

HELP

1 / 27
Other keys: showSpace: good1-4: rate0: skip5: flag6: invert

Question

What is a one-way function, and why is the word "impossible" in its definition not mathematically exact?

Answer

A one-way function is easy to compute in one direction (y = f(x)) but computationally infeasible to invert (finding x from y).

One-way function: easy forward, infeasible to invert without a trapdoor

* Easy one way, practically impossible the other — a trapdoor (like RSA's prime factors) is the only shortcut back. *

The formal definition:

  1. Computing $y = f(x)$ is computationally easy (polynomial time)
  2. 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:

The idea of trapdoor function. A trapdoor function f with its trapdoor t can be generated by an algorithm Gen. f can be efficiently computed, i.e., in probabilistic polynomial time. However, the computation of the inverse of f is generally hard, unless the trapdoor t is given.[1]
The idea of trapdoor function. A trapdoor function f with its trapdoor t can be generated by an algorithm Gen. f can be efficiently computed, i.e., in probabilistic polynomial time. However, the computation of the inverse of f is generally hard, unless the trapdoor t is given.[1]
IkamusumeFan · CC BY-SA 4.0 · Wikimedia Commons
or press any other key