Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General.

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) over right arrow satisfying A (s) over right arrow - (t) over right arrowt mod q. The currently mostefficient technique for constructing such a proof works by showing that the l(infinity) norm of (s) over right arrow is small. It creates a commitment to a polynomial vector m whose CRT coefficients are the coefficients of (s) over right arrow and then shows that (1) A center dot CRT(m) " t (t) over right arrow mod q and (2) in the case that we want to prove that the l(infinity) norm is at most 1, the polynomial product (m - 1) center dot m center dot (m + 1) equals to 0. While these schemes are already quite practical, the requirement of using the CRT embedding and only being naturally adapted to proving the l(infinity)-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) over right arrow have a small l(2) norm which does not require an equivocation with the l(infinity) norm, nor any conversion to the CRT representation. We observe that the inner product between two vectors (r) over right arrow and (s) over right arrow can be made to appear as a coefficient of a product (or sum of products) between polynomials which are functions of (r) over right arrow and (s) over right arrow. 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 (or of a vector with itself) modulo q. Using a cheap, "approximate range proof", one can then lift the proof to be over Z instead of Zq. Our protocols for proving short norms work over all (interesting) polynomial rings, but are particularly efficient for rings like 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.