Daniele Micciancio and Salil Vadhan
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
Shorttest 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 intersect 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 Statistical Difference, a complete problem for SZK. We also suggest a plausible approach to resolving the general question in the positive.