ECCC-Report TR05-093https://eccc.weizmann.ac.il/report/2005/093Comments and Revisions published for TR05-093en-usWed, 24 Aug 2005 10:42:14 +0300
Paper TR05-093
| Concurrent Zero Knowledge without Complexity Assumptions |
Daniele Micciancio,
Shien Jin Ong,
Amit Sahai,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2005/093We 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).
Wed, 24 Aug 2005 10:42:14 +0300https://eccc.weizmann.ac.il/report/2005/093