Learning to SQI

Implementing SQISign in SageMath

Maria Corte-Real Santos, Giacomo Pope

Overview

SQISign is an isogeny-based signature scheme that exploits the Deuring correspondence, which connects the world of supersingular elliptic curves over Fp2 to the world of quaternion algebras. More precisely, we have a one-to-one map between the following objects:

  1. Supersingular j-invariants over Fp2 (up to Galois conjugacy) Maximal orders in Bp, such that OEnd(E) (up to isomorphism).
  2. An isogeny φ:EE1 of degree D an integral left O-ideal and right O1-ideal Iφ of norm n(Iφ)=D.
  3. An endomorphism θEnd(E0) A principal ideal Oθ.

If we have two isogenies φ:EE1 and ψ:EE1 (i.e., two isogenies with the same domain and codomain), they will correspond to equivalent ideals IφIψ. This correspondence also behaves well with multiplication of ideals. Namely the ideal IρIτ is equal to Iτρ and therefore corresponds to the isogeny τρ.

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].

  1. Given a j-invariant j(E), it is computationally hard to compute the corresponding maximal order as this would require the computation of the endomorphism ring of E, 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 O, it is easy to compute the corresponding supersingular elliptic curve.
  2. By following the IdealToIsogeny and IsogenyToIdeal 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 p and let E0:y2=x3+x be the special supersingular curve over Fp2. Throughout, we will fix p3mod4. Then, select an odd, smooth, λ-bit numbers Dc,T with gcd(Dc,T)=1 which divide (p21). Let D=2e, where e is greater than the diameter of the 2-isogeny graph.
  • Keygen: given parameters, pick a random isogeny τ:E0EA of prime degree Nτ, leading to a random elliptic curve EA. The public key is EA and the secret key is the isogeny τ.
  • Commitment: the prover generates a random (secret) isogeny walk ψ:E0E1 of degree T and sends E1 to the verifier.
  • Challenge: the verifier sends the degree-Dc cyclic isogeny φ:E1E2 to the prover.
  • Response: from φψτ^:EAE2, the prover constructs a new isogeny σ:EAE2 of degree D with φ^σ cyclic, and sends σ to the verifier.
  • Verify: the verifier accepts the response if σ is a degree-D isogeny from EA to E2 and the isogeny φ^σ:EAE1 is cyclic. If any of these conditions are not met, the verifier rejects the response.
A diagram showing the SQISign Identification Protocol.

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 54-bit prime ptoy, for which SQISign takes around 30 seconds to run; and a cryptographic sized 256-bit prime p6983 which terminates in around 12 minutes at the time of writing.

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:

  1. Select a prime NτBτp1/4 that is inert in Z[i] uniformly at random (note that this is specific to p3mod4; otherwise we require it to be inert in Z[ω], the ring of integers of Bp,).
  2. Compute an endomorphism γO0 of norm Nτeτ, where eτlog(p), by running RepresentIntegerO0(Nτeτ).
  3. Set Iτ=O0γ+O0Nτ, which will be an integral left O0-ideal of prime norm Nτ.
  4. Set Jτ=O0γ¯+O0eτ, which will be a cyclic left O0-ideal of smooth norm eτ equivalent to Iτ.
  5. Compute the isogeny τ corresponding to Jτ using IdealToIsogenyFromKLPT() with end_close_to_E0 = True. The flag signals that Jτ is equivalent to an ideal of (relatively) small norm, which may cause EquivalentPrimeIdealHeuristic() to fail. Indeed, JτIτ with n(Iτ)p4. To see more details on this, see the page Equivalent Prime Norm Ideals.
  6. The secret key will then be the degree n(Jτ) isogeny τ:E0EA with corresponding public key EA. We also return the (secret) ideals Iτ,Jτ as these will be useful for future computations.

Commitment

To generate the commitment isogeny, we first generate a torsion basis E0[T]=P0,Q0. We then compute a secret integer x and with this construct the kernel generator Kψ=P0+[x]Q0 such that ψ:E0E0/Kψ=E1.

Next, by calling kernel_to_ideal(), we compute the ideal Iψ corresponding to the commitment isogeny ψ:E0E1. We keep as secret data the isogeny ψ and the ideal Iψ, and send as the codomain E1 as our commitment to allow the generation of a challenge.

Challenge

The verifier receives E1, the codomain of ψ, and computes the challenge isogeny kernel ker(φ) by computing a basis E1[Dc]=P1,Q1 and then computing a random kernel ker(φ)=P1+[x]Q1.

Response

The response is the most technical and slowest algorithm in the SQISign identification protocol. It runs as follows.

  1. Compute I¯τIψIφ which corresponds to the isogeny φψτ^. As ker(φ)E0, computing Iφ is inefficient. Instead, the product IψIφ can be computed directly from the intersection IψI[ψ]φ=IψI[ψ^]φ. For more details on how this is done, see the page Pushforwards and Pullbacks. Then we run multiply_ideals() on I¯τ and IψIφ to obtain an ideal I.
  2. Run SigningKLPT() on I to obtain a cyclic ideal JI of norm e, where e is a fixed global parameter. See Estimating Bounds for KLPT for a discussion on how we set the size of e. Here, as I is a left O-ideal where OO0, so we need to provide a connecting (O0,O)-ideal as a second input. In this case, our second input is Jτ.
  3. We now want to find the isogeny corresponding to J. As J is not a left O0-ideal, we need to provide a left O0-ideal whose right order is OL(J). By adjusting by an isomorphism if necessary, Jτ is such an ideal. Refer to the page Correct up to Isomorphism for more information on computing isomorphisms).
  4. Given the ideal J,Jτ, we then calculate σ as the isogeny corresponding to J using IdealToIsogenyFromKLPT with Jτ and its corresponding isogeny τ as additional input.
  5. We compress the isogeny σ as a bitstring S using compression, more information about the compression and following decompression is given on the page Modifying Compression.

The output of this algorithm is the bitstring S.

Verify

After decompressing the bitstring S to obtain σ, the verification algorithm is a composition of the following checks:

  • The codomain of σ is isomorphic to E2.
  • The degree of σ is D=2e.
  • The isogeny φ^σ is cyclic.

This last check is done by computing a torsion basis EA[2f]=P,Q. The isogeny φ^σ is cyclic if and only if there are points in the image of this isogeny. It is enough to check φ^σ(P) and φ^σ(Q), and check if either has order 2f.

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 E0 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 αBp, on points PE and then follows with a description of KernelToIsogeny and IsogenyToKernel.
  • 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

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 CodeSQISignLeroux’s Thesis
EquivalentSmoothIdealHeuristicKLPTlKLPTN
IdealToIsogenyFromKLPTIdealToIsogenylIdealToIsogenyFromKLPTl
IdealToIsogenySmallFromKLPTIdealToIsogenyl2f+ΔIdealToIsogenySmallFromKLPT
IdealToIsogenyCoprimeSpecialIdealToIsogenyIdealToIsogenyCoprimeT

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 N times before terminating.

Back to Top