**Authors:** Daniele Micciancio and Salil Vadhan

Advances in Cryptology - Crypto 2003. Santa Barbara, CA, USA, August 2003. LNCS 2729, Springer, pp. 282-298.

[DOI:10.1007/b11817]**Abstract:** We construct several new statistical
zero-knowledge proofs with *efficient provers*, i.e. ones where the
prover strategy runs in probabilistic polynomial time given an NP witness for
the input string. Our first proof systems are for approximate versions of the
Shortest Vector Problem (SVP) and Closest Vector Problem (CVP), where the
witness is simply a short vector in the lattice or a lattice vector close to
the target, respectively. Our proof systems are in fact proofs of knowledge,
and as a result, we immediately obtain efficient lattice-based identification
schemes which can be implemented with arbitrary families of lattices in which
the approximate SVP or CVP are hard.

We then turn to the general question of whether *all* problems in
SZK intersection NP admit statistical zero-knowledge proofs with efficient
provers. Towards this end, we give a statistical zero-knowledge proof system
with an efficient prover for a natural restriction of Statistica Difference,
a complete problem for SZK. We also suggest a plausible approach to resolving
the general question in the positive.