Random self-reducibility
A problem is random self-reducible if every instance can be solved by an efficient algorithm that queries a solver only on instances each distributed independently of the original instance, typically uniformly over instances of the same size. For a decision problem, the query distribution may instead depend on the instance only through its answer: one distribution for yes-instances and one for no-instances. For a reduction making one query, an algorithm that succeeds on a noticeable fraction of instances then succeeds, with repetition and a way to check answers, on every instance with overwhelming probability; for one making queries and correct whenever all answers are, an algorithm failing on at most a fraction of each query distribution suffices, by a union bound and a majority vote; in the decision form it must fail on at most a fraction of each of the two distributions. Either way average-case and worst-case hardness coincide over the query distribution, or over each of the two in the decision form (for the examples below, within a fixed group, modulus or matrix ) — standard. FF93 give a formal treatment, with non-adaptive reductions whose query distributions depend only on the length of the input.
Examples
- Discrete logarithm. In a cyclic group of known order , an instance maps to the uniform instance for , and a logarithm of it gives ; answers are checked by exponentiation, so a solver correct on an fraction of the group gives one correct on every instance after an expected queries — standard.
- RSA. An instance maps to for , a uniform instance, and an -th root of it divided by gives — standard.
- Computational Diffie–Hellman. maps to for with the order of , whose answer yields after dividing by . Answers cannot be checked without a DDH oracle, but a CDH solver correct on a noticeable fraction of instances can still be turned into one correct on every instance with overwhelming probability — Sho97.
- Decisional Diffie–Hellman. In a group of prime order, a tuple can be mapped to a uniform Diffie–Hellman tuple when and to a uniform tuple otherwise, and from one tuple to any number of independent such tuples, so DDH is as hard for many instances as for one — NR97. This is an instance of the decision form, up to the probability, one over the group order, that a uniform tuple is a Diffie–Hellman tuple.
- Quadratic residuosity. For of Jacobi symbol modulo for distinct odd primes , the element for is uniform among residues if is a residue and uniform among non-residues with Jacobi symbol otherwise, an instance of the decision form — standard. For a Blum integer , where is a non-residue of Jacobi symbol , the query with is uniform on the elements of Jacobi symbol whatever is, and its residuosity XOR gives that of , so quadratic residuosity modulo a Blum integer is random self-reducible with query distribution independent of the instance — standard.
- LWE. Samples map to for a uniform , so a worst-case secret reduces to a uniform one — standard. SIS has a worst-case to average-case reduction from lattice problems — Ajt96 — and LWE a quantum one — Reg05; in both the worst case is over lattices, not secrets.
Limits for NP-complete problems
If an -complete language is non-adaptively random self-reducible, then and the polynomial hierarchy collapses to its third level — FF93. More generally, a non-adaptive reduction from deciding an -complete language in the worst case to deciding some language on average over a polynomial-time samplable distribution has the same consequence (No non-adaptive reduction from NP to average-case NP hardness) — BT03.