A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A one-way function (OWF) is a function that is easy to compute (polynomial time) but hard to invert (no polynomial-time algorithm succeeds on a non-negligible fraction of inputs). OWFs are the minimal assumption of cryptography: they exist if and only if P != NP for certain structured problems, and their existence is necessary and sufficient for private-key cryptography (pseudorandom generators, pseudorandom functions, MACs, symmetric encryption, digital signatures, commitment schemes). Candidate OWFs include integer multiplication (easy to multiply, hard to factor) and modular exponentiation. Proving any function is one-way remains an open problem equivalent in difficulty to separating P from NP.
The concept of a one-way function is the minimal mathematical abstraction underlying all of computational cryptography. Informally, a OWF is a function f that is easy to compute but hard to invert: given x, computing f(x) takes polynomial time, but given f(x), no efficient algorithm can find any preimage x' with f(x') = f(x) except with negligible probability. The hardness is average-case — inversion must fail on a random input with overwhelming probability, not just on carefully constructed worst-case inputs. This is a stronger requirement than NP-hardness, which only guarantees that some instances are hard.
The importance of OWFs stems from a remarkable theoretical result: one-way functions are both necessary and sufficient for private-key cryptography. If OWFs exist, you can build pseudorandom generators (Hastad-Impagliazzo-Levin-Luby), pseudorandom functions (Goldreich-Goldwasser-Micali), message authentication codes, CPA-secure symmetric encryption, commitment schemes, and even digital signatures (Rompel). Conversely, if OWFs do not exist, none of these primitives can exist — every function can be efficiently inverted, so secret keys can be recovered from public information. OWFs are the minimal assumption: prove they exist and you get all of symmetric cryptography; prove they don't exist and computational cryptography is impossible.
Candidate OWFs abound but none are proven. Integer multiplication (easy to compute p * q, believed hard to factor), modular exponentiation (easy to compute gx mod p, believed hard to compute discrete logarithms), and subset sum (easy to add selected numbers, believed hard to find which were selected) are all candidates. Proving that any of these is one-way would effectively resolve the P vs NP question — specifically, it would show that NP is not contained in BPP, which is a major open problem in complexity theory. This is why OWF existence remains a conjecture despite decades of effort: we believe these functions are one-way because the smartest mathematicians and computer scientists have tried and failed to invert them, but belief is not proof.
The gap between OWFs and public-key cryptography is significant. OWFs suffice for private-key (symmetric) primitives but are not known to imply public-key encryption or key exchange. Public-key schemes require trapdoor one-way functions (functions that are hard to invert in general but easy to invert with a secret trapdoor) or specific algebraic structure (like the group structure in Diffie-Hellman). Whether OWFs imply public-key encryption is a major open question — it is possible that a world exists where private-key cryptography works but public-key cryptography is impossible. This hierarchy of assumptions — OWFs for symmetric crypto, trapdoor OWFs or CDH/DDH/LWE for public-key crypto — is the structural backbone of the field.