Paper 2022/284

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

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=tmodq$. The currently most-efficient technique for constructing such a proof works by showing that the ${\ell }_{\mathrm{\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)=tmodq$ and (2) in the case that we want to prove that the ${\ell }_{\mathrm{\infty }}$ norm is at most $$, the polynomial product $$ equals to $$. 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 $$-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 $$ have a small $$ norm which does not require an equivocation with the $$ norm, nor any conversion to the CRT representation. We observe that the inner product between two vectors $$ and $$ can be made to appear as a coefficient of a product (or sum of products) between polynomials which are functions of $$ and $$. 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 $$. Using a cheap, approximate range proof, one can then lift the proof to be over $$ instead of $$. Our protocols for proving short norms work over all (interesting) polynomial rings, but are particularly efficient for rings like $$ 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.