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 currently 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 \cdot \ CRT(\bold{m}) \ = \ {^ ⃗_t} \ mod \ q} $ and (2) in the case that we want to prove that the $ {ℓ_8} $ norm is at most 1, the polynomial product $ \bold {(m - 1) \cdot \ m \cdot(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 $ ℓ{_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 $ \mathbb{Z} $ instead of $ \mathbb{Z}_q. $ Our protocols for proving short norms work over all (interesting) polynomial rings, but are particularly efficient for rings like $ \mathbb{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.