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 A*s = t mod q. The currently most-efficient technique for constructing such a proof works by showing that the L_\infty norm of sis small using CRT slots technique (Esgin et al., Asiacrypt 2020). In this work, we show that there is a more direct and more efficient way to prove that s has a small L_2 norm which does not require an equivocation with the L_\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 with coefficient vectors r and s. Thus, by using a polynomial product proof system and hiding all but one coefficient, we can 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.

The talk is based on the following work: [LNP22] Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plançon, 'Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General', CRYPTO, 2022.

About the speaker