Reducing or separating $q$-type assumptions

Formal statement

Setting. CITED Pairing groups $(\mathbb G_1,\mathbb G_2,\mathbb G_T)$ of prime order $r$. [Boneh–Boyen 2008, §2]

$q$-SDH. CITED Given $g,g^x,g^{x^2},\ldots,g^{x^q}$, output $(c,g^{1/(x+c)})$ for some $c\in\mathbb Z_r$. [Boneh–Boyen 2008, §3.1]

Task. Either give a black-box reduction from $q$-SDH to a constant-size assumption (one whose instance size does not grow with $q$), or prove via meta-reduction that no such reduction exists.

Deliverables

1. A uniform-notation assumption catalogue.
2. An implication graph with cited edges and loss factors.
3. A written account of where an attempted constant-size-assumption reduction breaks.
4. A precisely scoped meta-reduction statement, proved or stated as a target.

Verified best-known table

Result	Verified statement	Primary reference
CITED $q$-SDH introduction	Short standard-model signatures are proved under inverse-form $q$-SDH.	Boneh–Boyen, EUROCRYPT 2004 / J. Cryptology 2008
CITED Generic hardness	The $q$-SDH family has generic-group lower bounds; this evidence is not a reduction to a static assumption.	Boneh–Boyen 2008
CITED Concrete attack	Supplied powers enable Cheon's divisor-dependent hidden-exponent recovery algorithms.	Cheon, EUROCRYPT 2006
CITED Historical meta-reduction	Coron's technique proves optimality/lower bounds for reductions of several signature schemes; it is not itself a $q$-SDH-to-static separation.	Coron, EUROCRYPT 2002
CITED Positive static reduction outside the setting	Déjà Q reduces $q$-SDH and broad $q$-type classes to static subgroup hiding in composite-order pairing groups.	Chase–Meiklejohn, EUROCRYPT 2014; Chase–Maller–Meiklejohn, ASIACRYPT 2016
CITED Prime-order meta-reduction	A fully black-box generic reduction from $q$-SDH to a true fixed-size prime-order assumption is impossible at the stated dimension thresholds.	Lu–Zhandry, CRYPTO 2024
CITED Scheme-level concrete follow-up	BBS+ and deterministic BBS security implies $\Theta(q)$-SDH, and matching usage-dependent attacks exist; later work gives a tight $q$-SDH proof for restricted-use BBS.	Chairattana-Apirom–Tessaro, ASIACRYPT 2025; Chairattana-Apirom–Hofheinz–Tessaro, EUROCRYPT 2026
CITED Label-model boundary	Random-representation and type-safe generic models require care when ordinary label computation is unbounded; efficient internal PRP substitutions do not preserve the full information-theoretic class.	Zhandry, CRYPTO 2022
CITED Structured-GGM lower bound	A partial public label operation yields a density-sensitive discrete-log lower bound, but not a $q$-SDH-to-static separation or a deterministic native-label budget.	Corrigan-Gibbs–Henzinger–Wu, EUROCRYPT 2026; A007
PROVED Representation-uniform corollary	A fully-black-box standard-oracle reduction guaranteed pointwise over every group representation implies GR-BB and is impossible at the same thresholds.	A003, using Lu–Zhandry Lemma 3.2 and Corollary 6.1
PROVED Limited-representation boundary	Random relabeling cannot extend the result to a guarantee for a class excluding random sparse implementations, including one named family or efficient-only families; the required representation quantifier and algebraic trace are absent.	A004
PROVED Bounded native-label separation	For one named concrete representation, a fully-black-box reduction that introduces at most $s_1$ unexplained labels in the $q$-SDH source is impossible under fixed-assumption hardness when $n_1+s_1<q-1$. For broader target-valued bilinear $q$-type games, a safe threshold is $\binom{n+s+2}{2}+t<q$.	A006, extending the trace dimension in Lu–Zhandry Theorems 5.2 and 5.10
PROVED Prefix relation-rank separation	For one named concrete representation, quotient all typed source-label logarithms by the affine relations efficiently available and verified at each adversary-call prefix. If the resulting dimension is $\kappa<q-1$, any fully-black-box $q$-SDH reduction yields a PPT attack on its fixed-size premise. Arbitrarily many affine-derived labels over $k$ native seeds cost only $k$ dimensions; target-valued bilinear games safely use $\binom{\kappa+2}{2}+\tau<q$.	A008, importing only the column-space root-list lemma of Lu–Zhandry and conditionally bridging to the factor-base relations of Corrigan-Gibbs–Henzinger–Wu

State in eight lines

PROVED The typed catalogue, loss-audited implication graph, and direct SXDH span obstruction are complete. CITED Lu--Zhandry rule out GR-BB/TS-BB reductions at the published dimension thresholds. PROVED A003 shows representation-uniform FBB implies GR-BB. PROVED A004/A005 isolate why relabeling and finite-seed encodings do not cover one named representation. PROVED A006 gives the raw fresh-label fixed-representation bound. PROVED A007 shows structured-label density alone does not control a transcript. PROVED A008 replaces label count by prefix affine relation rank and is now the main theorem. EMPIRICAL Exact finite-field fixtures and six unit tests validate the new bookkeeping.

Main theorem

PROVED Fix a concrete prime-order source group $G_*=\langle g\rangle$. At every prefix $\tau$, enumerate typed source-label logarithms $z=(z_1,\ldots,z_m)$ and collect only efficiently available relations $A_\tau z=b_\tau$ whose group identities are verified.

PROVED The prefix affine trace dimension is [ d(\tau)=m-\operatorname{rank}{\mathbb F_r}(A\tau). ] Gaussian elimination computes a particular solution and nullspace basis, so every label is a known affine function of $d(\tau)$ unknown parameters.

PROVED If a PPT fully-black-box fixed-representation reduction to $q$-SDH has $d(\tau)\le\kappa<q-1$ at every adversary-call prefix, its query matrix has at most $\kappa+1<q$ columns. Lu--Zhandry's root-list simulator then implements the selected perfect adversary in PPT, yielding an attack on the fixed-size premise with no additional success loss.

PROVED The maximum is prefix-sensitive. A late relation can lower current rank but cannot be applied to an earlier call. Equality branches, collisions, multiple calls, and rewinding are handled by online reparametrization and branch-local snapshots.

Corollaries

PROVED A006 is the empty-relation corollary $d\le n+s$.

PROVED If the challenge contributes $n$ coordinates, the native interface has $k$ raw seeds, and every other source label has a certified affine derivation row, then $d\le n+k$ regardless of total label count. Available factor-base exponent vectors give the same conditional structured-GGM bridge.

PROVED For target-valued bilinear games, the safe degree-two bound is $\binom{\kappa+2}{2}+\tau<q$. Typed source-valued $q$-SDH keeps $\kappa<q-1$.

Validation

EMPIRICAL: Python 3.13.4, NumPy 2.4.6, Windows, 2026-07-25 All 70 shared library baseline tests passed. All six P2.2 relation-rank tests passed.

EMPIRICAL The full $\mathbb F_{101}$ fixture has three challenge coordinates, two native seeds, and 24 derived labels. Dimension stays 5, a late raw label raises the prefix maximum to 6, its later relation restores current dimension 5, a collision row lowers it to 4, and the independent control has dimension 26.

CITED Primary proof bodies checked: Lu--Zhandry Lemmas 5.1/5.3 and Theorem 5.2; structured-GGM Definitions 2.2--2.4/4.3 and Theorem 4.2.

Residual gap

PROVED A surviving fully-black-box reduction must have a $q$-SDH-call prefix with $d(\tau)\ge q-1$, exploit nonlinear/unavailable native relations outside the certified affine trace, or leave the fully-black-box class.

PROVED Density, raw label count, random relabeling, and finite-seed substitution are not sufficient invariants.

EMPIRICAL A bounded primary-source search on 2026-07-25 found no paper stating the prefix relation-rank theorem. Treat this as candidate novelty, not an unconditional priority claim; a submission still needs a broader related- work review and external cryptographic proof review.

Next action

Pursue a bounded-degree nonlinear trace, a representation-specific upper bound forcing prefix rank below $q-1$, or an explicitly non-black-box construction.

Invariants

• Do not call the scoped theorem an unrestricted black-box impossibility.
• Use only relations whose coefficients are efficiently available and whose group identities are verified.
• Never lower an earlier call rank with a later relation.
• Do not equate structured-label density with relation rank.
• Do not transport composite-order Déjà Q to prime order.

Files that matter

attempts/A008-relation-rank-meta-reduction.md, code/relation_rank.py, code/audit_relation_rank.py, data/audit_relation_rank_p101_g24_s2208_20260725.json, NOTES.md, and papers/P2.2.typ.