Lattice-Based Zero-Knowledge Proofs Under a Few Dozen Kilobytes

In preparation for the eventual arrival of quantum computers, there has been a significant amount of work to construct quantum-safe cryptographic primitives, as evidenced by the ongoing NIST PQC Standardization. To ensure post-quantum security, the underlying public-key schemes have to be built based on quantum-safe computational hardness assumptions. In this regard, lattice-based primitives appear to be a leading choice. Indeed, the currently most efficient, in terms of size and speed, quantum-safe basic primitives (e.g. signatures and encryption schemes) are based on the hardness of lattice problems with algebraic structure such as Module-SIS and Module-LWE. As a natural next step, lattice-based cryptography can be thus applied to build more advanced primitives such as zero-knowledge arguments. In this thesis, we present $\mathsf{Lantern}$, a new lattice-based zero-knowledge protocol with short proofs based on the hardness of Module-SIS and Module-LWE problems. In particular, our framework is suitable for proving lattice-related statements, e.g. proving knowledge of a short vector $\vec s$ satisfying $A\vec s=\vec t\bmod q$. At the core of our constructions lies a more direct and more efficient way to prove that $\vec s$ has a small Euclidean norm which, unlike in prior works, does not require proving explicitly that each coefficient of $\vec s$ is small, nor any conversion to the CRT representation. Instead, we use the observation that the inner product $\langle \vec{r},\vec{s} \rangle$ between any two vectors $\vec r$ and $\vec s$ can be made to appear as a constant coefficient of a product (or sum of products) between polynomials which are functions of $\vec r$ and $\vec s$. Therefore, by using a polynomial product proof system and hiding all but the constant 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'', we can then lift the proof to be over $\mathbb{Z}$ instead of $\mathbb{Z}_q$. Performance-wise, our framework produces proofs of size $13$KB for basic statements which are $2-3$X smaller than prior works. Furthermore, the new proof system can be plugged into constructions of various lattice-based privacy-oriented primitives in a black-box manner. As examples, we instantiate a verifiable encryption scheme as well as ring and group signatures which are significantly more compact than previously the best solutions