Paper 2021/1415
A Note on the Pseudorandomness of LowDegree Polynomials over the Integers
Aayush Jain, Alexis Korb, Paul Lou, and Amit Sahai
Abstract
We initiate the study of a problem called the Polynomial Independence Distinguishing Problem (PIDP). The problem is parameterized by a set of polynomials $\mathcal{Q}=(q_1,\ldots, q_m)$ where each $q_i:\mathbb{R}^n\rightarrow \mathbb{R}$ and an input distribution $\mathcal{D}$ over the reals. The goal of the problem is to distinguish a tuple of the form $\{ q_i,q_i(\mathbf{x})\}_{i\in [m]} $ from $\{ q_i,q_i(\mathbf{x}_i)\}_{i\in [m]} $ where $\mathbf{x}, \mathbf{x}_1,\ldots , \mathbf{x}_m$ are each sampled independently from the distribution $\mathcal{D}^n$. Refutation and search versions of this problem are conjectured to be hard in general for polynomial time algorithms (Feige, STOC 02) and are also subject to known theoretical lower bounds for various hierarchies (such as SumofSquares and SheraliAdams). Nevertheless, we show polynomial time distinguishers for the problem in several scenarios, including settings where such lower bounds apply to the search or refutation versions of the problem. Our results apply to the setting when each polynomial is a constant degree multilinear polynomial. We show that this natural problem admits polynomial time distinguishing algorithms for the following scenarios: Nontrivial Distinguishers: We define a nontrivial distinguisher to be an algorithm that runs in time $n^{O(1)}$ and distinguishes between the two distributions with probability at least $n^{O(1)}$. We show that such nontrivial distinguishers exist for large classes of worstcase families of polynomials, and essentially any nontrivial input distribution that is symmetric around zero, and isn't equivalent to a distribution over Boolean values. In particular, we show that when $m\geq n$ and the sets of indices corresponding to the variables present in each monomial exhibit a weak expansion property with expansion factor greater than $1/2$ for unions of at most $4$ sets, then a nontrivial distinguisher exists. Overwhelming Distinguishers: Next we consider the problem of amplifying the success probability of the distinguisher, to guarantee that it succeeds with probability $1n^{\omega(1)}$. We obtain such an overwhelming distinguisher for natural random classes of homogeneous multilinear constant degree $d$ polynomials, denoted by $\mathcal{Q}_{n,d,p}$, and natural input distributions $\mathcal{D}$ such as discrete Gaussians or uniform distributions over bounded intervals. The polynomials are chosen by independently sampling each coefficient to be $0$ with probability $p$ and uniformly from $\cD$ otherwise. For these polynomials, we show a surprisingly simple distinguisher that requires $p> n\log n/\binom{n}{d}$ and $m\geq \tilde{O}(n^{2})$ samples, independent of the degree $d$. This is in contrast with the setting for refutation, where we have sumofsquares lower bounds against constant degree sumofsquares algorithms (Grigoriev, TCS 01; Schoenebeck, FOCS 08) for this parameter regime for degree $d>6$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 pseudorandomnessindistinguishability obfuscation
 Contact author(s)

aayushjain1728 @ gmail com
alexiskorb @ cs ucla edu
pslou @ cs ucla edu
sahai @ cs ucla edu  History
 20211024: received
 Short URL
 https://ia.cr/2021/1415
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1415, author = {Aayush Jain and Alexis Korb and Paul Lou and Amit Sahai}, title = {A Note on the Pseudorandomness of LowDegree Polynomials over the Integers}, howpublished = {Cryptology ePrint Archive, Paper 2021/1415}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1415}}, url = {https://eprint.iacr.org/2021/1415} }