Math Conjectures

Existence of One-Way Functions

OPENLandmarkOpen problemProposed 1976 · Standard version

Canonical statement

Does there exist a polynomial-time computable, length-preserving function family fn:{0,1}n→{0,1}nf_n:\{0,1\}^n\to\{0,1\}^n such that, for every probabilistic polynomial-time algorithm AA that outputs an nn-bit string (or failure), and every polynomial pp, for all sufficiently large nn,
Pr⁡x←{0,1}n, A[ fn(A(1n,fn(x)))=fn(x) ]<1p(n)? \Pr_{x\leftarrow\{0,1\}^n,\ A} [\,f_n(A(1^n,f_n(x)))=f_n(x)\,]<\frac1{p(n)}?
View source LaTeX
Does there exist a polynomial-time computable,
length-preserving function family
\(f_n:\{0,1\}^n\to\{0,1\}^n\) such that, for every probabilistic
polynomial-time algorithm \(A\) that outputs an \(n\)-bit string (or
failure), and every polynomial \(p\), for all
sufficiently large \(n\),
\[
  \Pr_{x\leftarrow\{0,1\}^n,\ A}
    [\,f_n(A(1^n,f_n(x)))=f_n(x)\,]<\frac1{p(n)}?
\]
TCS-013:[DiffieHellman1976][ImpagliazzoLuby1989][Goldreich2001Crypto]
Theoretical computer scienceInformation theory

Notes

The problem asks whether one-way functions exist: polynomial-time computable, length-preserving functions fn:{0,1}n→{0,1}nf_n:\{0,1\}^n\to\{0,1\}^n that no probabilistic polynomial-time algorithm can invert on a random input, except with probability smaller than any inverse polynomial. The question dates to 1976, when Diffie and Hellman placed such computationally asymmetric primitives at the foundation of their new approach to cryptography [DiffieHellman1976].

One-way functions are the minimal assumption of complexity-based cryptography: Impagliazzo and Luby showed they are essential for it [ImpagliazzoLuby1989], and the standard cryptographic toolbox can be built from them, as developed systematically by Goldreich [Goldreich2001Crypto]. Many candidate constructions, notably number-theoretic ones, are widely believed to be one-way, but each rests on an unproven hardness assumption; an unconditional construction would in particular imply P≠NPP\ne NP.

The problem is open in both directions: no unconditional one-way function is known, while a proof that none exists would collapse much of complexity-based cryptography.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.