Random Self-reducibility - Examples

Examples

• Discrete logarithm

Theorem: If a deterministic polynomial time algorithm A computes the discrete logarithm for a 1/poly(n) fraction of input y (n = |p|), then there is a randomized polynomial time algorithm for discrete logarithm for all inputs.

Given a generator g, and an x ∈ a cyclic group G, the discrete log of x to the base g is an integer k ({0 ≤ k < |G|}) and x = gk. Since the order of group G is known, and taking B to be distributed uniformly on {0, ..., p − 1} (where p = |G| is a prime), then xgB is also distributed uniformly on G. Likewise, gB is uniform in Z_p*, meaning it is impossible for it to be 0. Therefore xgB is independent of x, and log_gxgB ≡ B + log_gx (mod|G|) and the discrete logarithm is self-reducible.

• Permanent

Given the definition of the permanent of a matrix, it is clear that PERM(M) for any n-by-n matrix M is a multivariate polynomial of degree n over the entries in M. Calculating the permanent of a matrix is a difficult computational task—PERM has been shown to be #P-complete (proof). Moreover, the ability to compute PERM(M) for most matrices implies the existence of a random program that computes PERM(M) for all matrices. This demonstrates that PERM is random self-reducible. The discussion below considers the case where the matrix entries are drawn from a finite field F_p for some prime p, and where all arithmetic is performed in that field.

Let X be a random n-by-n matrix with entries from F_p. Since all the entries of any matrix M + kX are linear functions of k, by composing those linear functions with the degree n multivariate polynomial that calculates PERM(M) we get another degree n polynomial on k, which we will call p(k). Clearly, p(0) is equal to the permanent of M.

Suppose we know a program that computes the correct value of PERM(A) for most n-by-n matrices with entries from F_p---specifically, 1 − 1/(3n) of them. Then with probability of approximately two-thirds, we can calculate PERM(M + kX) for k = 1,2,...,n + 1. Once we have those n + 1 values, we can solve for the coefficients of p(k) using interpolation (remember that p(k) has degree n). Once we know p(k) exactly, we evaluate p(0), which is equal to PERM(M).

If we do so, we run the risk of being wrong 1/3 of the time, but by picking multiple random Xs and repeating the above procedure many times, and only providing the majority winner as an answer, we can drive the error rate down very low.

• Quadratic residuosity problem
• Inverse-RSA