Paper 2022/458

Multilinear Schwartz-Zippel mod N with Applications to Succinct Arguments

Abstract

We show that for $\mathbf{x}\gets [0,2^\lambda)^\mu$ and any integer $N$ the probability that $f(\mathbf{x})\equiv 0 \bmod N$ for any non-zero multilinear polynomial $f\in \mathbb{Z}[X_1, \dots,X_\mu]$, co-prime to $N$ is inversely proportional to $N$. As a corollary we show that if $\log_2 N\geq \log_2(2\mu)\lambda+8\mu^2 $ then the probability is bounded by $\frac{\mu+1}{2^\lambda}$. We also give tighter numerically derived bounds, showing that if $\log_2 N\geq {418}$, and $\mu\leq 20$ the probability is bounded by $\frac{\mu}{2^\lambda}+2^{-120}$. We then apply this Multilinear Composite Schwartz-Zippel Lemma (LCSZ) to resolve an open problem in the literature on succinct arguments: that the Bulletproofs protocol for linear relations over classical Pedersen commitments in prime-order groups remains knowledge sound when generalized to commitment schemes that are binding only over short integer vectors. In particular, this means that the Bulletproofs protocol can be instantiated with plausibly post-quantum commitments from lattice hardness assumptions (SIS/R-SIS/M-SIS). It can also be instantiated with commitments based on groups of unknown order (GUOs), in which case the verification time becomes logarithmic instead of linear time. Prior work on lattice-based Bulletproofs (Crypto 2020) and its extensions required modifying the protocol to sample challenges from special sets of polynomial size. This results in a non-negligible knowledge error, necessitating parallel repetition to amplify soundness, which impacts efficiency and poses issues for the Fiat-Shamir transform. Our analysis shows knowledge soundness for the original Bulletproofs protocol with the exponential-size integer challenge set $[0,2^\lambda]$ and thus achieves a negligible soundness error without repetition, circumventing a previous impossibility result (Crypto 2021). Our analysis also closes a critical gap in the original security proof of DARK, a GUO-based polynomial commitment scheme (Eurocrypt 2020). Along the way to achieving our result we also define Almost Special Soundness (AMSS), a generalization of Special-Soundness. Our main result is divided into two parts: (1) that the Bulletproofs protocol over generalized commitments is AMSS, and (2) that AMSS implies knowledge soundness. This framework serves to simplify the application of our analytical techniques to protocols beyond Bulletproofs in the future.

Note: This is a significant update that adds the applications to zero-knowledge proofs. It includes contents and super-seeds the result from https://eprint.iacr.org/2019/1229