Overview
SQISign is an isogeny-based signature scheme that exploits the Deuring correspondence, which connects the world of supersingular elliptic curves over
- Supersingular
-invariants over (up to Galois conjugacy) Maximal orders in such that (up to isomorphism). - An isogeny
of degree an integral left -ideal and right -ideal of norm - An endomorphism
A principal ideal .
If we have two isogenies
Developing efficient algorithms for the maps translating objects to and from the geometric world of elliptic curves and algebraic world of quaternions has been the focus of many works, including for example [KLPT14], [GPS17], [EHLMP18], [DKLPW20], [W21], [DLW22], and [EPSV23].
- Given a
-invariant , it is computationally hard to compute the corresponding maximal order as this would require the computation of the endomorphism ring of , which is conjectured to be a hard problem. In fact, this underlies the security of isogeny-based cryptography. Indeed, the quaternion -isogeny problem, which is the analogue of the -isogeny problem in quaternion algebras, can be solved in polynomial time ( and ) conversely, given the maximal order , it is easy to compute the corresponding supersingular elliptic curve. - By following the
and algorithms introduced in the SQISign paper, we are able to implement efficient algorithms for the translation of ideals to and from isogenies.
SQISign is obtained from a high-soundness, one round interactive identification protocol by the Fiat-Shamir transform. In our code, we implement this identification protocol, as described in the original paper, which consists of the following algorithms:
Setup
: on input of the security parameter , pick a suitable prime number and let be the special supersingular curve over . Throughout, we will fix . Then, select an odd, smooth, -bit numbers with which divide . Let , where is greater than the diameter of the -isogeny graph.Keygen
: given parameters, pick a random isogeny of prime degree , leading to a random elliptic curve . The public key is and the secret key is the isogeny .Commitment
: the prover generates a random (secret) isogeny walk of degree and sends to the verifier.Challenge
: the verifier sends the degree- cyclic isogeny to the prover.Response
: from , the prover constructs a new isogeny of degree with cyclic, and sends to the verifier.Verify
: the verifier accepts the response if is a degree- isogeny from to and the isogeny is cyclic. If any of these conditions are not met, the verifier rejects the response.

Figure 1: The SQISign Identification Protocol. Diagram inspired by Figure 1 in the original SQISign paper
We now discuss these in more depth.
Setup
We implement this in setup.py
, which computes all the global variables needed for the various algorithms given parameter sets designed for SQISign in parameters.py
.
In the parameters file, we currently have two parameters sets from which to chose: a toy
The remaining algorithms (from key generation to verification) can all be found in SQISign.py
.
Key generation
Note: We implement the efficient alternative key generation as described in Appendix D of the SQISign paper:
- Select a prime
that is inert in uniformly at random (note that this is specific to ; otherwise we require it to be inert in , the ring of integers of ). - Compute an endomorphism
of norm , where , by running . - Set
, which will be an integral left -ideal of prime norm . - Set
, which will be a cyclic left -ideal of smooth norm equivalent to . - Compute the isogeny
corresponding to usingIdealToIsogenyFromKLPT()
withend_close_to_E0 = True
. The flag signals that is equivalent to an ideal of (relatively) small norm, which may causeEquivalentPrimeIdealHeuristic()
to fail. Indeed, with . To see more details on this, see the page Equivalent Prime Norm Ideals. - The secret key will then be the degree
isogeny with corresponding public key . We also return the (secret) ideals as these will be useful for future computations.
Commitment
To generate the commitment isogeny, we first generate a torsion basis
Next, by calling kernel_to_ideal()
, we compute the ideal
Challenge
The verifier receives
Response
The response is the most technical and slowest algorithm in the SQISign identification protocol. It runs as follows.
- Compute
which corresponds to the isogeny . As , computing is inefficient. Instead, the product can be computed directly from the intersection . For more details on how this is done, see the page Pushforwards and Pullbacks. Then we runmultiply_ideals()
on and to obtain an ideal . - Run
SigningKLPT()
on to obtain a cyclic ideal of norm , where is a fixed global parameter. See Estimating Bounds for KLPT for a discussion on how we set the size of . Here, as is a left -ideal where , so we need to provide a connecting -ideal as a second input. In this case, our second input is . - We now want to find the isogeny corresponding to
. As is not a left -ideal, we need to provide a left -ideal whose right order is . By adjusting by an isomorphism if necessary, is such an ideal. Refer to the page Correct up to Isomorphism for more information on computing isomorphisms). - Given the ideal
, we then calculate as the isogeny corresponding to usingIdealToIsogenyFromKLPT
with and its corresponding isogeny as additional input. - We compress the isogeny
as a bitstring usingcompression
, more information about the compression and following decompression is given on the page Modifying Compression.
The output of this algorithm is the bitstring
Verify
After decompressing the bitstring
- The codomain of
is isomorphic to . - The degree of
is . - The isogeny
is cyclic.
This last check is done by computing a torsion basis
If all the checks pass, we return True
. Otherwise, False
.
Contents
We now give a short overview of the posts accessible on this website. The purpose of these posts is to highlight difficulties we encountered when implementing the algorithms above and explaining potential areas of confusion.
Background
- Working with Cyclic Ideals: in SQISign, we are interested in integral, cyclic ideals. We give an overview of these objects and how one can ensure a given ideal is cyclic.
- Correct up to Isomorphism: in many places, the Deuring correspondence is only correct up to isomorphism, but we must correct for exactness for the protocol to be successful. We discuss computing isomorphisms of ideals and isogenies.
- Pushforwards and Pullbacks: we describe how to compute the pushforwards and pullbacks of isogenies and ideals, which are vital for mapping to and from the curve
with known endomorphism ring.
KLPT for SQISign
- Estimating Bounds for KLPT: we discuss how we can set heuristic bounds for the KLPT algorithm such that we have a high chance of success for each call of
EquivalentSmoothIdealHeuristic()
. - Equivalent Prime Norm Ideals: one aspect of the KLPT algorithm requires computing equivalent prime norm ideals. This can fail on certain edge cases and this post aims to communicate how each edge-case is dealt with.
- Strong Approximation Lattice Trick: we can ensure the output of the KLPT has a small norm by using a lattice trick when solving the strong approximation. This page gives a detailed overview of how this works and how we have implemented it.
Computing isogenies from ideals
- Between Kernels and Ideals: at the core of the conversion of ideals and isogenies is the mapping between isogeny kernel generators and quaternion algebra generators of ideals. This page discusses how to implement the evaluation of endomorphisms
on points and then follows with a description of and . - Computing Isogenies from Ideals: we detail the algorithm that, given a cyclic ideal, computes the corresponding isogeny using
IdealToIsogenyFromKLPT()
; the algorithm introduced in the SQISign paper which allows for the construction of a high-soundness identification protocol. - Subroutines when Computing Isogenies from Ideals: the above algorithm is complicated, and so to help readers, we factor out subroutines used in
IdealToIsogenyFromKLPT()
into a separate page. - Meet in the Middle Isogenies: one step in the above algorithm is the brute force search of an
degree isogeny. We implement this with a meet in the middle algorithm using a depth-first search of the graph of j-invariants.
SQISign subtleties
- Small Steps from Curves with Small Endomorphisms: When we attempt to run the KLPT algorithm on an ideal which connects two left orders with particularly small norm, there is a chance the sub-algorithm to compute equivalent prime norm ideals may fail. This page gives detail on when we expect this to happen and how we pick an ideal filtration to ensure the protocol is successful.
- Modifying Compression: for our implementation, we found that we needed to include an additional bit to the compression algorithm to ensure successful decompression. This page details this bit, as well as giving a detailed discussion on the implementation of compression and decompression.
Conclusions
- Future Work: we summarise plans for future work, which are mainly focused between implementing the most modern description of SQISign following New algorithms for the Deuring correspondence: toward practical and secure SQISign signatures and the hope to improve the performance of isogeny computations in the current code.
Correspondence between notation
Due to the number of papers that have developed algorithms relating to the Deuring correspondence, there are various names out there for the same algorithm. Below we give a non-exhaustive list of equivalent names for algorithms in our code that appear in: the original SQISign paper; and Leroux’s thesis. We compare to these as they have associated implemented code.
Our Code | SQISign | Leroux’s Thesis |
---|---|---|
EquivalentSmoothIdealHeuristic | ||
IdealToIsogenyFromKLPT | ||
IdealToIsogenySmallFromKLPT | ||
IdealToIsogenyCoprime |
Note that throughout our code, we add heuristic to the end of algorithm names to indicate when an algorithm with some (small) probability of failure, and therefore may have to be run