Does every family of expanding quadratic integer polynomials admit an efficient distinguisher?
Barak–Hopkins–Jain–Kothari–Sahai’s Hypothesis 1 for weak pseudorandom generators computed by degree-two maps
Motivation
A line of candidate constructions of indistinguishability obfuscation (iO) bootstraps from a cryptographic multilinear map, LWE, and a low-degree expanding generator over the integers. After Lin–Tessaro’s block-wise local candidate was broken by the degree-two sum-of-squares relaxation, three follow-up candidates (Ananth–Jain–Sahai, Agrawal, Lin–Matt) retreated to a much weaker requirement: publish \(m \ge n^{1+\varepsilon}\) quadratic polynomials in \(n\) variables, evaluate them at one secret input, and ask only that the output be indistinguishable from itself plus small independent integer noise — nothing needs to look uniform, and the input need not be recoverable even in principle.
The question this hub tracks is whether that retreat helps at all: is there any choice of quadratic polynomials and any bounded input distribution, at this stretch, that survives every efficient distinguisher? If the answer is no — as the source paper conjectures — every degree-two route to iO via this template is dead, and the obstruction is now a statement about the algorithmic limits of semidefinite programming on planted rank-one problems, independent of cryptography. If the answer is yes, the construction is exactly the missing ingredient for iO from bilinear maps plus LWE.
Provenance and history
Posed as Hypothesis 1 in Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai, Sum-of-Squares Meets Program Obfuscation, Revisited, IACR Cryptology ePrint Archive, Report 2018/1237 (PDF p. 4): “We consider the following general hypothesis that, if true, would rule out not just the three proposed approaches based on quadratic polynomials for obtaining iO, but also a great many potential generalizations of them.”
The paper proves its own hypothesis only in a restricted special case (Theorem 2, PDF p. 5): when the polynomials are drawn independently and identically from a nice distribution — supported on homogeneous (no linear term) degree-two polynomials, normalised to unit coefficient variance, with pairwise-independent coefficients — a polynomial-time sum-of-squares/trace-norm algorithm recovers the secret input exactly with probability \(1 - n^{-\log n}\) from \(m \ge n(\log n)^{O(1)}\) samples. That covers random dense and random sparse polynomials and so breaks the Ananth–Jain–Sahai and Agrawal candidates outright, and the paper reports (without proof) experiments breaking the Lin–Matt candidate too, stating plainly: “we do not know of any degree-2 construction that does not fall prey to a variant of the same attack” (PDF p. 3). The general hypothesis — arbitrary, possibly correlated polynomials and an arbitrary bounded input distribution — is left open, and the paper is candid that this is only partial evidence: “As these are some of the most natural approaches to refute Hypothesis 1, our work can be seen as providing some (partial) evidence to its veracity” (PDF p. 5).
A companion open question from the same paper — whether the modified semidefinite program the authors use experimentally against the blockwise-random (Lin–Matt) candidate can be turned into a proof of exact recovery — is tracked separately at p/blockwise-random-quadratic-recovery; the two questions are independent. That one asks for a proof against one specific candidate; this one asks whether any efficient distinguisher can possibly fail against any candidate of this shape.
Parameter lattice
Only one statement occupies this hub. The hypothesis is a single implication over four independent parameters (\(n\), \(m\), \(\varepsilon\), \(\Lambda\)) rather than a family varying along a small number of discrete axes, so a lattice table would mostly restate the statement’s own quantifiers. The one genuine dichotomy the source paper itself draws is:
| axis | values | tracked here |
|---|---|---|
| polynomial family | i.i.d. draws from a nice distribution (settled, Theorem 2); arbitrary / adversarially correlated polynomials | arbitrary polynomials (c/0044) — the nice i.i.d. case is a proved special case, not itself conjectural |
Statements in this hub
- No Expanding Weak Quadratic Pseudorandom Generators — open: whether every family of quadratic \(\Lambda(n)\)-bounded polynomials at stretch \(m \ge n^{1+\varepsilon}\) admits an efficient distinguisher from the same family perturbed by bounded independent noise; settled only in the i.i.d.-nice special case.