Learning to SQI

Implementing SQISign in SageMath

Maria Corte-Real Santos, Giacomo Pope

Subroutines when Computing Isogenies from Ideals

At a high level, the purpose of the algorithm IdealToIsogenyFromKLPT() is to compute the isogeny corresponding to a given ideal (via the Deuring Correspondence). We discuss how it is implemented in more depth in Computing Isogenies From Ideals.

In this blogpost, however, we discuss the two main subroutines in IdealToIsogenyFromKLPT():

  1. IdealToIsogenyCoprime() to translate and evaluate T-isogenies (where T is coprime to )
  2. IdealToIsogenySmallFromKLPT() to translate f-isogenies using the output of IdealToIsogenyCoprime().

Corresponding isogeny of ideal with coprime norm

We first describe IdealToIsogenyCoprime(), which takes as input two equivalent left O0-ideals J,K where J has norm dividing T2 and K has -power norm, as well as the connecting isogeny corresponding to K, namely φK:E0EK. The output is the isogeny φJ:E0EJ corresponding to J.

As the two ideals are equivalent, we expect the domains and codomains of φI and φJ to be isomorphic. The importance of this function is to find isogenies with coprime degrees which is important for various pushforwards and pullbacks in the parent algorithms which call IdealToIsogenyCoprime().

The algorithm can be broken down into the following steps:

  1. Consider the function: χI=Iα¯n(I),αI{0}, as defined in Lemma 1 in the SQISign paper. For the first step, we need to find α such that χK(α)=J, which is achieved using the function chi_inverse().

  2. We compute two ideals H1=J+O0T, and  H2=O0α+O0n(J)n(H1). Ensure that the ideals are cyclic and that their norm divides T.

  3. Compute the isogenies whose kernels correspond to the Hi, say φi:E0Ei=E0/Hi.

  4. Compute an isogeny ψ:EKEψ=EK/φK(ker(φ2)), i.e., ψ=[φK]φ2 is the pushforward of φ2 through φK. The codomain of Eψ should be isomorphic to E1, but may not be equal. To fix this we use techniques described in Correct up to Isomorphism.

  5. Compute the dual isogeny ψ^. Throughout, we can ensure the computation of the dual isogenies is efficient by exploiting the fact we already know the kernel of ψ. For an isogeny of degree D, we find ker(ψ^)=ψ(R) for some point RE[D] linearly independent to ker(ψ). By the previous step, the codomain of φ1 and the domain of ψ^ should be the same.

  6. Return φJ=ψ^φ1:E0E1EKEJ=E0/J.

Corresponding isogeny of ideal with norm 2fstep+Δ

Next, we describe the subroutine IdealToIsogenySmallFromKLPT() in more detail. This algorithm takes the following input: left O0-ideals I and J of norm dividing T22fstep+Δ and T2 (respectively), an ideal KJ of -power norm, and the isogenies φJ, φK from E0 to E1 corresponding to J, K respectively. It will output:

  • φ:E1E2 of degree 2fstep+Δ, such that φI=φφJ,
  • LI of norm dividing T2
  • The corresponding isogeny φL:E0E2.
A diagram to show how the isogeny $\varphi$ is computed.

Figure 1: We compute φ using the isogeny diagram above. The isogenies in purple are given as input, and those in red are computed within the algorithm to obtain φ.

Following the diagram above, we compute φ:E1E2 and φL:E0E2 as:

  • φ=ψ1ρ2ηψ1φ1.
  • φL=ψ1ψ2

We will do this as follows:

  1. Compute φ1:E1E3: we first compute the kernel corresponding to I1=I+O0step of norm dividing step. Let P be the generator of this kernel. As I1 is a left O0-ideal, PE0. As φ1 has domain E1, we map P to E1 using φJ:E0E1. Then, φ1:E1E1/φJ(P).

  2. Compute ideal L: we now use KLPT to compute the ideal L equivalent to I with norm dividing T2 by running EquivalentSmoothIdealHeuristic().

  3. Compute γ: we compute α such that χK(α)=J, and β such that χI(β)=L using chi_inverse(). Set γ=βαn(J). Be careful: when n(K)=1, chi_inverse() will return ±i. This means that when we compute kernels from γ, it may be twisted by the automorphism ι. To avoid this, we manually set α=1.

  4. Compute ψ1: as the domain of ψ1 is not E0, we need to instead consider a related ideal with left order O0. The ideal we consider is H1=O0γ+O0(n(K)fstepT), which will correspond to the isogeny φH1=ψ1φ1φK:E0E5 of degree n(K)lfstepT. Note that the -power part of H1 corresponds entirely to φ1φK as deg(φ1)=fstep and deg(φK)=n(K). Therefore, we only need to compute the part of H1 coprime to , namely H1=O0γ+O0T. From this, which we obtain ψ1 by running ideal_to_kernel() on H1 to obtain kernel generator P. As H1 has left order O0, PE0. Therefore, the kernel of ψ1 is generated by φ1(φK(P))E3.

  5. Compute ψ2 and ρ^2: we now consider the ideal H2=O0γ¯+O0n(γ)n(H1)Δ. Then, H2 has left order O0 and will correspond to the isogeny φH2:E0E6 of degree dividing fstepT. How can this be used to compute ψ2 and ρ^2?

    • This isogeny can be decomposed as ρ^2ψ2:E0EψE6 where ρ^2 is of degree dividing fstep and ψ2 is of degree dividing T.
    • Compute ker(φH2) by running ideal_to_kernel() on H2.
    • Then, ker(ψ2) is the subgroup of order (dividing) T within ker(φH2), i.e., ker(ψ2)=lhker(φH2), where h is the -valuation of n(H2). From this kernel we obtain ψ2:E0Eψ.
    • Similarly, we compute the subgroup of ker(φH2) of order fstep and push it through ψ2 to obtain ker(ρ^2), and therefore ρ^2.
  6. Meet-in-the-middle step to find η: we now brute force the isogeny η:E5E6 of (small) degree Δ by using meet-in-the-middle. For more details on this, see the page Meet in the Middle Isogenies.

Recall that the desired output of this function is: φ:E1E2 such that φI=φφJ, an ideal LI and the corresponding isogeny φL. We now have all the pieces we need, but to output everything correctly, we will need to perform some pushforwards and pullbacks.

To compute φ, we exploit the fact that we know φ1:E1E3, and φ=φ2θφ1. For the other outputs, we have already computed L in Step 2, and the corresponding isogeny is given by ψ1ψ2:E0E2, for which we computed ψ2 in Step 5. We are left to compute ψ1 and φ2θ.

A diagram to show how the two isogenies are computed.

Figure 2: We compute ψ1 and φ2θ (shown in red) by considering the isogeny diagram above.

  1. Compute ψ1: from the diagram we can see that ker(ψ1)=ρ2(η(ker(ψ^1))), so once we compute the dual of ψ1, we can compute ker(ψ1), and therefore ψ1.

  2. Compute φ2θ: ideally, we would compute the kernel of φ2θ by observing that it is equal to ψ^1(ker(ρ2η)). However, we do not actually know the kernel of ρ2η, so we work around this by computing λ1 and λ3 as φ2θ=λ3λ1. We do this, using the diagram above, as follows:

    • We first compute ker(λ1)=ψ^1(ker(η)) and from this we get λ1:E3Eλ.
    • To compute λ3, we first need λ2, whose kernel is given by η(ker(ψ^1)). Then, by pre-composing with an isomorphism if necessary to make its codomain Eλ, we obtain λ2:E6Eλ.
    • Finally, we compute the kernel of λ3 as λ2(ker(ρ2)) to obtain the isogeny λ3:EλE2.

We can now output φ, L, and φL as required.

Edge cases

Small step size

When the step size is small enough, i.e., smaller than fstep, we can avoid going through the entire procedure above as the isogeny we wish to compute has degree dividing the available torsion, and we can skip many of the tricks used above and simply directly compute the kernel from the ideal. Concretely, we simply do the following:

  1. Set φJ and φK to have the same codomain as above.
  2. Derive φ1 as above.
  3. Find L, an ideal equivalent to I with norm dividing T2.

We then return φ1 and L. This will only happen when IdealToIsogenySmallFromKLPT() is called as the last step of the parent IdealToIsogenyFromKLPT().

Backtracking: when γ has non-trivial GCD

There is a caveat with the procedure depicted above. Before computing Hi in IdealToIsogenySmallFromKLPT() the coefficients of γ (when written as a linear combination of the basis elements of O0) may have non-trivial GCD, which causes the isogenies to backtrack and the algorithm to fail. One solution is to regenerate L and γ until the coefficients of γ have trivial GCD. However, we can relax the condition by fixing this backtracking when the GCD is a power of . We detail this procedure below.

Let α1,,α4 be a basis of O0, and write γ=c1α1++c4α4. Let g=gcd(c1,,c4). If g×, we regenerate L and γ. Otherwise, let us say g=d. We replace γ with γ/g. Note that now will have gγK, gγ¯L, and n(γ)=n(I)n(L)n(K)g2n(J). The ideals H1,H2 are computed in the same way, but in the meet-in-the-middle step we now expect to find an isogeny of degree Δ+d between E5 and E6.

Back to Top