Universal one-way function

A universal one-way function is an explicit polynomial-time computable function that is one-way if any one-way function exists — Lev85; the direct product of polynomially many independent copies of below is one — Lev85, Gol01. It is unrelated to universal one-way hash functions.

Construction

Fix a universal machine and an encoding of machines in which every string encodes a machine and every machine has encodings of every sufficiently large length. For and , let

where is the output of the machine encoded by on input if completes its simulation within steps, and otherwise. is computable in polynomial time — Gol01.

Universality

If a one-way function exists, then is weakly one-way, and the direct product of polynomially many independent copies of it is one-way (Weak OWF ⇒ OWF) — Lev85, Gol01. Conversely, if that direct product is one-way, a one-way function exists, so the existence of one-way functions is equivalent to the one-wayness of one explicit function.

Padding turns a one-way function into a one-way function , with polynomial in , whose simulation by finishes within steps on inputs of length — standard. For every large , some string of length encodes the machine computing , and with probability . A preimage of under has the form with . If an efficient inverted with probability at least for infinitely many , it would invert conditioned on , and hence , with probability at least for those . So every efficient inverter fails with probability more than for all large — Gol01.

Notes

  • The hardness of lies on the fraction of inputs whose first component encodes a one-way function, so the one-wayness of the amplified function reduces to that of an unspecified one-way function, with polynomial losses in input length, running time and success probability from padding, the weight of and Yao’s amplification — standard.