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