# Concurrent Zero Knowledge without
Complexity Assumptions

Daniele Micciancio, Shien Jin Ong, Amit Sahai, and Salil Vadhan

### Abstract

We provide *unconditional* constructions of *concurrent*
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
(coNP forms of the) Shortest Vector Problem and
Closest Vector Problem in lattices.

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 NP witness) and have Õ(log n) rounds, which is known to be essentially optimal
for black-box simulation.

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

### Versions

*Electronic Colloquium on
Computational Complexity (ECCC), *Technical Report TR05-093. August
2005. [postscript][pdf][ECCC
page]
- In
*Proceedings of the
Third Theory of Cryptography Conference (TCC `06), *volume 3876 of
Lecture Notes in Computer Science, pages 1-20. Springer-Verlag, 4-7 March 2006. [postscript][pdf][Springer page]

[ back to Salil Vadhan's research]