Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications.
Eran Gat, Shafi Goldwasser · Electronic colloquium on computational complexity · 2011
In this paper we introduce a new type of probabilistic search algorithm, which we call the Bellagio algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time, and to produce a correct and unique solution with high probability. We argue the applicability of such algorithms for the problems of verifying delegated computation in a distributed setting, and for generating cryptographic public-parameters and keys in distributed settings. We exhibit several examples of Bellagio algorithms for problems for which no deterministic polynomial time algorithms are known. In particular,we show such algorithms for: • finding a unique generator for Zp when p is a prime of the form kq + 1 for q is prime and k = polylog(p). The algorithm runs in expected polynomial in log p time. • finding a unique q’th non-residues of Zp for any prime divisor q of p − 1, extending Lenstra’s [11] algorithm for finding unique quadratic non-residue of Zp. The algorithm runs in expected polynomial time in log p and q. The tool we use is a new variant of the Adleman-Manders-Miller probabilistic algorithm for taking q-th roots, which outputs a unique solution to the input equations and runs in expected polynomial time in log p and q. • given a multi-variate polynomial P 6= 0, find a unique (with high probability) ~a such that P (~a) 6= 0. Alternatively you may think of this as producing a unique polynomial time verifiable certificate of inequality of polynomials. More generally, we show a necessary and sufficient condition for the existence of a Bellagio Algorithm for relation R: R has a Bellagio algorithm if and only if it is deterministically reducible to some decision problem in BPP. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 136 (2011)