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 A⃗s “ ⃗ t mod q. The cur- rently most-efficient technique for constructing such a proof works by showing that the ℓ8 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 ̈ CRTpmq “ ⃗ t mod q and (2) in the case that we want to prove that the ℓ8 norm is at most 1, the polynomial product pm ́ 1q ̈ m ̈ pm ` 1q 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 ℓ8-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 have a small ℓ2 norm which does not require an equivocation with the ℓ8 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 which are functions of ⃗r and ⃗s . 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 ZrXs{pXn ` 1q 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