Paper 2026/1305

Auxiliary Isogeny Freedom in SQIsign's Two-Dimensional Representation

Abstract

SQIsign encodes its response isogeny via a two-dimensional representation on a product of elliptic curves, using the Kani construction. We analyze the algebraic structure of this encoding in detail, with a focus on the role of the auxiliary isogeny and its implications for strong unforgeability. We show that the anti-isometry $\psi$ determining the Kani kernel is publicly computable from the torsion-point images of the component and auxiliary isogenies alone, that the automorphism orbit $\{\psi, -\psi\}$ is the only torsion-level source of encoding non-uniqueness on a fixed product surface, and that every auxiliary of the correct degree is commitment-compatible by Kani's theorem. The sole barrier to producing an alternative encoding is the construction of a new auxiliary isogeny of the required (generically non-smooth) degree from the challenge curve. We demonstrate that this barrier falls whenever a single small prime divides the auxiliary degree $2^f - q$: the adversary reroutes the terminal $\ell$-isogeny step at the codomain of the honest auxiliary, preserving the total degree exactly. Since generic odd integers possess small prime factors with overwhelming probability, this establishes that canonicalization of the basis change matrix does not suffice for strong unforgeability. We analyze the signing algorithm's dependency structure to show that the auxiliary cannot be bound into the Fiat-Shamir hash without a protocol redesign, and conclude with a structural comparison of ECDSA (where canonicalization suffices), SQIsign (where it does not), and salt-PRISM (which achieves strong unforgeability via a salted hash-to-prime mechanism that eliminates the auxiliary freedom entirely).

Note: Changes in v5: Complete rewrite. Versions 1-4 attempted a SUF-CMA proof for canonicalized SQIsign; following an observation by De Feo (Section 6), the proof's barrier identification was incorrect. This version pivots to a technical note analyzing the auxiliary isogeny freedom: why canonicalization eliminates the sign ambiguity (Section 3) but does not suffice for strong unforgeability (Sections 4-6), and what structural property a scheme needs to close the gap (Section 8). The M vs -M finding and canonical encoding fix are unchanged from v1.