No Expanding Weak Quadratic Pseudorandom Generators
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
View PDF · LaTeX source · Formal statement – not yet formalized
Several candidate constructions of indistinguishability obfuscation (iO) reduce security to a very weak kind of generator: publish a list of quadratic polynomials with small integer coefficients, evaluate all of them at one secret input drawn from some distribution, and require only that the resulting list of values be indistinguishable from that same list with small independent integer noise added to each entry. Nothing needs to look uniformly random, and the secret need not be recoverable even in principle. The paper’s Hypothesis 1 conjectures that this retreat does not help once the number of published polynomials exceeds the number of variables by any fixed polynomial factor.
Notation. \(n\) is the number of variables; \([m] := \{1, \dots, m\}\). A function \(\Lambda : \mathbb{N} \to \mathbb{N}\) is polynomially bounded if \(\Lambda(n) \le n^{O(1)}\). An \(n\)-variate polynomial \(q\) of total degree at most \(2\) is \(\Lambda\)-bounded if all its coefficients are integers in \([-\Lambda, +\Lambda]\); a distribution over \(\mathbb{Z}^n\) (or over \(\mathbb{Z}\)) is \(\Lambda\)-bounded if it is supported on \([-\Lambda, +\Lambda]^n\) (or \([-\Lambda, +\Lambda]\)). An algorithm is efficient if it is probabilistic and runs in time polynomial in the bit length of its input. For distributions \(D_1, D_2\), the advantage of an algorithm \(\mathcal{A}\) is \[ \mathrm{Adv}_{\mathcal{A}}(D_1, D_2) \;:=\; \Bigl| \Pr_{z \sim D_1}[\mathcal{A}(z) = 1] - \Pr_{z \sim D_2}[\mathcal{A}(z) = 1] \Bigr| . \]
Conjecture (no expanding weak quadratic generators). For every constant \(\varepsilon > 0\) and every polynomially bounded \(\Lambda : \mathbb{N} \to \mathbb{N}\) there is a constant \(c > 0\) such that the following holds for all sufficiently large \(n \in \mathbb{N}\).
Let \(m \ge n^{1+\varepsilon}\) be an integer, let \(q_1, \dots, q_m : \mathbb{R}^n \to \mathbb{R}\) be quadratic \(\Lambda(n)\)-bounded polynomials, let \(\mathcal{X}\) be a \(\Lambda(n)\)-bounded distribution over \(\mathbb{Z}^n\), and for each \(i \in [m]\) let \(\Delta_i\) be a \(\Lambda(n)\)-bounded distribution over \(\mathbb{Z}\) with \(\Pr[\Delta_i = z] < 0.9\) for every \(z \in \mathbb{Z}\). Define \[ D_1 := \bigl(q_1, \dots, q_m,\; q_1(x), \dots, q_m(x)\bigr), \qquad D_2 := \bigl(q_1, \dots, q_m,\; q_1(x) + \delta_1, \dots, q_m(x) + \delta_m\bigr), \] where \(x \sim \mathcal{X}\) in both, and in \(D_2\) the perturbations \(\delta_i \sim \Delta_i\) are independent of one another and of \(x\). Then there exists an efficient algorithm \(\mathcal{A}\) with \(\mathrm{Adv}_{\mathcal{A}}(D_1, D_2) \ge c\).
Note the quantifier order: \(c\) and the “for all sufficiently large \(n\)” are fixed first, but the instance (\(m\), the \(q_i\), \(\mathcal{X}\), the \(\Delta_i\)) is fixed before \(\mathcal{A}\) is chosen, so \(\mathcal{A}\) may depend on the whole instance; only the advantage \(c\) is required to be uniform. Equivalently: there is no family of quadratic \(\Lambda(n)\)-bounded polynomials, of stretch \(m \ge n^{1+\varepsilon}\), whose evaluations at a \(\Lambda(n)\)-bounded random input are computationally indistinguishable from those evaluations perturbed by bounded independent noise no one value of which is taken with probability \(0.9\) or more – the \(\Pr[\Delta_i = z] < 0.9\) clause is load-bearing here: drop it and \(\delta_i \equiv 0\) is a counterexample to the restatement, since then \(D_1 = D_2\) trivially.
What the paper settles. Its Theorem 2 proves the hypothesis in the restricted case where \(q_1, \dots, q_m\) are drawn independently and identically from a nice distribution: supported on homogeneous (no linear term) degree-two polynomials, with \(\|q\|_2^2 \le C \cdot \mathbb{E}\|q\|_2^2\) for a constant \(C\), with \(\mathrm{Var}(Q_{i,j}) = 1\), and with the coefficients \(Q_{i,j}\) pairwise independent – and where the input is uniform on a bounded box (or more generally centred sub-Gaussian). There, 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, which in particular distinguishes. This covers random dense and random sparse polynomials and so breaks the Ananth–Jain–Sahai and Agrawal candidates. The general hypothesis, with arbitrary (possibly correlated) polynomials and an arbitrary bounded input distribution, is open.
Sources
- Barak, Hopkins, Jain, Kothari, Sahai. Sum-of-Squares Meets Program Obfuscation, Revisited. IACR Cryptology ePrint Archive, Report 2018/1237, 2018. Hypothesis 1 is stated in Section 1.2 (PDF p. 4); Theorem 2 and the definition of a nice distribution are on PDF p. 5; the experimental attacks on all known degree-two candidates are in Section 6 (PDF pp. 14-18).
View PDF – no proof written yet · LaTeX source – no proof written yet · Formal proof – not yet formalized
Open. The paper proves only the i.i.d.-nice special case (its Theorem 2); the general hypothesis, over arbitrary and possibly adversarially correlated polynomials, has no known proof.
Why the natural route stalls. The obvious distinguisher – recover the secret input \(x\) from the evaluations – is not available in general: for adversarial polynomials it need not even be information-theoretically possible to recover \(x\), and where it is, doing so is an instance of the NP-hard problem of solving quadratic equations. The paper’s actual route, via low-rank recovery (writing a homogeneous quadratic as \(q_i(x) = \langle Q_i, xx^\top \rangle\) turns seed recovery into recovering a rank-one matrix from \(m\) linear measurements), goes through nuclear-norm minimisation guarantees that hold under matrix RIP or Gross’s incoherence condition. Both are randomness conditions on the measurement matrices, and need not hold once the polynomials are adversarially chosen – which is exactly what the general hypothesis allows. A proof would need either a recovery guarantee that survives adversarial measurements, or an entirely different route to a distinguisher that does not go through recovery at all.
Toward a negative answer. The authors report, but do not prove, that their attacks (or variants of them) break every degree-two candidate they are aware of, including Lin–Matt’s blockwise-random construction, which Theorem 2 does not cover directly. Turning that specific experimental success into a theorem is tracked as its own, narrower open question at p/blockwise-random-quadratic-recovery; resolving it would be evidence for, but not a proof of, the general hypothesis here.
Why it matters for iO. The hypothesis is the sharp form of a question that governed a whole line of candidate iO constructions: can iO be built from bilinear maps, LWE, and a “simple” low-degree generator? Lin–Tessaro’s block-wise-local candidate was killed by the degree-two sum-of-squares relaxation (Barak–Brakerski–Komargodski–Kothari; independently Lombardi–Vaikuntanathan). Ananth–Jain–Sahai, Agrawal, and Lin–Matt then retreated to the much weaker \(\Delta\)RG / pseudo-flawed-smudging requirement studied here. If Hypothesis 1 holds, every degree-two route of this shape is dead, and iO from bilinear maps would have to go through degree three or higher, or abandon the assumption that the published polynomials are independent of the secret. If it fails, the refutation is itself the missing ingredient for iO from bilinear maps – a genuine construction, not just a hardness argument.
A companion question, not a special case. The same paper’s experimental (but unproved) success against the Lin–Matt candidate is tracked separately at p/blockwise-random-quadratic-recovery (c/0045 once published). That question asks for a proof of recovery against one specific candidate; this one asks whether any efficient distinguisher can fail against any candidate of this general shape. They are independent: resolving the Lin–Matt case would not settle Hypothesis 1, and Hypothesis 1 failing would not by itself say anything about Lin–Matt’s specific construction.
What the hypothesis does not cover. It fixes the polynomials independently of the input distribution – the same \(q_1, \dots, q_m\) appear in both \(D_1\) and \(D_2\), uncorrelated with \(x\). It is plausible that later degree-two iO constructions sample public data jointly with the secret seed, so that the effective polynomials depend on the secret, which would place such constructions outside this quantification entirely rather than refuting it. This reading of the later literature has not been verified against a specific paper by this page – a candidate reference recalled from memory (Jain–Lin–Sahai, Indistinguishability Obfuscation from Well-Founded Assumptions, STOC 2021) is marked [UNVERIFIED] in the LaTeX source’s bibliography and should not be treated as confirmed. A reviewer should check both whether that citation is accurate and whether any construction in the post-2018 literature actually refutes, rather than merely evades, this hypothesis.
Checked against the literature, 2026-08-19. Searched for work since 2018 proving or refuting BHJKS’s Hypothesis 1 (the general, adversarial-polynomial case left open by Theorem 2): Ünal, Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality (eprint 2023/119), gives only subexponential-time attacks – not the polynomial-time distinguisher the conjecture requires – and does not mention BHJKS or Hypothesis 1; Algorithmic Thresholds for Refuting Random Polynomial Systems (arXiv 2110.08677) targets i.i.d.-random polynomials and refutation certificates, essentially an extension of the same “nice” case Theorem 2 already covers, not the adversarial setting at issue here. The page’s [UNVERIFIED] Jain–Lin–Sahai citation, Indistinguishability Obfuscation from Well-Founded Assumptions (arXiv 2008.09317), is confirmed to be a real paper, but it builds iO from a Boolean NC⁰ PRG rather than a quadratic weak PRG, so it bears on neither a proof nor a refutation of Hypothesis 1. Verdict: still open.