Paper 2020/1449
More Efficient Amortization of Exact ZeroKnowledge Proofs for LWE
Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler
Abstract
We propose a practical zeroknowledge 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 naturallyoccurring 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'' latticebased zeroknowledge proofs with the ReedSolomon proximity testing ideas present in some generic zeroknowledge 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)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Major revision. ESORICS 2021
 Keywords
 LatticesZeroKnowledge ProofsLWEAmortization
 Contact author(s)

jbt @ zurich ibm com
vad @ zurich ibm com
nkn @ zurich ibm com
gseiler @ inf ethz ch  History
 20210820: last of 2 revisions
 20201119: received
 See all versions
 Short URL
 https://ia.cr/2020/1449
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1449, author = {Jonathan Bootle and Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler}, title = {More Efficient Amortization of Exact ZeroKnowledge Proofs for {LWE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1449}, year = {2020}, url = {https://eprint.iacr.org/2020/1449} }