SQIsign: the isogeny-based digital signature proposed to NIST

08 Sep 2025

Introduction

Among the digital signatures submitted in 2023 to the NIST call in the post-quantum standardization process, the only proposal based on isogenies is SQIsign (Short Quaternion Isogeny Signature). Unique in its kind, this protocol offers greater variety in the class of hard computational problems resistant to quantum attacks; the other side of the coin is the complexity of the mathematical theory behind the techniques and objects involved.

The security of SQIsign is based on the EndRing Problem, which for supersingular elliptic curves is equivalent to the $\ell$ –IsogenyPath Problem. The link between these two problems is suggested by isogeny graphs: cycles in isogeny graphs determine endomorphisms.

More explicitly, this means that, given two elliptic curves with known endomorphism rings, it is possible to compute an isogeny between them and, conversely, given an isogeny whose domain’s endomorphism ring is known, it is possible to compute the endomorphism ring of the codomain curve. The standard choice for a starting curve $E_0$ for which $\mathrm{End}(E_0)$ is known is:

$E_0: y^2=x^3-x,$

which is also used in the signature scheme.

SQIsign is based on a three-pass identification scheme converted into a digital signature using the Fiat-Shamir paradigm. The Prover’s public key consists of an elliptic curve $E_{pk}$ and the secret key is its endomorphism ring $\mathrm{End}(E_{pk})$ . Essentially, given $E_{pk}$ as public information, the goal of the Prover is to convince the Verifier that they know $\mathrm{End}(E_{pk})$ .

The latest version of the protocol was introduced in 2025 and constructively uses techniques developed to attack SIDH in 2022. Thanks to these, it is possible to represent the involved isogenies more efficiently, thereby improving the performance of the signature scheme.

Signature Protocol Overview

In SQIsign, the public key is an elliptic curve $E_{pk}$ and the secret key is $\mathrm{End}(E_{pk})$ . Due to the equivalence between the EndRing and $\ell$ –IsogenyPath Problems, knowing the secret key is equivalent to knowing an isogeny

The identification scheme from which SQIsign derives via Fiat-Shamir allows the Prover to demonstrate knowledge of $\mathrm{End}(E_{pk})$ to the Verifier. It consists of three steps and can be simplified as follows:

Commitment: The Prover generates an isogeny $\phi_{com}: E_0 \rightarrow E_{com}$ and sends the curve $E_{com}$ to the Verifier. Recall that, due to the equivalence between EndRing and $\ell$ –PathProblem, the Prover knows the endomorphism ring of $E_{com}$ .
Challenge: The Verifier responds with an isogeny $\phi_{chl}: E_{pk} \rightarrow E_{chl}$ .
Response: Since the Prover knows $\mathrm{End}(E_{pk})$ and $\phi_{chl}: E_{pk} \rightarrow E_{chl}$ , they can compute $\mathrm{End}(E_{chl})$ . Knowing both $\mathrm{End}(E_{com})$ and $\mathrm{End}(E_{chl})$ allows the Prover to compute an isogeny $\phi_{rsp}: E_{com} \rightarrow E_{chl}$ , which is then sent to the Verifier.

The Verifier accepts if $\phi_{rsp}$ is indeed an isogeny from $E_{com}$ to $E_{chl}$ and if $\phi_{chl}$ is not a component of the response isogeny; otherwise, it rejects.

Ensuring that the response isogeny does not factor through the challenge is crucial for the security of the protocol. Indeed, a dishonest Prover — who does not know $\mathrm{End}(E_{pk})$ — could generate a commitment by choosing a dummy isogeny $\phi_{com}^{\textit{cheat}}: E_{pk} \rightarrow E_{com}$ . Without knowing $\mathrm{End}(E_{pk})$ , the Prover would not be able to compute $\mathrm{End}(E_{com})$ , but that’s not an obstacle. In fact, given the challenge $\phi_{chl}: E_{pk} \rightarrow E_{chl}$ , the dishonest Prover would respond with:

$\phi_{rsp}^{\textit{cheat}}:=\phi_{chl}\circ \widehat{\phi_{com}^{\textit{cheat}}}: E_{com}\longrightarrow E_{chl},$

where $\widehat{\phi_{com}^{\textit{cheat}}}: E_{com} \rightarrow E_{pk}$ is the dual of $\phi_{com}^{\textit{cheat}}$ .

If the Verifier does not check whether the response isogeny has this form, the dishonest Prover would pass the verification, and SQIsign would be trivially insecure.

In summary, the Prover must produce an isogeny from the commitment curve (whose endomorphism ring they know) to an arbitrary curve defined as the codomain of the Verifier’s challenge. The equivalence between EndRing and $\ell$ –PathProblem implies this is equivalent to knowing the endomorphism ring of $E_{chl}$ . Since the challenge is an isogeny from the Prover’s public key to $E_{chl}$ , knowing $\mathrm{End}(E_{chl})$ implies knowledge of the secret key $\mathrm{End}(E_{pk})$ .

The Mathematics Behind SQIsign Implementation

The implementation of SQIsign relies not only on the theory of elliptic curves but also on two other families of mathematical objects: quaternions and abelian surfaces.

Quaternions

It is natural to consider quaternions in the study of elliptic curves thanks to a mathematical correspondence known as the Deuring correspondence, which allows translating the geometric world of elliptic curves into the purely algebraic world of quaternions. The switch to quaternions is necessary for key generation and signing, while verification stays within the realm of elliptic curves.

Quaternions can be thought of as a generalization of complex numbers. A complex number is written as $a + bi$ , where $i$ is the square root of $-1$ , i.e., $i^2 = -1$ . Similarly, to define quaternions, we introduce not only the root $i$ of $-1$ but also the root $j$ of a negative prime $-p$ , which in SQIsign is the characteristic of the (finite) field over which the elliptic curves are defined. Operationally, a quaternion can be represented as a quadruple of rational numbers. The set of such elements forms the so-called quaternion algebra, denoted $B_{p,\infty}$ .

The Deuring correspondence states that the endomorphism rings of supersingular elliptic curves correspond to specific subsets of the quaternion algebra $B_{p,\infty}$ , called maximal orders. Quaternions corresponding to endomorphisms have the advantage of being representable as quadruples of integers.

Through the Deuring correspondence, we obtain quaternion analogs of foundational problems in isogeny-based cryptography. For example, the EndRing Problem becomes the MaxOrder Problem, which asks, given an elliptic curve $E$ (defined over a field of characteristic $p$ ), to explicitly determine the maximal order in $B_{p,\infty}$ isomorphic to $\mathrm{End}(E)$ .

Surprisingly, the quaternionic analogs can be solved more efficiently than the original problems—highlighting how the algebraic world of quaternions is more computationally convenient. However, this does not compromise the security of isogeny-based cryptography because the computational difficulty lies in the transition from isogenies to quaternions: this conversion is, in fact, the most computationally expensive step in the SQIsign signing process.

Isogenies in Dimension 2

The use of isogenies between abelian surfaces, the two-dimensional generalization of elliptic curves, is one of the most significant differences in the latest version of SQIsign.

Elliptic curves are one-dimensional geometric objects. Their definition can be generalized to any dimension, leading to the notion of abelian varieties; specializing to dimension 2, we get abelian surfaces. A concrete example is the product of two elliptic curves; these are the most relevant abelian surfaces in the SQIsign protocol.

Increasing the dimension allows each isogeny between products of elliptic curves to be represented via the image of certain points. This is made possible by the Kani Lemma, a theoretical result from the late 1990s, which essentially allows writing isogenies between products of elliptic curves as $2\times 2$ matrices whose entries are 1-dimensional isogenies.

The Kani Lemma is the key ingredient in the 2022 attacks on SIDH and SIKE, as it enables reconstruction of an elliptic curve isogeny by “embedding” it in an isogeny between abelian surfaces. In other words, one can obtain it as one of the entries of the $2\times 2$ matrix representing an isogeny between products of elliptic curves.

Kani’s result had been known in the mathematical literature for over two decades before it was leveraged for these attacks. This highlights one of the most delicate aspects of SQIsign and isogeny-based cryptography: the mathematical theory on which security assumptions rely is deep and sophisticated and has only recently gained attention from a cryptographic point of view.

Performance

The most attractive properties of SQIsign are undoubtedly the sizes of the public key and the signature, both smaller than those of the post-quantum signature schemes standardized by NIST in 2023: Falcon, CRYSTALS-Dilithium and SPHINCS+..

fig6_28 — Public key and signature size of main digital signatures

On the other hand, as discussed in the previous section, the operations involved in key generation and signing are highly non-trivial due to the need to manage quaternions and degree-two isogenies. This implies that, despite recent research significantly improving performance, it remains the Achilles’ heel of SQIsign. Since key generation is done offline and only a limited number of times, we focus on the signing process. Compared to lattice-based signatures like CRYSTALS-Dilithium and Falcon, at the first security level (128 bits), SQIsign requires several orders of magnitude more cycles to sign a message.

Verification times, though still behind lattice-based competitors, are acceptable and make SQIsign an interesting alternative in use cases where the transmission and verification of a large number of signatures is required.

fig7_28 — Performance (measured in cycles) of key generation, signing, and verification operations

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Elena Broggini, MSc in Mathematics at University of Milan. She is currently a PhD student in the Number Theory and Cryptography group at the Polytechnic University of Turin with a scholarship on Post-Quantum Cryptography and Fully Homomorphic Encryption in collaboration with the Telsy research group.

Giuseppe D’Alconzo is a research fellow at the Polytechnic University of Turin. He received his Ph.D. in Mathematics with a grant themed “Post-Quantum Cryptography” under the UniversiTIM program and in collaboration with the Telsy Research Group. He graduated in Mathematics with a specialization in Cryptography from the University of Trento, and he did an internship at Telsy in 2019, working on Multi-party Computation and Attribute-Based Encryption.