Welcome to the resource topic for 2022/458
Title:
Schwartz-Zippel for multilinear polynomials mod N
Authors: Benedikt Bünz, Ben Fisch
Abstract:We derive a tight upper bound on the probability over \mathbf{x}=(x_1,\dots,x_\mu) \in \mathbb{Z}^\mu uniformly distributed in [0,m)^\mu that f(\mathbf{x}) = 0 \bmod N for any \mu-linear polynomial f \in \mathbb{Z}[X_1,\dots,X_\mu] co-prime to N. We show that for N=\prod_{i=1}^\ell p_i^{r_i} this probability is bounded by \frac{\mu}{m} + \prod_{i=1}^\ell I_{\frac{1}{p_i}}(r_i,\mu) where I is the regularized beta function. Furthermore, we provide an inverse result that for any target parameter \lambda bounds the minimum size of N for which the probability that f(\mathbf{x}) \equiv 0 \bmod N is at most 2^{-\lambda} + \frac{\mu}{m}. For \mu =1 this is simply N \geq 2^\lambda. For \mu \geq 2, \log_2(N) \geq 8 \mu^{2}+ \log_2(2 \mu)\cdot \lambda the probability that f(\mathbf{x}) \equiv 0 \bmod N is bounded by 2^{-\lambda} +\frac{\mu}{m}. We also present a computational method that derives tighter bounds for specific values of \mu and \lambda. For example, our analysis shows that for \mu=20, \lambda = 120 (values typical in cryptography applications), and \log_2(N)\geq 416 the probability is bounded by 2^{-120}+\frac{20}{m}. We provide a table of computational bounds for a large set of \mu and \lambda values.
ePrint: https://eprint.iacr.org/2022/458
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .