Aristeidis Tentes

Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems

Chris Peikert and Vinod Vaikuntanathan (Proc. of Crypto 2008)

We construct noninteractive statistical zero-knowledge (NISZK) proof
systems for a variety of standard approximation problems on lattices,
such as the shortest independent vectors problem and the complement of
the shortest vector problem. Prior proof systems for lattice problems
were either interactive or leaked knowledge (or both).

Our systems are the first known NISZK proofs for any cryptographically
useful problem not related to integer factorization. In addition, they
are proofs of knowledge, have reasonable complexity, and generally admit
efficient prover algorithms (given appropriate auxiliary input). In some
cases, they even imply the first known interactive statistical
zero-knowledge proofs for certain lattice problems.

As an additional contribution, we construct an NISZK proof for a special
language representing a disjunction (OR) of two or more variables. This
may be useful for potential constructions of noninteractive
(computational) zero knowledge proofs for NP based on lattice  assumptions.