onewayness

Onewayness is a property of a function in which evaluation is easy but inversion is hard. A function f is one-way if computing f(x) from x can be done efficiently, but given a value y = f(x), recovering any x with f(x) = y is computationally infeasible for all but negligible probability.

Formally, one speaks of a family of functions {f_s} parameterized by a security parameter s. There exists a polynomial-time algorithm to compute f_s(x) for any x, but for every polynomial-time inverter A, the probability that A(y) outputs a valid preimage x with f_s(x) = y (where y = f_s(x) for random x) is negligible in s. When such a family exists, it is called a family of one-way functions.

In cryptography, one-wayness underpins many secure constructions. Classic informal examples include modular exponentiation modulo a composite n = pq: computing y = x^e mod n is easy, while recovering x from y without knowing the factorization of n is believed hard. More generally, one-wayness is the basis for preimage resistance in cryptographic hash functions: given a hash value, finding a corresponding input is intended to be computationally infeasible.

Limitations and status: the unconditional existence of one-way functions remains unproven; it is a central assumption in complexity theory and cryptography. If one-way functions exist, they enable a wide range of primitives, including pseudorandom generators, digital signatures, and secure encryption. Variants include strong one-wayness and one-way permutations, which impose additional requirements such as invertibility being hard even when given the output.