Paper 2026/1305

SUF-CMA SQISign via Canonical Response Encoding

Abstract

SQIsign is the only isogeny-based digital signature scheme under consideration in NIST's post-quantum standardization process. All published security results, including the first complete proof, establish only existential unforgeability under chosen-message attack (EUF-CMA). It is known informally that SQIsign does not achieve strong unforgeability (SUF-CMA) due to the non-uniqueness of its two-dimensional isogeny representation. We make three contributions. First, we identify a concrete malleability vector in the SQIsign v2.0 specification: the basis change matrix $M_{\mathrm{chl}}$ in the signature can be negated modulo $2^N$ to produce a distinct valid signature for the same public key and message. This is the direct structural analog of ECDSA's $(r, s)$ versus $(r, n - s)$ malleability. We provide a proof-of-concept against the C reference implementation at all three NIST security levels. Second, we propose a minimal fix: canonical matrix encoding, where the signer normalizes $M_{\mathrm{chl}}$ and the verifier rejects non-canonical forms. We prove that after canonicalization, the response encoding is information-theoretically injective on each fixed product surface (for generic $j$-invariants outside $\{0, 1728\}$), and computationally unique across surfaces under an explicit hardness assumption, using the structure of reducible gluings of abelian varieties. Third, we prove that the modified scheme achieves SUF-CMA in the quantum random oracle model under the hardness of the One Endomorphism problem with hints (the core assumption of the existing EUF-CMA proof, which additionally invokes hint indistinguishability) together with an explicit commitment-compatible auxiliary isogeny assumption: the sigma protocol's honest-verifier zero-knowledge and special soundness together with computationally unique responses (established by our encoding injectivity result) imply SUF-CMA via the KLS18 framework.

Note: Rewrote the CUR proof (Section 5.2). Case 2 now has two explicit sub-cases: 2a extracts a non-scalar endomorphism of E_A via the Kani component claw (tight reduction to OneEnd, Page-Wesolowski); 2b introduces and analyzes a commitment-compatible auxiliary isogeny assumption (Assumption 5.7). The bespoke CAIP assumption from v1 is removed. Response isogeny notation corrected to sigma: E_com -> E_chl throughout (Remark 2.7). Diamond equation updated. Automorphism exclusion now covers all four curves (E_A, E_aux, E_com, E_chl) with explicit SUF-CMA game justification. ROM/QROM mismatch in the UF-NMA term fixed via DFM20. Sub-case 2a non-scalarity algebra tightened. QROM remark expanded (KLS18 Definition 2.7, DFM20 Theorem 22, Barbosa et al. gap fix). Frobenius conjugate vector addressed (SEC-10). Gluing lemmas re-anchored to Kani 1997 and SQIsign2D-West Theorem 4. Added references: PW24, EHLMP18, DFM20, LZ19, BBD+23, BKM+24.