Revision #1 Authors: eran gat , shafi goldwasser

Accepted on: 20th October 2011 00:00

Downloads: 2294

Keywords:

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.

TR11-136 Authors: eran gat , shafi goldwasser

Publication: 12th October 2011 22:32

Downloads: 3401

Keywords:

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.