Practical Lattice-Based Zero-Knowledge Proof Systems

This PhD thesis is about practical lattice-based zero-knowledge proof systems. We construct protocols based on computational lattice assumptions that allow to commit to arbitrary vectors s over a finite field, and prove linear and product relations between the vector coefficients, while achieving proof sizes and implementation characteristics that are competitive to non-lattice (PCP-type) proof systems. Firstly, we use the linear-size BDLOP commitment scheme (SCN 2018) based on Module-SIS and Module-LWE that allows to commit to a vector of polynomials over a cyclotomic polynomial ring such as ZZq[X]/(X^128+1), where the modulus q splits so that the ring is isomorphic to a product of copies of low-degree extensions of the prime field ZZq via the Number Theoretic Transform (NTT). Then we encode s as the vector of polynomials whose NTT basis representations make up s. We give a new opening proof for this commitment scheme that can be extended to prove probabilistic non-linear relations on the polynomials representing s, and that also supports the action by Galois automorphisms of the cyclotomic ring. Our opening proof does not require invertible challenge differences that were used in all previous proofs for BDLOP. Then, we make use of the new opening proof to construct protocols for proving product and linear relations such as for example s(1 - s) = 0 and As = u. The combination of these three protocols -- opening proof, product proof, and linear proof -- gives a general linear-size proof system. Secondly, we construct a sublinear-size proof system that scales with the square root of the length of s. We use the previous linear-size proof system as a building-block. As the commitment scheme we use a standard compressing commitment scheme based on Module-SIS only. At the heart of the sublinear-size proof system lies an interactive version of the Schwartz-Zippel lemma that is useful for arguing about multivariate polynomial equations in a way that only needs a linear number of garbage coefficients in the number of variables. This interactive Schwartz-Zippel lemma also requires a linear number of rounds in the number of variables. The linear-size proof system is used to prove the Schwartz-Zippel equation and the use of BDLOP as the underlying commitment schemes makes it possible to commit to individual garbage coefficients at a time with little cost. The concrete cost of our sublinear-size proof system is further reduced by extending it to prove Merkle hash-trees by induction over the levels of the tree. The special algebraic structure related to the NTT and Galois automorphisms is crucial for the construction of our protocols. We also study the implication of this structure for high-speed implementations of our proof systems and lattice-based cryptography in general. We present techniques for record-breaking vectorized implementations that are by now adopted in all finalist and alternate structured lattice-based candidates in the NIST PQC standardization effort. Our linear-size proof system beats PCP-type systems in terms of proof sizes for small statements as for example proving a Ring-LWE sample with ternary noise in dimension 1024, where it achieves a proof size of about 50 Kilobytes. Proving such statements is useful in privacy preserving protocols. At the same time our proof system is more than ten thousand times faster than for example the PCP-type Aurora proof system (Eurocrypt 2019). Our sublinear-size square-root proof system beats the Ligero PCP-type system (CCS 2017) in proof size for the application of proving rank-1 constraint satisfaction with more than one million constraints. Ligero also exhibits square root scaling. Unlike other approaches, all our protocols achieve negligible soundness error directly and we do not boost the soundness of an underlying protocol by simple repetition