Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general (Q6104329)

The authors present a much-improved practical protocol, based on the hardness of Module-SIS and Module-LWE problems, for proving knowledge of a short vector $\vec{s}$ satisfying $A\vec{s} =t \bmod q$. The currently most efficient technique for constructing such a proof works by showing that the $l_\infty$ norm of $\vec{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 CRT(m) = \vec{t}\bmod q$ and (2) in the case that they want to prove that the $l_\infty$-norm is at most 1, the polynomial product $(m - 1).m. (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_\infty$-norm somewhat hinders the efficiency of this approach. In this work, the authors show that there is a more direct and more efficient way to prove that the coefficients of $\vec{s}$ have a small $l_2$ norm which does not require an equivocation with the $l_\infty$ norm, nor any conversion to the CRT representation. They observe that the inner product between two vectors $\vec{r}$ and $\vec{s}$ can be made to appear as a coefficient of a product (or sum of products) between polynomials which are functions of $\vec{r}$ and $\vec{s}$. Thus, using a polynomial product proof system and hiding all but one coefficient, they 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$. Their 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, they instantiate a verifiable encryption scheme and a group signature scheme which are more than twice as compact as the previously best solutions. For the entire collection see [Zbl 1514.94002].