## 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.