Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings

Abstract

We propose a very fast lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution \(\vec {s} \in \{-1,0,1\}^n\) to a linear equation \(A\vec {s}=\vec {u}\) over \(\mathbb {Z}_q\), which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of 8.