TY - GEN
T1 - Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments
AU - Bünz, Benedikt
AU - Fisch, Ben
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2023.
PY - 2023
Y1 - 2023
N2 - We show that for x←$[0,2λ)μ and any integer N the probability that f(x)≡0modN for any non-zero multilinear polynomial f∈ Z[ X1, ⋯, Xμ], co-prime to N is inversely proportional to N. As a corollary we show that if log 2N≥ log 2(2 μ) λ+ 8 μ2 then the probability is bounded by μ+12λ. We also give tighter numerically derived bounds, showing that if log 2N≥ 418, and μ≤ 20 the probability is bounded by μ2λ+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. 1 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 λ] 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(1 This paper incorporates content published in the updated EPRINT of DARK [18]. The full version of this paper containing proofs is available online [17].).
AB - We show that for x←$[0,2λ)μ and any integer N the probability that f(x)≡0modN for any non-zero multilinear polynomial f∈ Z[ X1, ⋯, Xμ], co-prime to N is inversely proportional to N. As a corollary we show that if log 2N≥ log 2(2 μ) λ+ 8 μ2 then the probability is bounded by μ+12λ. We also give tighter numerically derived bounds, showing that if log 2N≥ 418, and μ≤ 20 the probability is bounded by μ2λ+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. 1 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 λ] 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(1 This paper incorporates content published in the updated EPRINT of DARK [18]. The full version of this paper containing proofs is available online [17].).
UR - http://www.scopus.com/inward/record.url?scp=85178660972&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85178660972&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-48621-0_14
DO - 10.1007/978-3-031-48621-0_14
M3 - Conference contribution
AN - SCOPUS:85178660972
SN - 9783031486203
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 394
EP - 423
BT - Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings
A2 - Rothblum, Guy
A2 - Wee, Hoeteck
PB - Springer Science and Business Media Deutschland GmbH
T2 - 21st International conference on Theory of Cryptography Conference, TCC 2023
Y2 - 29 November 2023 through 2 December 2023
ER -