The Uber Assumption and its Random Self-Reducibility

in Non-Bilinear and Type 1, 2, 3 Bilinear Groups

generic-group-model

pairings

random-self-reducibility

uber-assumption

Author

Pooya Farshim, with Claude (Anthropic)

Published

August 16, 2026

Statement: AI-written, not yet formalized. Proof: AI draft, not yet independently reviewed, not yet formalized.

This is a working draft, published early on purpose. The mathematics is not finished and the paper is under active revision. It is on the site so that its claims are addressable and checkable while that happens, not because it is done. See Open obligations.

View PDF · Download LaTeX source

The note fixes notation for prime-order groups without a pairing and for bilinear groups in each of the three Galbraith-Paterson-Smart types, defines the Uber assumption uniformly across all four settings, and asks in each which instances are random self-reducible.

The organizing idea

One lemma isolates, per setting, the space \(\mathcal{L}_\gamma\) of exponents a reduction can realize in each group. Writing \(R, S, T\) for the source tuples in \(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T\), the four settings differ in exactly one place, the products the pairing can form:

setting	\(\mathcal{L}_T\) products available
non-bilinear	none (no pairing)
Type 1	\(R \cdot R\)
Type 2	\((R \cup S) \cdot S\)
Type 3	\(R \cdot S\) only

One theorem then does the work in all four. If there is a subgroup \(\mathcal{T} \le \mathrm{AGL}_n(\mathbb{Z}_p)\) of affine reparametrizations \(\tau\) under which (C1) the source exponents stay computable, (C2) the challenge transforms covariantly, \(f \circ \tau = \lambda_\tau f + h_\tau\) with \(h_\tau\) computable, and (C3) \(\tau(\mathbf{x})\) is uniform, then the problem is random self-reducible with exact advantage transfer, using one oracle call.

The two results the draft turns on

Proposition (monomial targets never separate)

If the source tuples are monomials and the challenge is a monomial \(f = X_1^i X_2^j\) with \(i, j \ge 1\), the diagonal torus \((x_1, x_2) \mapsto (a x_1, d x_2)\) satisfies (C1) and (C2) in every one of the four settings, with defect \(h_\tau = 0\) identically. So no monomial target can separate two settings, and a separating target must be non-monomial and must defeat the torus.

Proposition (a Type-2 versus Type-3 separation)

For \(p \ge 5\), with \(R = (1, X_1)\), \(S = (1, X_2)\), \(T = (1)\) and \[ f = X_1^2 + X_1X_2^2 + X_2^3 \] in \(\mathbb{G}_T\): the assumption is generically hard in both Type 2 and Type 3. In Type 2 the admissible reparametrizations act uniformly on \(\mathbb{Z}_p^2\) and the theorem applies with exact advantage transfer. In Type 3 the admissible group collapses to \(\mathcal{T}_3 = \{(x_1, x_2) \mapsto (x_1 - 3c,\ x_2 + c)\} \cong (\mathbb{Z}_p, +)\), whose orbits are the \(p\) lines \(x_1 + 3x_2 = k\), and on no such line is \(f\) computable from the instance. The affine reduction therefore fails at every worst-case point.

The failure is as large as it can be, and not by accident: the set of \(\tau\) satisfying (C1) and (C2) is a group, so the failure locus is a union of orbits, and the failure fraction is either \(O(1/p)\) or exactly \(1\), with nothing in between.

The separation’s algebra was re-derived symbolically during this run and agrees with the paper at every coefficient. Under \(\tau_1 = aX_1 + c_1\), \(\tau_2 = dX_2 + c_2\) the monomials of \(f \circ \tau\) outside \(\mathcal{L}_T = \langle 1, X_1, X_2, X_1X_2 \rangle\) carry coefficients

\[ [X_1^2] = a^2, \qquad [X_1X_2^2] = ad^2, \qquad [X_2^3] = d^3, \qquad [X_2^2] = d^2(c_1 + 3c_2), \]

so covariance forces \(a^2 = ad^2 = d^3 = \lambda_\tau\), hence \(a = d = 1\), and then \(c_1 = -3c_2\). That leaves the one-parameter group \(\mathcal{T}_3\), and \(x_1 + 3x_2\) is invariant under it. Restricted to an orbit \(x_1 = k - 3s\),

\[ f|_{\ell_k} = -2s^3 + (k+9)s^2 - 6ks + k^2, \qquad \mathcal{L}_T|_{\ell_k} = \langle 1, s, s^2 \rangle, \]

and \(s^3\) is independent of \(1, s, s^2\) as a function on \(\mathbb{Z}_p\) exactly when \(p > 3\). The hypothesis \(p \ge 5\) is therefore tight, not cosmetic: at \(p = 3\) Fermat gives \(s^3 = s\) and the escape clause reopens on every orbit.

In Type 2, \(\psi\) puts \(X_2^2\) into \(\mathcal{L}_T\) and \(X_2\) into \(\mathcal{L}_1\). The first removes the constraint tying \(c_1\) to \(c_2\); the second lets \(\tau_1\) carry a shear term \(a_{12}X_2\). The surviving conditions give \(a_{11} = d^2\) and \(a_{12} = d^2 - d\) with \(c_1, c_2\) free, so the action is uniform on all of \(\mathbb{Z}_p^2\).

What the separation does and does not rule out

It rules out the single-reparametrization technique, which is the tool behind every positive result in the note. It does not rule out every reduction: Lipton’s multi-query line interpolation still solves the computational problem for this target, though only against a high-advantage solver and never the decisional problem. The gap is therefore a gap for decisional reductions and for reductions that must work at negligible advantage. Ruling out every decisional reduction would need a lower-bound argument such as a meta-reduction, which the note does not attempt.

Not formalized. No Lean artifact exists for this paper, and none is planned before the mathematics is finished.

Open obligations

Finish the mathematics. The paper is a working draft under active revision; the last several commits were substantive mathematics, not write-up. This is the blocking item and it is the author’s.
Independent human review. reviewers is empty and proof_review is ai. The separation’s coefficient algebra has been machine-checked, but that is not a review of the argument.
Decide whether statement_informal should be human. It is ai because the draft was AI co-authored and an AI does not mark its own work human; the author may raise it.
Reconcile the paper’s 39 em-dashes with the repository style rule (“No em-dashes in prose”, CONTRIBUTING.md), which prompts/revise.md also enforces as a hard invariant.

Checks run

Recorded here rather than in a commit message, so that what has and has not been checked is visible on the page itself.

Bibliography, 16 August 2026. All seventeen entries verified against their sources: author list, title, venue, volume, page range and year each confirmed, including the two the paper leans on hardest — Galbraith, Paterson and Smart, “Pairings for Cryptographers”, Discrete Applied Mathematics 156(16):3113–3121, 2008, for the type classification, and Boyen, “The Uber-Assumption Family – A Unified Complexity Framework for Bilinear Groups”, Pairing 2008, LNCS 5209, pp. 39–56, for the Uber baseline. No entry was fabricated, misdated or misattributed. The preliminary-version notes on Blum–Luby–Rubinfeld (STOC 1990), Regev (STOC 2005) and Escala et al. (Journal of Cryptology 30(1), 2017) also check out.
chktex and lacheck, 16 August 2026. Both silent. The three typographic items previously listed here are fixed: intersentence spacing after “co-CDH” (line 482), a non-breaking space before a \ref (line 668), and the \Span definition (line 22, suppressed inline as a math-mode no-op). Two spaces before a period inside display math were tidied at the same time. A .chktexrc beside the source pins the four suppressed warnings, each documented with why it is a false positive on this file, so the run is reproducible rather than a one-off.
Still outstanding: the four prompts this paper is meant to be put through – prompts/proof.md (the idealized-model audit; the paper lives in the generic-group model), prompts/style.md, prompts/latex.md and prompts/revise.md – have not been run. The mathematics is unreviewed either way; see the obligations above.