TR05-093 Authors: Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

Publication: 24th August 2005 10:42

Downloads: 2719

Keywords:

We provide <i>unconditional</i> constructions of <i>concurrent</i>

statistical zero-knowledge proofs for a variety of non-trivial

problems (not known to have probabilistic polynomial-time

algorithms). The problems include Graph Isomorphism, Graph

Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a

restricted version of Statistical Difference, and approximate

versions of the (<b>coNP</b> forms of the) Shortest Vector Problem

and Closest Vector Problem in lattices.<br>

For some of the problems, such as Graph Isomorphism and Quadratic

Residuosity, the proof systems have provers that can be implemented

in polynomial time (given an <b>NP</b> witness) and have Õ(log

<i>n</i>) rounds, which is known to be essentially optimal for

black-box simulation.<br>

To our best of knowledge, these are the first constructions of

concurrent zero-knowledge protocols in the asynchronous model

(without timing assumptions) that do not require complexity

assumptions (such as the existence of one-way functions).