Random self-reducibility

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.

Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.

Definition

If for a function f evaluating any instance x can be reduced in polynomial time to the evaluation of f on one or more random instances y i , then it is self-reducible (this is also known as a non-adaptive uniform self-reduction). In a random self-reduction, an arbitrary worst-case instance x in the domain of f is mapped to a random set of instances y 1 , ..., y k . This is done so that f(x) can be computed in polynomial time, given the coin-toss sequence from the mapping, x, and f(y 1 ), ..., f(y k ).

Therefore, taking the average with respect to the induced distribution on y i , the average-case complexity of f is the same (within polynomial factors) as the worst-case randomized complexity of f. One special case of note is when each random instance y i is distributed uniformly over the entire set of elements in the domain of f that have a length of |x|. In this case f is as hard on average as it is in the worst case. This approach contains two key restrictions. First the generation of y 1 , ..., y k is performed non-adaptively.

This means that y 2 is picked before f(y 1 ) is known. Second, it is not necessary that the points y 1 , ..., y k be uniformly distributed.

Application in cryptographic protocols

Problems that require some privacy in the data (typically cryptographic problems) can use randomization to ensure that privacy. In fact, the only provably secure cryptographic system (the one-time pad) has its security relying totally on the randomness of the key data supplied to the system. The field of cryptography utilizes the fact that certain number-theoretic functions are randomly self-reducible. This includes probabilistic encryption and cryptographically strong pseudorandom number generation. Also, instance-hiding schemes (where a weak private device uses a strong public device without revealing its data) are easily exemplified by random self-reductions.

Examples

The discrete logarithm problem, the quadratic residuosity problem, the RSA inversion problem, and the problem of computing the permanent of a matrix are each random self-reducible problems. Theorem: Given a cyclic group G of size |G|. If a deterministic polynomial time algorithm A computes the discrete logarithm for a 1/poly(n) fraction of all inputs (where n = log |G| is the input size), then there is a randomized polynomial time algorithm for discrete logarithm for all inputs. Given a generator g of a cyclic group G = { g i | 0 ≤ i k .

Take B to be distributed uniformly on {0,...,|G| − 1}, then xg B = g k+B is also distributed uniformly on G. Therefore xg B is independent of x, and its logarithm can be computed with probability 1/poly(n) in polynomial time. Then log g x ≡ log g xg B - B (mod |G|) and the discrete logarithm is self-reducible. 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.

Consequences

If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to Σ 3 . If a CoNP-hard problem is random self-reducible in O(log n/n) then Σ 2 = Π 2 .

References

M. Abadi, J. Feigenbaum, and J. Kilian, On Hiding Information from an Oracle, J. Comput. Syst. Sci., 1989 S. Arora, Around the PCP Theorem, 1996 J. Feigenbaum, L. Fortnow, On the Random-self-reducibility of Complete Sets, 1991

Text derived from https://en.wikipedia.org/w/index.php?oldid=1287704500 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001287704500 · captured 1745787047.0 · version history

Cite this page as: encyclopegia.org, “Random self-reducibility”, snapshot enwiki-001287704500. https://encyclopegia.org/a/random-self-reducibility

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.