Paper 2026/1337

Elliptic Extraction and Pushable Hints for Higher-Dimensional SQIsign

Abstract

Higher-dimensional SQIsign variants use product and Kani-style isogeny representations to make response isogenies compact, checkable, or compatible with non-smooth degrees. These representations raise a foundations question: do they introduce genuinely higher-dimensional hardness, or do they preserve elliptic extraction while moving the additional assumptions into simulation? This paper gives a proof-theoretic separation between these two layers. We identify a recoverability condition under which an accepted higher-dimensional response publicly induces an elliptic Hom element; under the usual challenge-separation hypotheses, special soundness then extracts an elliptic \OneEnd witness. The remaining higher-dimensional assumptions are simulation assumptions, and we formulate them as non-interactive hint distributions. The separation yields two concrete theorem packages. First, SQIsign2D--West admits an exact Fiat--Shamir-with-hints EUF-CMA theorem: the security loss is expressed through a simulation-hint \OneEnd assumption, the statistical simulator loss, the challenge-space term, and the commitment min-entropy term; a pushable uniform-hint corollary gives the EndRing-compatible interpretation under a named hint-indistinguishability assumption. Second, for SQIPrime2D we do not claim a proof for the published auxiliary sampler. We define and analyze \(\mathsf{SQIPrime2D\text{-}UAux}\), a foundations variant that replaces the published Algorithm-context AIO layer by a context-independent uniform auxiliary hint distribution. UAux is an ideal proof-model distribution unless an efficient represented sampler is separately supplied; an approximate sampler instantiates the theorems with an explicit additive sampling loss. For this SQIPrime2D-UAux foundations variant, UAux gives a context-independent and exactly pushable replacement for the auxiliary AIO layer. We then introduce challenge-carrying uniform hints that additionally reveal the non-smooth challenge isogeny, the residual response isogeny, and the UAux auxiliary isogeny. These hints are stronger than ordinary SQIPrime auxiliary information, but they are fully pushable through the smooth self-reduction isogenies used in EndRing-style reductions. Consequently SQIPrime2D-UAux admits a fully pushable EndRing-compatible challenge-carrying hint layer, with a q-HintDist assumption separating simulation-shaped hints from the pushable distribution. None of these SQIPrime-side statements is a claim of plain EndRing security or a claim that the published SQIPrime2D AIO sampler itself is pushable.