Easy to compute, hard to reverse. This asymmetry is the foundation everything in cryptography is built on — without it, secure communication, digital signatures, and password storage all collapse.
Blending fruit into a smoothie is easy. Unblending a smoothie back into whole strawberries and bananas is impossible. That is a one-way function: a transformation that is trivial to perform and infeasible to undo.
Formally: given x, computing f(x) is efficient. Given f(x), finding any x that produces that output is computationally infeasible — not because no algorithm exists, but because no efficient algorithm is known.
Some one-way functions have a secret shortcut. With knowledge of the trapdoor, reversing the function becomes easy. Without it, the function remains infeasible to invert.
This is the basis of public-key cryptography. The public key defines the one-way function. The private key is the trapdoor. Anyone can encrypt (compute forward), but only the key holder can decrypt (reverse via the trapdoor).
No one has proven that one-way functions exist. We have candidate functions — integer factorization, discrete logarithm — where no efficient reverse algorithm has been found despite decades of effort. But “no one has found a fast algorithm” is not the same as “no fast algorithm exists.” This gap between evidence and proof is a fundamental open problem in computer science.
When cryptographers say “hard,” they mean a precise thing: no known algorithm solves the problem in polynomial time as the input size grows. An attacker would need to perform an amount of work that grows exponentially — making the attack infeasible for sufficiently large inputs, even with enormous computational resources.
This is a statement about the best known algorithms, not about the universe of possible algorithms. Every cryptographic system is a bet that the underlying hard problem stays hard.
The question “do one-way functions exist?” is closely related to the P vs NP problem. If P = NP — if every problem whose solution can be efficiently verified can also be efficiently solved — then one-way functions cannot exist. Every cryptographic hash could be reversed, every encryption broken, every signature forged.
Cryptography implicitly assumes P is not equal to NP. The entire field is built on this unproven conjecture. If someone proves P = NP constructively, all of modern cryptography collapses overnight.
One-way functions appear throughout everyday software, whether or not they are named as such.
Password storage: passwords are hashed with bcrypt or argon2. The server stores f(password), never the password itself. Authentication means computing f(input) and comparing. A database breach reveals hashes, not passwords — because the function is one-way.
Content addressing: git identifies every object — commits, trees, blobs — by the SHA hash of its content. The hash is easy to compute, and two different objects producing the same hash is vanishingly unlikely. This is a one-way function providing integrity guarantees.
Integrity checking: download a file, compute its SHA-256 hash, compare to the published hash. If they match, the file hasn’t been tampered with. The one-way property ensures an attacker cannot craft a different file with the same hash (assuming collision resistance holds).
Every system that stores credentials, verifies data integrity, or relies on content-addressable storage depends on one-way functions. A system that stores reversible credentials or relies on obscurity instead of computational hardness has a design flaw — not a tradeoff.
One-way functions are not encryption. Encryption is reversible by design (with the key). One-way functions are irreversible by design (even with full knowledge of the function). Confusing the two leads to security vulnerabilities — like “encrypting” passwords with AES instead of hashing them, which means anyone with the key can recover every password.
This lesson establishes:
Next: Symmetric Encryption