Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR11-136 | 20th October 2011 00:00

#### Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications

Revision #1
Authors: eran gat , shafi goldwasser
Accepted on: 20th October 2011 00:00
Keywords:

Abstract:

In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it 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:
\begin{itemize}
\item finding a unique generator
for \Z\ 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.
\item finding a
unique $q$'th non-residues of \Z\ for any prime divisor $q$ of $p-1$,
extending Lenstra's \cite{L} algorithm for finding unique quadratic non-residue of \Z.
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$.
\item given a multi-variate polynomial $P\neq 0$, find a unique (with high probability) $\vec{a}$ such that
$P(\vec{a})\neq0$. Alternatively you may think of this as producing a unique polynomial time
verifiable certificate of inequality of polynomials.
\end{itemize}

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.

### Paper:

TR11-136 | 12th October 2011 22:10

#### Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications

TR11-136
Authors: eran gat , shafi goldwasser
Publication: 12th October 2011 22:32
Keywords:

Abstract:

In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it 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:
\begin{itemize}
\item finding a unique generator
for \Z\ 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.
\item finding a
unique $q$'th non-residues of \Z\ for any prime divisor $q$ of $p-1$,
extending Lenstra's \cite{L} algorithm for finding unique quadratic non-residue of \Z.
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$.
\item given a multi-variate polynomial $P\neq 0$, find a unique (with high probability) $\vec{a}$ such that
$P(\vec{a})\neq0$. Alternatively you may think of this as producing a unique polynomial time
verifiable certificate of inequality of polynomials.
\end{itemize}

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 | Imprint