One-way functions

Take a string of zeros and ones, 1011, and erase its last digit: the output is 101. Returning 1010 counts as reversing the rule, because it produces the same output; recovering the original string is unnecessary. This rule is easy to reverse. Do there exist easy forward rules that every efficient attacker using ordinary classical computation almost always fails to reverse on randomly chosen inputs? Efficient here allows running time bounded by a fixed power of input length; the attacker’s success must shrink rapidly as those strings grow.[2] [4]

Can a rule be easy to compute yet overwhelmingly difficult for every efficient classical attacker to reverse on uniformly sampled inputs? Efficient means running in time bounded by a fixed power of input length. The toy map erases an $n$-bit string's final bit, and appending 0 always reverses it. For the general target, choose $X$ uniformly among all $n$-bit strings and give the attacker $f(X)$ together with $n$. Any returned string $x'$ satisfying $f(x')=f(X)$ counts as success. The question asks for one classical polynomial-time computable function $f$ such that, for every probabilistic polynomial-time attacker and every constant $c>0$, this success probability is at most $n^{-c}$ for all sufficiently large $n$. The size after which the bound holds may depend on the attacker and $c$; the function must defeat them all.[2]

Losing information is not enough: appending 0 reverses the toy rule every time. A few exceptionally hard inputs are not enough either; the required protection concerns inputs sampled uniformly at each length. Proposed constructions depend on unproved assumptions, so the existence question remains open.[2] [3]

A worst-case lower bound can leave almost all sampled instances easy and therefore misses the inversion target. Liu and Pass prove an equivalence with average-case difficulty in finding the length of a shortest program that outputs a string within a specified polynomial time budget. That equivalence characterizes existence; it does not prove the needed hardness. The 2026 symmetry-of-information results concern particular randomized descriptions and parameter guarantees, which must likewise be kept separate from an unconditional one-way function.[2] [3]

A proven construction can turn any one-way function into a generator that expands a short random seed into a longer string that efficient classical tests cannot reliably distinguish from fresh random bits. Such generators support secret-key encryption: two parties sharing a secret can conceal a message from a computationally limited attacker. This establishes a foundation connecting security to limits on computation, rather than to passing a few familiar randomness tests.[2] [4]

A generator stretching a uniformly sampled $n$-bit seed to $2n$ bits can produce at most $2^n$ outputs, among $2^{2n}$ possible strings. Its output distribution therefore differs sharply from true uniform randomness. Pseudorandomness says that every polynomial-time classical test has only negligible advantage in detecting that difference. The general construction from any one-way function makes this gap between statistical information and accessible information useful for secret-key cryptography. Both the inverter and the distinguishing tests here are classical; resistance to quantum attackers is a separate requirement.[2] [4]