**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.

**Category / Keywords: **public-key cryptography / Lattices, Zero-Knowledge Proofs, LWE, Amortization

**Date: **received 17 Nov 2020

**Contact author: **jbt at zurich ibm com, vad@zurich ibm com, nkn@zurich ibm com, gseiler@inf ethz ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20201119:094126 (All versions of this report)

**Short URL: **ia.cr/2020/1449

[ Cryptology ePrint archive ]