Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments

Benedikt Bünz, Ben Fisch

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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[ 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].).

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 21st International Conference, TCC 2023, Proceedings
EditorsGuy Rothblum, Hoeteck Wee
PublisherSpringer Science and Business Media Deutschland GmbH
Pages394-423
Number of pages30
ISBN (Print)9783031486203
DOIs
StatePublished - 2023
Event21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China
Duration: Nov 29 2023Dec 2 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14371 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International conference on Theory of Cryptography Conference, TCC 2023
Country/TerritoryTaiwan, Province of China
CityTaipei
Period11/29/2312/2/23

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments'. Together they form a unique fingerprint.

Cite this