Paper 2022/284
LatticeBased ZeroKnowledge Proofs and Applications: Shorter, Simpler, and More General
Abstract
We present a muchimproved practical protocol, based on the hardness of ModuleSIS and ModuleLWE problems, for proving knowledge of a short vector $s$ satisfying $As=t\bmod q$. The currently mostefficient technique for constructing such a proof works by showing that the $\ell_\infty$ 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 \mathsf{CRT}(m)=t\bmod\,q$ and (2) in the case that we want to prove that the $\ell_\infty$ norm is at most $1$, the polynomial product $(m  1)\cdot m\cdot(m+1)$ equals to $0$. While these schemes are already quite good for practical applications, the requirement of using the CRT embedding and only being naturally adapted to proving the $\ell_\infty$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 $\ell_2$ norm which does not require an equivocation with the $\ell_\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 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 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 latticebased privacy primitives in a blackbox 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in CRYPTO 2022
 Keywords
 lattices latticebased zeroknowledge proofs
 Contact author(s)

vadim lyubash @ gmail com
nkn @ zurich ibm com
mpl @ zurich ibm com  History
 20220814: last of 4 revisions
 20220307: received
 See all versions
 Short URL
 https://ia.cr/2022/284
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/284, author = {Vadim Lyubashevsky and Ngoc Khanh Nguyen and Maxime Plancon}, title = {LatticeBased ZeroKnowledge Proofs and Applications: Shorter, Simpler, and More General}, howpublished = {Cryptology ePrint Archive, Paper 2022/284}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/284}}, url = {https://eprint.iacr.org/2022/284} }