## Abstract

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[ X_{1}, ⋯, X_{μ}], co-prime to N is inversely proportional to N. As a corollary we show that if log _{2}N≥ log _{2}(2 μ) λ+ 8 μ^{2} then the probability is bounded by μ+12λ. We also give tighter numerically derived bounds, showing that if log _{2}N≥ 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].).

Original language | English (US) |
---|---|

Title of host publication | Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings |

Editors | Guy Rothblum, Hoeteck Wee |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 394-423 |

Number of pages | 30 |

ISBN (Print) | 9783031486203 |

DOIs | |

State | Published - 2023 |

Event | 21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China Duration: Nov 29 2023 → Dec 2 2023 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 14371 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 21st International conference on Theory of Cryptography Conference, TCC 2023 |
---|---|

Country/Territory | Taiwan, Province of China |

City | Taipei |

Period | 11/29/23 → 12/2/23 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science