Paper 2022/458
Multilinear SchwartzZippel 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 nonzero multilinear polynomial $f\in \mathbb{Z}[X_1, \dots,X_\mu]$, coprime 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 SchwartzZippel 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 primeorder 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 postquantum commitments from lattice hardness assumptions (SIS/RSIS/MSIS). 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 latticebased Bulletproofs (Crypto 2020) and its extensions required modifying the protocol to sample challenges from special sets of polynomial size. This results in a nonnegligible knowledge error, necessitating parallel repetition to amplify soundness, which impacts efficiency and poses issues for the FiatShamir transform. Our analysis shows knowledge soundness for the original Bulletproofs protocol with the exponentialsize 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 GUObased polynomial commitment scheme (Eurocrypt 2020). Along the way to achieving our result we also define Almost Special Soundness (AMSS), a generalization of SpecialSoundness. 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 zeroknowledge proofs. It includes contents and superseeds the result from https://eprint.iacr.org/2019/1229
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in TCC 2023
 Keywords
 SchwartzZippelZeroKnowledgeLatticesRSA
 Contact author(s)

bb @ nyu edu
ben fisch @ yale edu  History
 20230927: last of 4 revisions
 20220412: received
 See all versions
 Short URL
 https://ia.cr/2022/458
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/458, author = {Benedikt Bünz and Ben Fisch}, title = {Multilinear SchwartzZippel mod N with Applications to Succinct Arguments}, howpublished = {Cryptology ePrint Archive, Paper 2022/458}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/458}}, url = {https://eprint.iacr.org/2022/458} }