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 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.
Ngoc Khanh Nguyen is a fourth-year PhD student at IBM Research Europe - Zurich and ETH Zurich, Switzerland, supervised by Dr Vadim Lyubashevsky and Prof. Dennis Hofheinz. Previously, Khanh obtained his B.Sc. and M.Eng. degrees in Mathematics and Computer Science at the University of Bristol, UK.