You are looking at a specific version 20201119:094126 of this paper. See the latest version.

Paper 2020/1449

More Efficient Amortization of Exact Zero-Knowledge Proofs for LWE

Jonathan Bootle and Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler

Abstract

We propose a practical zero-knowledge proof system for proving knowledge of short solutions s, e to linear relations A s + e= u mod q which gives the most efficient solution for two naturally-occurring classes of problems. The first is when A is very ``tall'', which corresponds to a large number of LWE instances that use the same secret s. In this case, we show that the proof size is independent of the height of the matrix (and thus the length of the error vector e) and rather only linearly depends on the length of s. The second case is when A is of the form A' tensor I, which corresponds to proving many LWE instances (with different secrets) that use the same samples A'. The length of this second proof is square root in the length of s, which corresponds to square root of the length of all the secrets. Our constructions combine recent advances in ``purely'' lattice-based zero-knowledge proofs with the Reed-Solomon proximity testing ideas present in some generic zero-knowledge proof systems -- with the main difference is that the latter are applied directly to the lattice instances without going through intermediate problems.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
LatticesZero-Knowledge ProofsLWEAmortization
Contact author(s)
jbt @ zurich ibm com
vad @ zurich ibm com
nkn @ zurich ibm com
gseiler @ inf ethz ch
History
2021-08-20: last of 2 revisions
2020-11-19: received
See all versions
Short URL
https://ia.cr/2020/1449
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.