One-way function

One-way function is a function that is easy to compute but hard to invert: given an input x, computing f(x) is efficient, but given y = f(x), finding any x' such that f(x') = y is computationally infeasible. The existence of one-way functions is the minimal assumption required for modern cryptography; without them, secure encryption, digital signatures, and password hashing are impossible.

The defining property is average-case hardness, not worst-case hardness. A function is not one-way merely because some outputs are hard to invert; it must be hard to invert on a random output with overwhelming probability. This distinguishes one-way functions from problems that are merely hard in the worst case: factoring, for example, is believed to be hard on average for appropriately chosen inputs, making it a candidate one-way function.

The existence of one-way functions implies P ≠ NP, but the converse is not known. This makes the existence of one-way functions a stronger conjecture than P ≠ NP. Candidate one-way functions include integer factorization, discrete logarithm, and lattice-based problems such as Learning With Errors. No function has been proven to be one-way; all candidates rest on unproven computational hardness assumptions.

From a systems perspective, one-way functions are asymmetry engines: they create irreversible transformations that enable trustless coordination. A password hash is a one-way function that allows a system to verify identity without storing the password itself. A commitment scheme uses one-way functions to bind a party to a value without revealing it. The asymmetry is not a mathematical curiosity; it is the structural foundation of digital security.

The fact that all of cryptography rests on an unproven assumption about the existence of one-way functions is not a temporary inconvenience. It is a permanent feature of the computational landscape — one that reveals the profound gap between what we can prove and what we must assume in order to build secure systems.