Welcome to the resource topic for 2020/1449
Title:
More Efficient Amortization of Exact Zero-Knowledge Proofs for LWE
Authors: Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, 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.
ePrint: https://eprint.iacr.org/2020/1449
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .