Probabilistic Search Algorithms and their Cryptographic Applications

by Eran Gat and Shafi Goldwasser

Oded's comments

This paper initiates the study of probabilistic (polynomial-time) search algorithms that with high probability output the same solution. That is, for a fixed relation $R$, such algorithm (called Bellagio) associate a "canonical" solution (denoted $s(x)$) with any instance $x$ (which has a solution) such that $prob[Bellagio(x)=s(x)]>2/3$. Of course, such an algorithm is of interest only when no deterministic (polynomial-time) search algorithms are known.

The paper shows several such examples as well as establishes the a necessary and sufficient condition for such algorithms: A relation $R$ has a Bellagio-algorithm iff finding solutions wrt $R$ is deterministically reducible to some BPP set.

The first direction is proved by using the reduction as an algorithm, while providing answers to its queries via a BPP algorithm (of sufficiently low error probability). For the opposite direction, suppose that $A$ is a Bellagio-algorithm for $R$, and consider the set $S$ s.t. $(x,i,b)\in S$ iff $\prob[A(x)_i=b] > 2/3$. Then, (i) $S$ is a BPP set, and (ii) finding solutions wrt $R$ is deterministically reducible to $S$.

In contrast to this fact, in my work in the world of P=BPP, it is showed that a natural class of "BPP search problems" is deterministically reducible to "promise BPP". Thus, the difference between standard problems in BPP and promise problems in BPP seems crucial. Indeed, using a deterministic reduction of search to a promise problem in BPP does not seem to yield a Bellagio-algorithm; the problem is that queries that violate the promise may yield arbitrary answers, which may possibly lead the search to different solutions...

The original abstract

See ECCC TR11-136.

Back to list of Oded's choices.