The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

Giacomo Borin, Luca De Feo, Guido Lido, Sina Schaeffler · 2026

Read The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures by Giacomo Borin, Luca De Feo, Guido Lido, Sina Schaeffler (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09899.txt.

Introduction

Giacomo Borin and coauthors write a guide to using level structures to widen the SQIsign signature scheme. In their general frame, a signer must show an isogeny between public key and commitment that also maps one chosen level structure to another. They work the frame out with isogenies in one and two dimensions. Along the way they give an explicit Deuring correspondence for supersingular curves with level structure.

Catalog record

CREATORGiacomo Borin, Luca De Feo, Guido Lido, Sina Schaeffler
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE117639
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.09899

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures Giacomo Borin, Luca De Feo, Guido Lido, Sina Schaeffler Abstract We explore the use of level structures to generalize the SQIsign signature scheme. We give a general framework where, given the public key and the commitment, the challenge is to exhibit an isogeny between them with an additional requirement, namely to map a chosen level structure to another. We then instantiate the framework using 1-dimensional and 2-dimensional isogenies. In doing that we provide a new explicit Deuring correspondence for supersingular elliptic curves with level structures and solve new constrained norm equations. † † Author list in alphabetical order; see https://ams.org/profession/leaders/CultureStatement04.pdf. 1 Introduction Isogeny-based cryptography is a promising candidate for post-quantum cryptography, with several proposals for key exchange and digital signatures, but also for more advanced primitives such as threshold and ring signatures. A mainstay of isogeny-based cryptography is \mathrm{SQIsign} [ 23 ] , which is so far the most compact signature scheme participating in NIST’s post-quantum standardization process [ 36 ] . At its heart, it is based on the Deuring correspondence , a mathematical and algorithmic equivalence between supersingular curves and orders of a quaternion algebra. The original instantiation of \mathrm{SQIsign} constructs signatures by solving some quadratic equations in the quaternion algebra, using an algorithm known as KLPT [ 31 , 24 ] . This approach gives very compact signatures, with a relatively simple verification procedure, but a quite involved and slow signing procedure. It also presents an intrinsic difficulty in proving EUF-CMA security, owing to the limitations of KLPT. A paradigm shift for \mathrm{SQIsign} , first proposed in [ 21 ] and then improved [ 8 , 26 , 35 ] , came with the introduction of higher-dimensional (HD) isogenies . Building upon a line of work started with the SIDH attacks [ 15 , 34 , 40 ] , these techniques significantly sped up \mathrm{SQIsign} and improved its provable security. Taking a step back, level structures are bases of torsion subgroups of elliptic curves, up to transformation by a well chosen group of matrices. They have been used to prove indistinguishability of certain distributions on supersingular isogeny graphs [ 7 ] , and to classify hardness assumptions in isogeny-based cryptography [ 22 ] . However level structures are implicitly featured in many more isogeny-based protocols, for example in SIKE [ 30 ] or FESTA [ 10 ] . Even \mathrm{SQIsign} itself can be understood in terms of level structures. Indeed, a response in the \mathrm{SQIsign} interactive identification protocol is generally understood to be an isogeny connecting a public key curve to a challenge curve . The challenge curve is generated as the codomain of a challenge isogeny , which is itself defined in terms of its kernel , a form of level structure. Thus, an equivalent characterization of a \mathrm{SQIsign} signature is as an isogeny (the composition of response and challenge isogeny) vanishing on a level structure (the kernel). This point of view is especially visible in the variant of \mathrm{SQIsign} named \mathrm{SQIprime} [ 26 ] . {\lx@inpgf@ignorespaces E_{\mathsf{pk}}} {\lx@inpgf@ignorespaces E_{\mathsf{com}}} {\lx@inpgf@ignorespaces E_{\mathsf{pk}}} {\lx@inpgf@ignorespaces E_{\mathsf{com}}} {\lx@inpgf@ignorespaces{\color[rgb]{1,0,0}E_{\mathsf{ch}}}} {\lx@inpgf@ignorespaces{\color[rgb]{1,0,0}C_{\mathsf{ch}}=\ker(\varphi_{\mathsf{ch}})}} {\lx@inpgf@ignorespaces\{0\}} \scriptstyle{\color[rgb]{1,0,0}\lx@inpgf@ignorespaces\varphi_{\mathsf{ch}}} {\lx@inpgf@ignorespaces\iff} \scriptstyle{\lx@inpgf@ignorespaces\varphi_{\mathrm{rsp}}^{\prime}=\varphi_{\mathrm{rsp}}\circ\varphi_{\mathsf{ch}}} \scriptstyle{\lx@inpgf@ignorespaces\varphi_{\mathrm{rsp}}} \scriptstyle{\lx@inpgf@ignorespaces\varphi_{\mathrm{rsp}}^{\prime}} Figure 1: SQIsign simplified (generation of key and of commitment is omitted) With this point of view, it is very natural to consider signatures where the response is requested to send a certain cyclic subgroup (or a suitable level structure) to another one, instead of annihilating it. This is exactly the idea of our new proposal: \mathrm{SQInstructor} is a general framework following this idea, with freedom to choose the kind of level structure and whether the response should be computed with one-dimensional or with HD techniques. {\lx@inpgf@ignorespaces E_{\mathsf{pk}}} {\lx@inpgf@ignorespaces E_{\mathsf{com}}} {\lx@inpgf@ignorespaces{\color[rgb]{1,0,0}C_{\mathsf{ch}}\,\,\text{ or }\,\,\phi_{\mathsf{ch}}}} {\lx@inpgf@ignorespaces C_{\mathsf{com}}\,\,\text{ or }\,\,\phi_{\mathsf{com}}} \scriptstyle{\lx@inpgf@ignorespaces\varphi_{\mathrm{rsp}}} Figure 2: SQInstructor simplified (generation of key and of commitment is omitted) Contributions. In this work we instantiate and explore in detail the use of level structures for the \mathrm{SQInstructor} protocol. Progressively in each section we: • Generalize the well-known Deuring Correspondence to the setting of supersingular elliptic curves with level structure, with some concrete examples. Remarkably, we show how to make this correspondence explicit, even for large non-smooth levels. • We describe the new identification scheme \mathrm{SQInstructor} in full generality, leaving open the choice of the level structure and isogeny representation for the specific instantiation of the protocol. • Instantiating the framework using 1-dimensional isogenies, a la [ 23 ] requires solving specific constrained norm equations in the quaternion algebra {{\mathcal{B}_{p,\infty}}} . We show how to modify and combine previous algorithms in the literature to efficiently solve these equations in practice. We believe this is of independent interest. We also give a proof-of-concept implementation of these algorithms. • We instantiate the framework using 2-dimensional isogenies, prove its security under assumptions similar to those of \mathrm{SQIsign} , and give an optimized implementation based on [ 1 ] . Related work. Arpin [ 5 ] initiated the study of supersingular isogeny graphs with Borel level structure and generalized the Deuring correspondence to them. Here we extend the correspondence to even more general level structures, and explain for the first time how to build SQIsign-like identification protocols from it. In [ 22 ] , level structures were used to classify SIDH-like hardness assumptions and prove reductions between them, showing in particular that the SIDH attacks [ 15 , 34 , 40 ] apply to a broader class of problems than initially thought. Although we use level structures in this work, we only do so constructively and we never rely on the kind of assumptions studied in [ 22 ] . The security of \mathrm{SQInstructor} rests on the same foundations as SQIsign itself. Basso, De Feo, Patranabis, Radulescu and Wesolowski [ 9 ] introduce an abstract framework for SQIsign-like schemes called forensic categories . Among the proposed instantiations of the framework, one is based on level structures and yields an identification protocol equivalent to \mathrm{SQInstructor} ’s 1 1 1 Precisely, equivalent to the 1-dimensional variant of Section 5 . Their work is complementary to ours: whereas they focus on protocols and show that one can construct ring signatures and chameleon hashes from any forensic category, we focus on algorithms, carefully generalizing the Deuring correspondence and explaining how to implement \mathrm{SQInstructor} ’s 1- and 2-dimensional variants. Acknowledgments. We thank Andrea Basso, Sikhar Patranabis, Ilinca Radulescu and Benjamin Wesolowski for the useful discussions, and Antonin Leroux for pointers to KLPT variants. The third author is supported by the MIUR Excellence Department Project MatMod@TOV awarded to the Department of Mathematics, University of Rome Tor Vergata, by the PRIN PNRR 2022 “Mathematical Primitives for Post Quantum Digital Signatures” and by GNSAGA - INdAM. All other authors are supported by SNSF Consolidator Grant CryptonIs 213766. 2 The Deuring Correspondence in Cryptography We recall here some basic facts about the Deuring correspondence and its applications to cryptography, in particular to SQIsign. We assume some familiarity with elliptic curves, isogenies and quaternion algebras. For more details, we refer to [ 41 , 43 , 25 , 12 ] . Throughout this document we fix a prime p and we write \mathbb{F}_{p} for the finite field with p elements, \mathbb{F}_{p^{2}} for a field extension

Read the complete text