Welcome to the resource topic for 2022/284
Title:
Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General
Authors: Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plancon
Abstract:We present a much-improved practical protocol, based on the hardness of Module-SIS and Module-LWE problems, for proving knowledge of a short vector s satisfying As=t\bmod q. The currently most-efficient technique for constructing such a proof works by showing that the \ell_\infty norm of s is small. It creates a commitment to a polynomial vector m whose CRT coefficients are the coefficients of s and then shows that (1) A\cdot \mathsf{CRT}(m)=t\bmod\,q and (2) in the case that we want to prove that the \ell_\infty norm is at most 1, the polynomial product (m - 1)\cdot m\cdot(m+1) equals to 0. While these schemes are already quite good for practical applications, the requirement of using the CRT embedding and only being naturally adapted to proving the \ell_\infty-norm, somewhat hinders the efficiency of this approach. In this work, we show that there is a more direct and more efficient way to prove that the coefficients of s have a small \ell_2 norm which does not require an equivocation with the \ell_\infty norm, nor any conversion to the CRT representation. We observe that the inner product between two vectors r and s can be made to appear as a coefficient of a product (or sum of products) between polynomials which are functions of r and s. Thus, by using a polynomial product proof system and hiding all but one coefficient, we are able to prove knowledge of the inner product of two vectors modulo q. Using a cheap, approximate range proof, one can then lift the proof to be over \mathbb{Z} instead of \mathbb{Z}_q. Our protocols for proving short norms work over all (interesting) polynomial rings, but are particularly efficient for rings like \mathbb{Z}[X]/(X^n+1) in which the function relating the inner product of vectors and polynomial products happens to be a ``nice’’ automorphism. The new proof system can be plugged into constructions of various lattice-based privacy primitives in a black-box manner. As examples, we instantiate a verifiable encryption scheme and a group signature scheme which are more than twice as compact as the previously best solutions.
ePrint: https://eprint.iacr.org/2022/284
Talk: https://www.youtube.com/watch?v=2uVsVYtedVQ
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/262/slides.pdf
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 .