2008 | OriginalPaper | Buchkapitel
Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
verfasst von : Chris Peikert, Vinod Vaikuntanathan
Erschienen in: Advances in Cryptology – CRYPTO 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 problems that are 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 cryptographically important lattice problems.
We also construct an
NISZK
proof for a special kind of disjunction (i.e., OR gate) related to the shortest vector problem. This may serve as a useful tool in potential constructions of noninteractive (computational) zero knowledge proofs for
NP
based on lattice assumptions.