Post-quantum commutative group actions from oriented superspecial abelian varieties

Post-quantum commutative group actions from oriented superspecial abelian varieties Wouter Castryck1 , Bogdan Adrian Dina2,3 , Péter Kutas2,4 , and Gioella Lorenzon1

arXiv:2610.27922v1 [math.NT] 20 Oct 2026

1

KU Leuven, Belgium Eötvös Loránd University, Hungary 3 University of Haifa, Israel 4 University of Birmingham, United Kingdom 2

Abstract. We study the cryptographic use of Shimura class group actions on superspecial principally polarized abelian varieties equipped with a CM orientation, within the context of post-quantum cryptography. Besides giving an accessible introduction to the topic, illustrated with many examples, we provide tools for representing CM orientations through higher-dimensional isogenies and for computing the Shimura class group action in the restricted effective group action model. Here, key auxiliary results are a version of Kani’s lemma “with CM” and a trick that often allows to halve the ambient dimension. We also give a method for finding superspecial principally polarized abelian surfaces that are oriented by a given CM order, which is extracted from an algebraic framework for studying CM orientations using the Ibukiyama–Katsura– Oort correspondence. We also analyze obstructions to transitivity of the Shimura class group action, related to the characteristic-zero notion of CM type.

1

Introduction

Commutative cryptographic group actions generalize exponentiation in finite cyclic groups and inherit some of its versatility in cryptographic design, such as non-interactive key exchange protocols à la Diffie–Hellman and threshold signatures, see [1] for an overview. At the same time, the concept is general enough to allow for (conjecturally) quantum-resistant instantiations, unlike exponentiation which falls prey to Shor’s algorithm. This generality is, however, relative: the only known fruitful source of post-quantum commutative group actions comes from the theory of complex multiplication (CM). Moreover, nearly all known instantiations work in dimension g = 1, i.e., using elliptic curves, where the groups are ideal-class groups of imaginary quadratic orders, acting on sets of oriented elliptic curves via isogenies. Their cryptographic use was proposed independently by Couveignes [29] and Rostovtsev–Stolbunov [87], using ordinary elliptic curves over finite fields, but the focus has now shifted to supersingular elliptic curves for the sake of flexibility and efficiency. This is implemented, e.g., in [17,35,5]. CM theory in arbitrary dimension g ≥ 1 was developed by Shimura and Taniyama mid-20th century [89]. Unlike the elliptic curve case, the acting group

is not simply the ideal-class group of an imaginary quadratic order, but a slightly more complicated class group attached to a CM order of rank 2g. The complication comes from the fact that it acts on principally polarized abelian varieties (PPAVs); the action needs to be compatible with the polarization data. Given the growing role of higher-dimensional abelian varieties in isogenybased cryptography, and given the central place of CM theory in the theory of PPAVs, it is a natural goal to study how Shimura class group actions can be put to cryptographic use. Our purpose is to initiate this study for superspecial PPAVs, which are the appropriate generalizations to higher dimension of supersingular elliptic curves. Sanon’s PhD thesis [88] already gave a high-level description of a key exchange protocol from Shimura class groups acting on absolutely simple, ordinary abelian surfaces over a finite field Fq oriented by their full endomorphism ring. We are unaware of other literature exploring such constructive uses, let alone in the superspecial setting, although [83] mentions the possibility of extending the module-action framework to modules over CM orders, which would generalize our discussion (which corresponds to rank-1 modules). This being said, the Shimura class group action has been on cryptographers’ radars for a long time, in tangential studies such as [68,6,7,63,10,51]. When compared to elliptic curves, the cases g > 1 offer two potential advantages: (i) one can reach larger class groups for a given field size, especially when working over a prime field Fp as in CSIDH [17], which is not possible in large-discriminant frameworks such as [16,46], and (ii) there potentially exist more prime ideals of a given small norm ℓ, allowing for a key space that is more concentrated on small primes. But we mainly view this work as a didactic exploration of CM orientations on superspecial PPAVs and the corresponding Shimura class group actions, with a focus on their cryptographic use and spiced up with many examples. We also note that, already in dimension g = 1, orientations and CM actions have proven to be important tools beyond the constructive use of cryptographic group actions [34,45,66]. Contributions and paper organization. Our contributions are organized as follows. First, after reviewing CM orientations and Shimura class groups in Section 2, with further background to be found in the appendices, we introduce some recurring examples of superspecial CM orientations in Section 3. Next, in Section 4 we discuss how to set up and evaluate Shimura class group actions within the g-REGA model from [1]. This includes finding the generating set g and representing the orientation; two auxiliary tools here are an enhanced version of Kani’s lemma incorporating the CM orientation, and a dimension-halving trick often allowing the user to keep working in dimension g (which seems a new observation even for g = 1). Along the way we describe the structure of Shimura class groups of CM orders in biquadratic CM fields (i.e., C2 × C2 fields), and we break a security measure proposed by Sanon in Remark 4.8. Then in Section 5, we give a purely algebraic treatment of CM orientations on superspecial principally polarized abelian surfaces (PPASs), within the framework of the Ibukiyama– Katsura–Oort (IKO) correspondence from [49]. We show how to evaluate the 2

Shimura class group action on the IKO-side, and how to produce superspecial PPASs that are oriented by a prescribed CM order; this has applications to the 2dimensional version of the “one endomorphism” problem (often called OneEnd in the literature [79]), on which we elaborate in Appendix I. Next, in Section 6, we delve into the orbits of the Shimura class group action, which is a rich and much more intricate discussion than in the case g = 1, led by the characteristic-zero notion of CM type. An interesting by-product of our discussion is a very efficient method for deciding whether two given oriented supersingular elliptic curves lie in the same orbit under the usual ideal-class group action, see Example 6.3. We conclude in Section 7 with some security considerations. Appendices. To keep the main body contained, a considerable amount of material was deferred to the appendices. Besides additional background in Appendices A, J and proofs in Appendices D, E, H, they contain several results worth highlighting. Most notably, building on Section 4, we present a key exchange protocol built from superspecial CM-oriented PPASs, all defined over Fp , where the real multiplication part is generated by the p-th power Frobenius endomorphism. The starting orientation is called R2-D4 and described in Appendix C, while concrete parameters tailored for efficient key exchange are discussed in Appendix F. Some compression techniques for CM-oriented superspecial PPASs over Fp can be found in Appendix G. Along the way, for use in R2-D4 and similar orientations, we give explicit descriptions of the endomorphism rings of certain well-known supersingular elliptic curves in Appendix B, thereby fixing and completing corresponding statements in the existing literature. Away from key exchange, we recall that Appendix I contains results on the 2-dimensional counterpart of OneEnd. In Appendix K we slightly extend a result due to Goren [42], which describes modulo which unramified primes p a given CM-oriented PPAS in characteristic zero has a superspecial reduction; concretely, unlike Goren, we also cover the C2 × C2 case, i.e., the case of CM by a biquadratic field. Acknowledgements. The authors would like to thank Eyal Goren, the reviewers of a prior version of this paper, and the authors of [28,50] for helpful input and feedback. For the statement and proof of Lemma 5.14 we strongly benefited from interactions with Claude Opus 5.5 (Anthropic PBC). All authors are supported by the European Union under the Horizon Europe programme with grant agreement No. 101309092 (PQC-SCAN), as well as by the CELSA alliance through the MaCro project. Castryck and Lorenzon are also supported by the European Research Council (ERC) under the Horizon 2020 programme, grant agreement No. 101020788 (ISOCRYPT), by the Research Council KU Leuven grant C14/24/099, as well as by Cybersecurity Research Flanders with reference number VR20192203. Kutas is partly supported by EPSRC through grant number EP/V011324/1, and together with Dina, he is also supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Quantum Information National Laboratory Program. Kutas is also supported by NRDI grant “EXCELLENCE-151343”. Lorenzon is funded by 3

Research Foundation – Flanders (FWO) under a PhD Fellowship fundamental research (project number 1139225N).

2

Background

We review the notions of principally polarized abelian varieties (PPAVs) equipped with a CM orientation and the Shimura class group action. More elementary background can be found in Appendix A, to which we have deferred all proofs. 2.1

CM orientations

Henceforth K denotes a CM field of degree 2g, i.e., a totally imaginary quadratic extension of a totally real degree-g number field K0 ⊃ Q. Observe that K comes equipped with an automorphism x 7→ x with fixed field K0 that we can think of as complex conjugation. We write K0+ for the set of totally positive elements in K0 , i.e., whose minimal polynomial over Q has positive real roots only. Definition 2.1. A K-orientation on a g-dimensional PPAV (A, λ) is a homomorphism ι : K ,→ End0 (A) such that ι(α) = ι(α)† for all α ∈ K, where † denotes the Rosati involution. We say that ι is moreover a primitive R-orientation, for some order R ⊂ K, if ι−1 End(A) = R. Since End(A) is closed under the Rosati involution, primitive R-orientations can only occur for orders that are self-conjugate, i.e., R = R. 5 We call such an order a CM order. A sufficient condition is that R has maximal real multiplication, i.e., R ∩ K = ZK0 . We remark that we use the terminology of “orientations” for the sake of analogy with cryptographic customs in the case g = 1, but we note that many mathematical texts just talk about PPAVs “with CM”. Consider two K-oriented PPAVs (A1 , λ1 , ι1 ), (A2 , λ2 , ι2 ). Let µ ∈ K0+ ∩ −1 ι1 End(A1 ), i.e., µ ∈ K is such that ι1 (µ) is a totally positive endomorphism on A1 (e.g., we can choose µ = N ∈ Z>0 ). Consider an ι1 (µ)-isogeny φ : (A1 , λ1 ) → (A2 , λ2 ). Then we say that this polarized isogeny is an oriented −1 isogeny if for all α ∈ ι−1 1 End(A1 ) ∩ ι2 End(A2 ) we have φ ◦ ι1 (α) = ι2 (α) ◦ φ. We mark this by writing φ : (A1 , λ1 , ι1 ) → (A2 , λ2 , ι2 ). If both orientations are primitive for the same order R ⊂ K then we say that it concerns a horizontal oriented isogeny. An oriented isomorphism is an oriented 1-isogeny. Definition 2.2. Let K be a CM field of degree 2g. We write Mk (K) for the set of K-oriented PPAVs (A, λ, ι) over k, up to oriented isomorphism. For a CM order R ⊂ K, we write Mk (R) for the subset of primitively R-oriented PPAVs. Remark 2.3. If g = 1 then we suppress the canonical principal polarization from the notation and denote the elements of Mk (K) as (E, ι). The set Mk (R) may be empty. E.g., this is the case if g = 1, p > 0 and p | [ZK : R], see Section 6. 5

√ √ √ √ E.g., the order Z[ 2 + −1] ⊂ Q( 2, −1) does not satisfy R = R.

4

2.2

The Shimura class group

To any CM order R in a CM field K we attach its Shimura class group, denoted C(R). The nomenclature in the existing literature is heterogeneous: the Shimura class group also goes under the name polarized class group, while our main reference [65] even just talks about “a Picard group”, denoting it as Pic∗ R. Explicitly, consider pairs (a, µ) where a is an invertible fractional R-ideal such that aā = µR, and µ ∈ K0+ (i.e., µ is a totally positive element of K0 ). Endowed with component-wise multiplication, such pairs form a group we denote by IR . Pairs (µR, µµ̄) with µ ∈ K × form a subgroup we denote by PR . The Shimura class group of R is the quotient C(R) := IR /PR .

(1)

We denote by ∼ the equivalence induced by PR on pairs (a, µ) ∈ IR . If g = 1 then the existence of µ ∈ K0+ = Q>0 such that aā = µR is an automatic condition and it determines µ uniquely (namely, it must be the norm of a). Thus, in this case, it is immediate that C(R) ∼ = Cl(R). Lemma 2.4. For a given invertible fractional ideal a ⊂ R there are at most 2g−1 Shimura classes [(a, µ)] ∈ C(R). √ √ then ε1 = 1 + 2 is√not totally positive, so there Example 2.5. If K0 = Q( 2) √ is one class only. If K0 = Q( 3) then ε1 = 2 + 3 is totally positive, so here there will √ be two classes, typically, but there are exceptions: e.g., if K = K0 (α) with α = −ε1 then clearly ε1 = αᾱ so, here too, there is one class only. As explained in the proof of Theorem 2.7 below, if a ⊂ R then we can act with the Shimura ideal (a, µ) on any primitively R-oriented PPAV (A, λ, ι) by means of an ι(µ)-isogeny. Since all existing formulae for isogeny evaluation in higher dimension restrict to N -isogenies for some positive integer N , in practice we will restrict to Shimura ideals for which µ = N ∈ Z>0 , even though in Corollary 5.6 we will explain how the KLPT2 algorithm from [13] can be used, in principle, to by-pass this restriction in the case of an oriented superspecial PPAS with “known” endomorphism ring. The Shimura classes of the form [(a, N )] with a ⊂ R and N ∈ Z>0 form a subgroup C(R)Z ⊂ C(R) whose index is bounded by the following statement, for which we provide a simple proof; this also follows from [7, Lem. 6]. Lemma 2.6. We have C(R)2 ⊂ C(R)Z , therefore [C(R) : C(R)Z ] | #C(R)[2]. The Shimura class group fits into the following exact sequence: 1→ −

NK/K0 (R0× )+ u 7→ [(R,u)] [(a,µ)] 7→ [a] −−−−−−−−→ C(R) −−−−−−−−→ Cl(R) −−−−→ Cl+ (R0 ), NK/K0 (R× )

(2)

where R0 = R∩K0 , (R0× )+ is the subgroup of totally positive units, and Cl+ (R0 ) is the narrow class group (which, as we recall, is the group of invertible fractional 5

ideals modulo the subgroup of principal fractional ideals admitting a totally positive generator). For instance, this implies that #C(R)[2] ≤ # Cl(R)[2] · U with U = [(R0× )+ : NK/K0 (R× )] ≤ 2g−1 , where the last bound arises as in the proof of Lemma 2.4. Under mild conditions, the last map is surjective. For example, this is true if R = ZK and at least one prime ideal of R0 ramifies in K [9, Proof of Thm. 3.1] (that theorem also states that if g = 2 then this can only fail if Gal(K, Q) ∼ = C2 × C2 ). So the Shimura class number h(R) = #C(R) can often be computed as h(R)U/h+ (R0 ). An algorithm for computing Shimura class groups was described in [40, §4] (implemented in PARI/GP). We are now ready to state our main theorem of interest: Theorem 2.7. Assume that the set Mk (R) is non-empty. There is a free action C(R) × Mk (R) → Mk (R) : ( [(a, µ)], (A, λ, ι) ) 7→ [(a, µ)] ⋆ (A, λ, ι). It can be assumed w.l.o.g. that a ⊂ R and has norm coprime to p, in which case the image arises as the codomain of an ι(µ)-isogeny with kernel ∩x∈a ker ι(x). At this point we make no claims on the orbits of the action. This is discussed in Section 6.

3

First examples of superspecial CM orientations

The focus of our paper lies on the case of superspecial abelian varieties (and surfaces in particular). The easiest way to generate a g-dimensional PPAV that is oriented by a CM field K of degree 2g is by considering A = E g , for some supersingular elliptic curve E, equipped with the product polarization λ. The curve E admits an isomorphism ϑ : O → End(E) from a maximal order O in the unique definite quaternion algebra Bp,∞ over Q that is ramified at p. By component-wise application we obtain an isomorphism ϑ : Mg (O) → End(A) that we denote by the same letter. Therefore giving a K-orientation on (A, λ) is the same as giving an embedding ι : K ,→ Mg (Bp,∞ ) such that ι(ᾱ) = ι(α)∗ for all α ∈ K; here ∗ denotes conjugate-transpose, which under ϑ indeed corresponds to the Rosati involution on A according to Example A.3. For a CM order R ⊂ K, a primitive R-orientation is then a K-orientation mapping R into Mg (O), in such a way that ι(α) ∈ / Mg (O) for any α ∈ K \ R. Example 3.1. Let p ≡ 3 mod 4 and consider the elliptic curve E : y 2 = x3 − x over Fp2 , which is supersingular. Fix a square root i ∈ Fp2 \ Fp of −1. Consider A = E 2 equipped with the product polarization λ. It is well-known that ϑ : i 7→ ( (x, y) 7→ (−x, iy) ), j 7→ πp establishes an isomorphism between the maximal order O = Z⟨1, i, (1+j)/2, (i+k)/2⟩ ⊂ Bp,∞ and End(E). Assume that m = p+4 and d = (p + 1)/4 are coprime, square-free integers. We claim that ι :

1+

√ 2

−m

 1+j 7→

2

i

i 1+j 2

6

√

 ,

 d 7→

0 1−j 2

1+j 2

0



√ √ is a primitive R-orientation on (A, λ), where R = Z[(1 + −m)/2, d]; as above we identify elements of M2 (O) with their images in End(A) under ϑ. If we denote the two matrices by M and D, then in order to verify that this indeed concerns a CM orientation, the key properties to check are that – M and D commute, – M 2 − M + (m + 1)/4Id2 = 0 and D2 − dId2 = 0, – M ∗ = 1 − M and D∗ = D, which is easily done. To verify primitivity, note that if d ̸≡ 1 mod 4 then R = ZK (this follows, e.g., from [62, p. 68]), in which case primitivity √is automatic. To / M2 (O). cover the case d ≡ 1 mod 4 it is enough to observe that ι((1 + d)/2) ∈ As a toy example, √ letting p = 103 √ we find m = 107 and d = 26. Using that the fundamental unit 26 + 5 of Q( 26) is not totally positive and that 107R0 ramifies in K,6 from (2) we see that the sequence NK/K

[(a,µ)] 7→ [a]

0 1→ − C(R) −−−−−−−−→ Cl(R) −−−−→ Cl+ (R0 ) → − 1

is exact. With the use of Magma or SageMath one then verifies that C(R) has order 42 and is generated by the classes of  √  √ √
s = (7, −107 26 − 2), 7 t = (3, −107 − 1), 3 , (and cyclically generated by the class of their product st). Then, for instance, using the (3, 3)-isogeny formulae from [11] one calculates that [t] ⋆ (A, λ, ι) = (Jac(H), λ1 , ι1 ) where H : y 2 = 102x6 + 25x5 + 57x4 + 4x3 + 41x2 + 46x + 14 and λ1 is the canonical principal polarization on Jac(H), and where ι1 denotes the push-forward orientation (which we do not spell out here). See Section 4.3 for more details on how to evaluate the Shimura class group action in practice. Example 3.2. Now assume that moreover d = a2 +b2 for certain integers a, b ∈ Z (e.g., 26 = 52 + 12 in the toy example). Since d is square-free we can assume that b is odd. Then a similar reasoning shows that √     √ 1 + −m 0 a b i + 1+j 2 ι′ : d → 7 7→ , b −a 0 i + 1+j 2 2 is another R-orientation on √(A, λ). It is always primitive because using that b is odd one sees that ι′ ((1 + d)/2) ∈ / M2 (O). In Example 6.4 we will argue that (A, λ, ι) and (A, λ, ι′ ) cannot lie in the same orbit under the action of C(R). Example 3.3. Away from products, let p ̸= 2, 5 and consider the genus-2 curve C : y 2 = x5 − 1 together with its Jacobian A = Jac(C), equipped with the canonical polarization. This PPAS is superspecial if and only if p ≡ 4 mod 5. For the CM order R = Z[ζ5 ] we have a primitive orientation ι : R ,→ End(A) sending ζ5 to the automorphism of A induced by C → C : (x, y) 7→ (ξ5 x, y); here ζ5 , ξ5 denote primitive 5-th roots of unity in C and k, respectively. 6

It can in fact be argued that the existence of a ramifying prime follows from the fact that the fundamental unit is not totally positive.

7

Example 3.4 (R2-D2). We fix a supersingular elliptic curve E/Fp2 for which πp2 = −p and let (A, λ) be its Weil restriction, i.e., A = WFp2 /Fp (E) ∼ =F̄p E × E (p) equipped with the product polarization. We choose E such that it comes equipped with an explicit isogeny τ : E → E (p) , satisfying τ̂ ◦ πp = πp ◦ τ , of square-free degree d not a multiple of p. Such curves were studied in [22] and a method for finding large examples can be found in [16, §5]. Then, an orientation is given by √ √ √ ι : Q( d, −p) → End0 (A) : d 7→



   0 τ̂ √ 0 πp , −p 7→ Πp = , τ 0 πp 0

where we note that Πp is the p-th power Frobenius endomorphism on A. These matrices are fixed, resp. negated, under the Rosati involution (= conjugatetranspose), they square to d, resp. −p, and they commute, so this is a welldefined√field embedding. It typically √ concerns a primitive R-orientation with √ √ R = Z[ d, −p]. Indeed, clearly (1 + d)/2, (1 + √ −p)/2 do not map to endomorphisms, so the only concern is whether (1 + −dp)/2 maps to an endomorphism. This concern √ is void if −dp ̸≡ 1 mod 4 (true for the parameters from [16]) because then (1 + −dp)/2 is not an algebraic integer. In general, one can verify that the orientation is primitive if and only if (1 + πp ◦ τ )/2 ∈ / End(E). In the above examples, the primitivity of the orientation was easily established. In general, however, finding the primitive order R = ι−1 End(A) from a description of ι on a suborder R′ ⊊ R may be a very hard problem. Indeed, this is similar to computing the endomorphism ring of an ordinary abelian surface A over a finite field Fq from its Frobenius order Z[πq , π̂q ], for which no efficient algorithms are available [6]. Remark 3.5. R2-D2 is part of a larger family of orientations called R2, discussed in Appendix C. The suffix D2 refers to the Galois group D2 ∼ = C2 × C2 of K = Frac(R) over Q. Remark 3.6. In Section 5 we will develop the theory of CM orientations on the algebraic side of the IKO correspondence. Within that framework, we will discuss an easy technique for producing superspecial PPASs together with a prescribed CM orientation, see Section 5.3. In Appendix C we will put Example 3.4 inside the larger family of explicit Fp -rational orientations that we call R2.

4

Evaluating the Shimura class group action

In this section we describe the main auxiliary tools needed for cryptographic applications of the Shimura ideal class group action on oriented superspecial PPAVs in the g-REGA model (e.g., non-interactive key exchange). 8

4.1

On the generating set g

As mentioned in Section 2.2, we will act with C(R)Z in practice. Recall that this may be a strict subgroup of the full Shimura class group (but when choosing parameters carefully, equality may be enforced). We refer the reader to Section 5.2 for how to act with elements of C(R) \ C(R)Z in dimension g = 2, but this method requires knowledge that is not available to Bob when extracting the shared secret from Alice’s public key, and vice versa. Similar to class group actions like CSIDH [17] and SCALLOP [35], we choose the elements of our generating set g to be representable by Shimura ideals (a, ℓ) for small odd primes ℓ ∤ disc R,7 and we collect enough (yet polylogarithmically many) such ideals for these to generate C(R)Z with overwhelming probability (heuristically). Note: the inverse of [(a, ℓ)] is represented by (a, ℓ). In Appendix D we prove that, in dimension g = 2, the options for a are the following. Lemma 4.1. For a given CM order R of degree 4 and a prime number ℓ ∤ disc R there exists an ideal a ⊂ R such that (a, ℓ) ∈ IR if and only if ℓR splits as either ℓR = p1 p1 p2 p2

or

ℓR = pp

(3)

for degree-1 prime ideals p1 , p2 , resp., a degree-2 prime ideal p. The corresponding options for a are p1 p2 , p1 p2 , p1 p2 , p1 p2 , resp., p, p. One sees that if ℓ splits completely then we obtain two pairs l, l−1 , l′ , l′−1 ∈ C(R)Z , while if ℓ splits into two complex-conjugate primes, we end up with one pair l, l−1 ∈ C(R)Z . E.g., this means that if we consider a set of primes ℓ1 , . . . , ℓr that split completely along with the corresponding set g = {l1 , l′1 , . . . , lr , l′r }, then the number of expressions of the form ′e′

′e′

|ei |, |e′i | ≤ B

le11 l1 1 · · · lerr lr r ,

(4)

for some bound B ∈ Z≥0 equals (2B +1)2r , potentially yielding the same amount of elements of C(R)Z . More generally, for arbitrary g, we end up with 2g−1 pairs in the completely split case, hence g−1

(2B + 1)r2

many expressions. This growing “key space” for fixed r and B is one of the features of working in higher dimension. Remark 4.2. The asymptotic proportions of primes factoring as in (3) depend on Gal(L, Q) where L denotes the Galois closure of K. Using Chebotarev’s density theorem, one checks that these proportions are given by 41 , resp. 12 , in the case C2 × C2 , by 14 , resp. 0, in the case C4 , and by 81 , resp. 14 , in the case D4 . In practice, see e.g. Appendix F, we can bias this in our favor and choose parameters such that as many small primes ℓ as possible split completely. 7

This is a convenient assumption but it can be relaxed, to allow for horizontal isogenies coming from ramified primes; since this adds technicality while not adding much to C(R) (the corresponding ideal classes have very small order), we omit this.

9

In order to find the factorization of ℓR, one can look for an order Z[γ] ⊂ R (i.e., a monogenic suborder) such that every element of R can be written as a Q-linear combination of 1, γ, . . . , γ 2g−1 without denominators that are 0 mod ℓ (e.g., this is true as soon as ℓ ∤ [R : Z[γ]]). Writing f (x) ∈ Z[x] for the minimal polynomial of γ, the factorization of ℓR can be obtained from that of f (x) mod ℓ. For g = 2 the details are as follows; it is convenient to precompute8 r := γ1 γ̄1 + γ2 γ̄2 ∈ Z, where γ1 = γ, γ̄1 , γ2 , γ̄2 ∈ C are the roots of f (x). – If f (x) ≡ f1 (x)f2 (x) mod ℓ for irreducible quadratic factors fi (x) such that f1 (0) + f2 (0) ≡ r mod ℓ then ℓR = pp with p = (ℓ, f1 (γ)). – If f (x) factors completely mod ℓ then we label the roots as a1 , b1 , a2 , b2 of f (x) mod ℓ in such a way that r ≡ a1 b1 + a2 b2 mod ℓ. Then we can conclude that ℓR = p1 p1 p2 p2 with pi = (ℓ, γ − ai ) for i = 1, 2. The C2 × C2 case. There is an alternative way of describing an “easy” generating set g in the case of a CM field K with Gal(K, Q) ∼ = C2 × C2 , even though this time the group generated by g may be a strict subgroup of C(R)Z (but of very small index). The starting point is that K has three quadratic subfields: the real field K0 and two imaginary fields K1 , K2 . We let Ri = R ∩ Ki for i = 1, 2. It is then natural to consider the following map: κR : Cl(R1 )×Cl(R2 ) → C(R) : ([a1 ], [a2 ]) 7→ [((a1 R)(a2 R), NK1 /Q (a1 )NK2 /Q (a2 ))], seen as taking values in C(R)Z . In Lemma 4.3 below we argue that this group homomorphism is close to being an isomorphism (at least in the case R = ZK ). We can then build g from a set of “easy” ideal classes [m1 ], [m2 ], . . . , [ms ] ∈ Cl(R1 ),

[l1 ], [l2 ], . . . , [lt ] ∈ Cl(R2 ),

e.g., as chosen in CSIDH or SCALLOP, by letting it be the collection of images of ([mi ], 1), i = 1, . . . , s and (1, [li ]), i = 1, . . . , t. Lemma 4.3. Assume that K is a C2 × C2 CM field, and let K0 be the real quadratic subfield and K1 , K2 the imaginary quadratic subfields. If Z× K contains no roots of unity other than ±1, then | ker κZK | ≤ | coker κZK | ≤

1 2q(K)

Y

e(ℓ),

ℓ prime

Y 1 | coker NK/K0 | e(ℓ), 4q(K) ℓ prime

× where q(K) = [Z× K : ZK0 ] ∈ {1, 2}, e(ℓ) is the ramification index of a prime ℓ in K, and NK/K0 : Cl(ZK ) → Cl+ (ZK0 ) denotes the ideal class norm map. 8

An elegant way of computing r directly from f (x) is through its cubic resolvent: in cases C4 , D4 it concerns the unique integer root of the cubic resolvent, while in the C2 × C2 case it can be characterized as the largest root; see [26].

10

Proof. The proof follows from results by Lemmermeyer [64] and the exact sequence (2). We refer to Appendix E for all the details. ⊔ ⊓ As mentioned in Section 2.2, a sufficient condition for | coker NK/K0 | = 1 is that the extension K/K0 ramifies at a prime of K0 . A theorem characterizing such C2 × C2 fields can be found in [92, Thm. 2]. We note that when R is not a maximal order, a similar bound on ker κR can also be proven (see Corollary E.1 in Appendix E). We expect that a similar bound on the cokernel also holds for κR , but the proof seems less straightforward. 4.2

Kani’s lemma with CM

In Section 4.3 we will use the machinery of higher-dimensional isogeny representations for the purpose of representing orientations. Let us quickly revisit the case of a polarized isogeny φ : A1 → A2 between PPAVs of dimension g, of reduced degree d ∈ Z>0 . The higher-dimensional representation of φ exploits Kani’s lemma [53] to encode φ into a higher-dimensional isogeny Φ of smooth reduced degree N , so that Φ, and hence φ, can be evaluated using a chain of isogenies of small degree. The classical method makes use of an auxiliary matrix α with entries in Z, coming from an expression of n := N − d as a sum of u = 1, 2, 4 squares (see [84, Prop. 5.15]); by Lagrange’s theorem, u = 4 always succeeds. For the purpose of representing orientations, we wish to generalize this to the setting where A1 and A2 have an explicit R-orientation for some CM order R in a CM field K of degree 2g. Two things change. First, the auxiliary matrix may be taken with entries in R rather than in Z, and so the condition on n becomes about relative norms of elements of R rather than about sums of integer squares. Second, the d-isogeny φ does not necessarily have d ∈ Z>0 , as d can be any element of R0+ = R0 ∩ K0+ , i.e., any totally positive element of R0 . Theorem 4.4. Let (A1 , λ1 , ι1 ) and (A2 , λ2 , ι2 ) be R-oriented PPAVs of dimension g, and let φ : (A1 , λ1 , ι1 ) → (A2 , λ2 , ι2 ) be an R-oriented d-isogeny with d ∈ R0+ . Let n ∈ R0+ be such that N := d+n ∈ Z, and let α = (αj,k )1≤j,k≤u ∈ Mu (R) be such that α∗ α = n Idu , where α∗ denotes the conjugate-transpose of α. Write αAi = ιAi (α) := (ιi (αj,k ))1≤j,k≤u ∈ End(Aui ). Then ! † φ Idu αA ×u ×u ×u u u 2 Φ= : (Au1 × Au2 , λ×u 1 × λ2 ) → (A2 × A1 , λ2 × λ1 ) −αA1 φ† Idu is an N -isogeny of PPAVs of dimension 2ug; in particular Φ† Φ = [N ] and deg Φ = N 2ug . Moreover: (i) φ = ϱ ◦ Φ ◦ ȷ, where ȷ : A1 → Au1 × Au2 is the inclusion of the first factor and ϱ : Au2 × Au1 → A2 is the projection onto the first factor; (ii) if the ideals dR0 and nR0 are coprime in R0 and N is coprime to the base field characteristic, then † ker Φ = {(−αA (P ), φ Idu (P )) | P ∈ Au1 [N ]} 1

= {(ι1 (d)Idu (P ), αA2 φ Idu (P )) | P ∈ Au1 [N ]}. 11

Remark 4.5. Point (ii) of Theorem 4.4 describes ker Φ in terms of the action of φ on A1 [N ], so the images of the 2g points in a basis of A1 [N ] are enough to determine Φ. Assuming √ that N is a square, less than that actually suffices: the action of φ on A1 [ N ] already determines Φ, by the meet-in-the-middle technique of [86, §6.4], which we detail further in Remark D.1. To apply Theorem 4.4 one has to produce, for a prescribed n ∈ R0+ , a matrix α ∈ Mu (R) such that α∗ α = nIdu , and one wants u as small as possible since Φ is an isogeny between abelian varieties of dimension 2ug. As mentioned, if n ∈ Z>0 then one can construct α ∈ Mu (Z) with u = 1, 2, 4 in the cases where n is a sum of 1, 2, 4 integer squares. A similar technique applies if n ∈ R0+ is a sum of squares of elements in R0 : in [85, Lem. 4.2], Robert gives solutions for α ∈ M2k (R0 ) when n is a sum of m squares, for some k ≥ ⌈log2 m⌉ Pm−1 where equality can be assumed if m ≤ 8. E.g., for n = i=0 ϑ2i with ϑi ∈ R0 the solutions for m = 1, 2, 4 are   ϑ0 ϑ1 ϑ2 −ϑ3   −ϑ1 ϑ0 ϑ3 ϑ2  ϑ 0 ϑ1  α = (ϑ0 ), α= , α= (5) −ϑ2 −ϑ3 ϑ0 −ϑ1  . −ϑ1 ϑ0 ϑ3 −ϑ2 ϑ1 ϑ0 There is no guarantee that n ∈ R0+ can always be written as a sum of squares in R0 , and if it can, more than 4 squares might be needed. A theorem by Siegel [90, Thm. 1] states that all totally positive integral elements of a totally real √ number field K0 are a sum of integral squares only when K0 = Q or K0 = Q( 5). Peters showed that if a totally positive integral element n of a real quadratic field is a sum of integral squares, then it is a sum of at most 5 integral squares, and gave an explicit criterion to detect such n [81, Sz. 2]. In the following, we give solutions for α ∈ Mu (R) in the cases where n is a sum of k + 1 relative norms of elements of R, in which case one can always take u = 2k , and in the cases where n is a sum of t relative norms of elements of R and m = 2d squares in R0 , in which case one ends up with u = 2k+t with k ≥ d as above. These solutions are more general than what is required for our applications in Section 4.3, but they are of independent interest, and do specialize to meet our needs. Proposition 4.6. Let X, Y ∈ Mm (R) and set   X Y∗ α= ∈ M2m (R). −Y X ∗ (a) If X ∗ X = XX ∗ = x Idm and Y ∗ Y = Y Y ∗ = y Idm for some x, y ∈ R0 , and if XY = Y X, then α∗ α = αα∗ = (x + y) Id2m . (b) Conversely, for arbitrary X, Y ∈ Mm (R) and n ∈ R0 one has α∗ α = n Id2m if and only if XY = Y X,

X ∗ X + Y ∗ Y = XX ∗ + Y Y ∗ = n Idm . 12

(c) Let k ∈ Z≥0 and ϑ0 , . . . , ϑk ∈ R. Define α0 := (ϑ0 ) ∈ M1 (R) and, for 1 ≤ i ≤ k,   αi−1 ϑ̄i Id2i−1 ∈ M2i (R). αi := ∗ −ϑi Id2i−1 αi−1 Pk Then αk∗ αk = n Id2k with n = i=0 NK/K0 (ϑi ). In particular, if n is a sum of k + 1 relative norms of elements of R there is a matrix α ∈ M2k (R) such that α∗ α = nId2k . (d) Let d, t ∈ Z≥0 and let m = 2d . Consider ϑ0 , . . . , ϑm−1 ∈ R0 . Let α0 ∈ Pm−1 M2k (R0 ) such that α0∗ α0 = α0 α0∗ = n1 Id2k with n1 = i=0 ϑ2i , for k ≥ d as P t above. Consider ϑ′1 , . . . , ϑ′t ∈ R and let n2 = i=1 NK/K0 (ϑ′i ). Define, for 1 ≤ i ≤ t,   αi−1 ϑ̄′i Id2k+i−1 αi := ∈ M2k+i (R). ∗ αi−1 −ϑ′i Id2k+i−1 Then αt∗ αt = (n1 + n2 )Id2k+t . In particular, if n is a sum of t relative norms of elements of R and m = 2d squares of elements in R0 , there exists a matrix α ∈ M2k+t (R) such that α∗ α = nId2k+t . Proposition 4.6(d) reduces to [85, Lem. 4.2] when n2 = 0, which a priori only offers a solution α ∈ M2k (R0 ) but it is clear that if n1 is a sum of squares in Z then also α ∈ M2k (Z) (as is apparent from (5) for k = d = 0, 1, 2). 4.3

Representing the orientation

Usage. Let (A, λ) be a g-dimensional PPAV together with a primitive orientation ι : R → End(A) by a CM order R of rank 2g. Say we want to act on (A, λ, ι) with a Shimura ideal of the form ((ℓ, f1 (γ)), ℓ), for a suitable γ ∈ R generating K/Q and a suitable degree-g polynomial f1 (x) ∈ Z[x]; that is, a Shimura ideal of the kind described in Section 4.1. Following the proof of Theorem 2.7, this amounts to computing the subgroup  g Z H := A[ℓ] ∩ A[f1 (ι(γ))] ∼ , = ℓZ which is maximal isotropic with respect to the ℓ-Weil pairing. Generators for H can be obtained from the kernel of a matrix of f1 (ι(γ)) acting on A[ℓ]. Remark 4.7. This can be sped up by using that H equals the image of f2 (ι(γ)) on A[ℓ], where f2 (x) denotes the cofactor of f1 (x) in the factorization of the minimal polynomial f (x) of γ. This generalizes an optimization that is well-known in the elliptic curve setting, see e.g. [16, §3.2]. The result of the action is then the codomain of an ℓ-isogeny with kernel H, equipped with the induced principal polarization and the push-forward orientation. For this approach, it is crucial to be able to evaluate ι(γ) on arbitrary ℓ-torsion points. Thus, we need to represent the orientation in a way that is both compact and allows the user to evaluate it efficiently. 13

Remark 4.8. As a side remark, observe that we can act with ((ℓ, f1 (γ)), ℓ) without knowing what R is, as long as γ ∈ R. One could hope to thwart Kuperberg’s attack [23,58] on the vectorization problem on C(R) by keeping R secret and just providing γ: as mentioned at the end of Section 3, extracting the primitive order R from a non-primitive orientation (by Z[γ] in this case) might indeed be an intractable problem. Interestingly, this countermeasure was proposed by Sanon [88, pp. 107–108], albeit in the context of ordinary PPAVs oriented by Frobenius. But it does not provide the hoped-for security: determining the stabilizer S of the (non-free) action by Z[γ] is an abelian hidden subgroup problem, which is solved in polynomial time using Kitaev’s algorithm [54]. One then has a free action by C(Z[γ])/S which can be targeted using Kuperberg’s algorithm. Higher-dimensional representation. Let us first assume that we can efficiently evaluate endomorphisms coming from R0 . Then, in order to represent ι(γ), the routine approach, whose elliptic curve counterpart was first described in SCALLOP-HD [21], would be as follows: write d = γγ ∈ R0+ and suppose that we can find a smooth integer N , ideally a power of 2, such that N − d can be effectively written as a sum of s squares of elements of R0 .9 Then using the auxiliary matrix α ∈ Mu (R0 ), u = 2⌈log2 s⌉ from Proposition 4.6(d), we can embed ι(γ) in an N -isogeny between PPAVs of dimension 2ug as outlined in Theorem 4.4. This is an endomorphism of A2u , in fact. This endomorphism can be computed from interpolation data for ι(γ), i.e., from the point pairs P, ι(γ)(P ) with P running over a basis of A[N ]. Recall from Remark 4.5 that if N is a square then using Robert’s √ meet-in-the-middle technique it suffices to provide interpolation data on A[ N ]. When evaluating the action, this interpolation data can be pushed through: if φ : A → A/H is a horizontal isogeny of degree coprime to N , then the point pairs φ(P ), φ(ι(γ)(P )) form a valid set of interpolation points for (φ∗ ι)(γ).10 √ Halving the ambient dimension. In the common scenario where γ = −d and N − d is a sum of at most 3 squares of elements of R0 , we can reduce the ambient dimension to ug. This observation seems new even for g = 1. To see this, let α be as in (5), where in the case of 3 squares we let ϑ2 = 0, i.e., N − d = ϑ20 + ϑ21 + ϑ23 . Define √ – ξ := √−d + α if u = 1 (i.e., N − d is the square of an element of R0 ), – ξ := −d · diag(1, −1) + α if u = 2 (sum of two squares), 9

If N − d is not a sum of squares then one can retry with a different N or γ; see our paragraph on representing R0 at the end of this section for a workaround. 10 In applications, this interpolation data must be masked using a change of basis for security reasons. In practice, one changes to a deterministic basis of A[N ] (or of √ A[ N ] in the case of meet-in-the-middle) for reasons of data compression, and this handles the security issue at once.

14

– ξ :=

√

−d · diag(1, −1, 1, −1) + α if u = 4 (sum of 3 squares and ϑ2 = 0).

One then checks that ιA (ξ) is a polarized endomorphism of Au of reduced degree N . If we can evaluate this endomorphism at any point of Au , then we can also evaluate ι(γ) at any point of A, assuming we know how √ to evaluate ιA (α). It is easy to see that the interpolation points φ(P ), φ(ι( −d)(P )) can be used to determine the kernel of ι(ξ). The method remains compatible with meet-in-the√ middle: if the interpolation data is restricted to A[ N ] then this remains good √ enough to compute “half the kernel”, i.e., ker(ι(ξ)) ∩ Au [ N ]. But the data can also√be used to compute half the kernel of the Rosati dual, i.e., ker(ι(ξ ∗ )) ∩ Au [ N ], allowing one to complete the path as wanted. Observe that the case u = 1 avoids the need for working in higher dimension altogether; for g = 1 this essentially specializes to the non-HD versions of SCALLOP [35,2]. Representing R0 . We now return to the problem of representing √ endomorphisms coming from R0 . In dimension g = 2 where K0 = Q( c) for some square-free c ∈ Z>0 , one can√ proceed by finding a smooth-degree representation of the endomorphism ι( c), which is a c-isogeny, using the methods from the previous paragraph but where now α ∈ Mu (Z). In the special case where c = p, this is actually not needed: here the representation comes for free, see the next Section 4.4. In arbitrary dimension, the most robust solution seems to be circumventing the problem and looking for some γ ∈ R generating K/Q such that γγ ∈ Z, so that the methods from the previous paragraph can be run over Z right away. The existence of such an element γ is not a strong condition on R.11 E.g., if R = ZK then any element of the form (β/β̄)NK/Q (β) does the job, as long as β/β̄ generates K/Q. Moreover, by ensuring that NK/Q (β) is smooth, one gets for free that γγ = NK/Q (β)2 is smooth as well, again avoiding all need to go to higher dimension. However, this typically leads to generators γ having a large norm (corresponding to ι(γ) having a large degree), and it gives little control over [R : Z[γ]], meaning we potentially lose many small primes ℓ that could have been used to compute the Shimura class group action. 4.4

Instantiating key exchange over Fp

In Appendix F we describe concrete key exchange protocols built from Shimura class group actions on superspecial PPASs. These are built from the R2 family of orientations: R2-D2 was described in Example 3.4, while R2-C4 and R2-D4 will be discussed in Appendix C. A common feature of these orientations is that all PPASs and isogenies involved when computing the action are defined over Fp and the p-th power Frobenius endomorphism Πp is in the image of ι. This choice is motivated by CSIDH [17], where working with the Frobenius orientation on supersingular elliptic curves comes with three distinguishing features: (i) the 11

Note that on PPAVs over a finite field Fq one always has πq π̂q = q, so in the simple, ordinary case (where πq generates the endomorphism algebra) one can simply work with Frobenius.

15

fact that every curve E in the orbit is defined over Fp makes for a more compact object; (ii) the orientation does not need representation, because the Frobenius endomorphism is always known explicitly; (iii) it is easy to choose parameters ensuring the splitting of many small primes ℓ (as well as control the field of definition of the points in a corresponding kernel). In higher dimension, these features remain partially present: – One can no longer avoid the need for representing the orientation altogether, but at least the Frobenius part of the orientation still comes for free. E.g., in the R2-D4 and R2-C4 orientations described in Appendix C, where √ √ K0 = Q( p) and ι( p) = Π √p , this removes the need for representing an endomorphism of the form ι( c), c ∈ Z>0 , overall making for a more compact orientation representation. Moreover, the Fp -rationality can be exploited to compress this data further: this is explained in Appendix G. √ – In all R2 orientations we have Q( ±p) ⊂ K, so by choosing ±p to be a quadratic residue mod ℓi for small primes ℓ1 , . . . , ℓr we roughly double the chance that ℓi splits completely (from 14 to 12 in cases C2 × C2 , C4 and 81 to 41 in case D4 ). Moreover, parameter generation is flexible enough to boost those chances further; e.g., see our approach to R2-D4 taken in Appendix F.1. Remark 4.9. There may be reasons to stay away from Frobenius orientations, e.g., for more control over #C(R) or more flexibility in choosing parameters, as in the SCALLOP family [35,21,2] (a general technique for constructing such orientations in dimension g = 2 will be outlined in Section 5.3). In the C2 × C2 case, there is another very good reason for avoiding Frobenius orientations: based on a preliminary version of the current paper, the authors of [50] observed that the vectorization problem a CM √ √ for R2-D2, which we recall is an orientation by√ order of the form Z[ d, −p], reduces to vectorization problems in Cl(Z[ −p]) √ and Cl(Z[ −dp]). This relies on a twisting trick akin to [18,96] and, as far as we are aware, does not obviously generalize to arbitrary C2 × C2 orientations, because it depends on a property that is specific to cases where p ramifies in K, namely that twists coming from “inequivalent CM types” can nevertheless end up in the same orbit; see Section 6, and Example 6.12 in particular. For the sake of reference, we have still included (a shortened version of) our R2-D2-based key exchange protocol in Appendix F.2.

5

CM orientations under the IKO correspondence

The IKO framework, introduced in [49], gives a convenient Deuring-like dictionary between the geometry of superspecial PPASs over Fp and their connecting isogenies on one hand, and the algebra of positive definite invertible matrices in M2 (Bp,∞ ) and their “connecting matrices” on the other hand. The goal of this section is to incorporate CM orientations and Shimura class group actions in this framework and provide applications. Omitted proofs can be found in Appendix H. Note: in this section the letter g is used to denote an IKO matrix, rather than the dimension of an abelian variety, which is assumed 2 throughout. 16

5.1

The IKO correspondence: a slight extension

Fix a supersingular elliptic curve E in characteristic p > 0 along with an isomorphism ϑ : O → End(E) from some maximal order O ⊂ Bp,∞ , as at the beginning of Section 3. By Deligne’s theorem [41] any superspecial PPAS is isomorphic to (A, λ) for some principal polarization λ : A → A∨ on A = E 2 . Let λ0 denote the product polarization. Then the automorphism λ−1 0 ◦ λ corresponds under ϑ (when applied component-wise) to some totally positive Hermitian norm-1 matrix, i.e.,   sr g= , s, t ∈ Z>0 , r ∈ O, st − rr̄ = 1; r̄ t see also Example A.5. We call g the g-matrix or IKO-matrix associated with (A, λ). To identify equivalent principal polarizations λ, λ′ , i.e., for which (A, λ) ∼ = (A, λ′ ), one should work with g-matrices up to equivalence, where we say g ′ ∼ g if and only if g ′ = u∗ gu for some u ∈ GL2 (O). Since we are just considering A with different principal polarizations, we always have End(A) ∼ = M2 (O) and the piece of data that varies with λ is the Rosati involution. We know that the Rosati involution for the product polarization λ0 is just conjugate-transpose b 7→ b∗ . In general, for a superspecial PPAS corresponding to a matrix g, the Rosati involution is b 7→ b† = g −1 b∗ g which follows from the definition of the g-matrix and the definition of the Rosati involution. In that respect, superspecial surfaces can also be characterized by positive involutions on M2 (O). Isogenies are incorporated in the IKO correspondence as follows. Let λ1 , λ2 be principal polarizations on A with g-matrices g1 , g2 and let µ ∈ M2 (O) be a matrix fixed by the Rosati involution with respect to g1 that is totally positive, i.e., the (necessarily real) roots of its minimal polynomial over Q are positive. Then γ ∈ M2 (O) corresponds (under ϑ) to a ϑ(µ)-isogeny (A, λ1 ) → (A, λ2 ) if and only if d ◦ λ2 ◦ ϑ(γ) ⇔ λ−1 ◦ λ1 ◦ ϑ(µ) = λ−1 ◦ ϑ(γ) d ◦ λ0 ◦ λ−1 ◦ λ2 ◦ ϑ(γ) λ1 ◦ ϑ(µ) = ϑ(γ) 0 0 0 ⇔ g1 µ = γ ∗ g2 γ. This (slightly) extends the corresponding calculation from [13, §2.3], which was restricted to µ = N Id2 for positive integers N . Remark 5.1. For γ = Id2 we have the following identity as a special case: g1 Id2 = Id∗2 g1 Id2 . An interesting aspect of this trivial equation is that it says both that (A, λ1 ) and (A, λ1 ) are 1-isogenous (trivially), and that (A, λ0 ) and (A, λ1 ) are ϑ(g1 )-isogenous. Since this reasoning applies to arbitrary g1 , this shows the great impact of the choice of µ (e.g., when specified as the second component of a Shimura ideal) on the resulting codomain as a PPAV. So this means that if λ1 is a principal polarization on A with g-matrix g1 and if H ⊂ A is a finite subgroup that is maximal with the property that eϑ(µ) (P, λ1 (Q)) = 1, 17

∀P, Q ∈ H,

then a g-matrix for the induced principal polarization on A ∼ = A/H is g2 := γ −∗ g1 µγ −1 , with γ ∈ M2 (O) any matrix such that ker ϑ(γ) = H. This follows, e.g., from Proposition A.4. In particular, g2 is necessarily a valid g-matrix, i.e., a positivedefinite Hermitian matrix of norm 1 contained in M2 (O). Remark 5.2. Most of these properties are easily confirmed: – Using µ† = g1−1 µ∗ g1 one checks that g2∗ = g2 . – By definition of a ϑ(µ)-isogeny, the degree of ϑ(µ) equals the squared degree of ϑ(γ), hence in view of [14, Lem. 2.10] we see that g2 has norm 1. – It concerns a positive-definite matrix: for this it suffices to see that γ ∗ g2 γ = g1 µ is positive-definite, and this in turn follows from the total positivity of µ and the fact that after base-changing to Bp,∞ ⊗Q C ∼ = M2 (C) if needed one can rewrite g1 µ = h(h∗ µh)h−1 with hh∗ = g1 . The existence of such an h follows from Cholesky decomposition, which we have included as Lemma 5.3 below. Verifying that g2 ∈ M2 (O) in an elementary way is more intricate. For instances of H that arise as the kernel of a Shimura ideal, such a verification can be found in Appendix H.1; see also Remark 5.5. Lemma 5.3 (Cholesky decomposition in M2 (Bp,∞ )). Let g ∈ M2 (Bp,∞ ) be a positive-definite Hermitian matrix, i.e., g = g ∗ and its (necessarily real) eigenvalues are positive. Then there exists h ∈ M2 (Bp,∞ ) such that hh∗ = g. 5.2

Orientations of g-matrices and the Shimura class group action

Let K be a quartic CM field and let R ⊂ K be a CM order. We now describe K-oriented superspecial PPASs (A, λ, ι) within the framework of the IKO correspondence, where as above we assume A = E 2 . Let g be the g-matrix associated with λ and let ι : R ,→ End(A) ∼ = M2 (O) be a primitive orientation. Write R0 = Z[a] for some real generator a and R = R0 [b1 , b2 ] for generators bi ∈ R.12 Upon identifying a, b1 , b2 with their images under the orientation, we can think of them as commuting elements of M2 (O) satisfying g −1 a∗ g = a and g −1 b∗i g ∈ R for i = 1, 2. We refer to the tuple g, a, b1 , b2 ∈ M2 (O) as algebraic data associated with (A, λ, ι). Theorem 5.4. Assuming the generalized Riemann hypothesis (GRH), there is a polynomial-time algorithm which upon input of – algebraic data g, a, b1 , b2 of an oriented superspecial PPAS (A, λ, ι), 12

In many cases one can do with a single generator bi : this is true if and only if R is a free R0 -module. E.g., for this it suffices that R0 is maximal and h(K0 ) = 1.

18

– an integral Shimura ideal (a, µ) of Z[a, b1 , b2 ] such that p ∤ N (a),13 returns algebraic data of the codomain of the corresponding ι(µ)-isogeny, equipped with the induced principal polarization and orientation. Proof. The endomorphisms that vanish on the kernel of a form a left ideal of M2 (O) generated by the elements of a. A generator γ of this (principal) ideal can be found in polynomial time, using either [14] or [78, §4]; the former algorithm is more efficient but the latter method is heuristic-free (modulo a dependency on GRH). As explained in the previous section, the g-matrix of the codomain is then g ′ = γ −∗ gµγ −1 . From the requirement that γ should represent an oriented isogeny, it is then clear that the push-forward orientation is given by a′ = γaγ −1 , ⊓ ⊔ b′i = γbi γ −1 . All this data is straightforward to compute. Remark 5.5. It is instructive to try and define the Shimura class group action (on superspecial PPASs) via g 7→ γ −∗ gµγ −1 , a 7→ γaγ −1 , bi 7→ γbi γ −1 and then give a direct matrix-arithmetic proof that this action is well-defined. The main tasks here are showing that g ′ , a′ , b′i ∈ M2 (O), that a′ is fixed under the Rosati involution induced by g ′ , and that Z[a′ , b′1 , b′2 ] is stable under this Rosati involution. The details of such a direct approach can be found in Appendix H.1. All explicit formulae for isogeny evaluation (that we are aware of) restrict to N -isogenies for some N ∈ Z>0 . In view of this, we have the following important consequence of Theorem 5.4: if a g-matrix of (A, λ) is known, then we can act with arbitrary Shimura ideal classes, even if they do not belong to C(R)Z , in polynomial time. (Note: here we assume that (A, λ) is given to us as a Jacobian with the canonical polarization, or as a product of elliptic curves with the product polarization.) We point out that knowing a g-matrix of (A, λ) is polynomial-time equivalent to knowing the endomorphism ring of A, in the strong sense of [73, Def. 2.14]; see [73, §3] for details. Corollary 5.6. Let R be a CM order in a quartic CM field and let p be a prime number. There exists a heuristic polynomial-time algorithm for computing [(a, µ)] ⋆ (A, λ, ι) for all [(a, µ)] ∈ C(R) and (A, λ, ι) ∈ MFp (R), assuming that a g-matrix of (A, λ) is known. Proof. We assume that the orientation ι is given in higher-dimensional representation as in Section 4.3, but the argument should carry over to any other valid way of representing ι. From a g-matrix of (A, λ) we can compute an explicit isomorphism φ : (A, λ) → (E 2 , λ0 ◦ g) using [73, Thm. 5.3]. This is then also an oriented isomorphism between (A, λ, ι) and (E 2 , λ0 ◦ g, φ∗ ι), and the given orientation data are easily pushed through and interpolated to obtain algebraic data g, a, b1 , b2 . Algebraic data g ′ , a′ , b′1 , b′2 for [(a, µ)] ⋆ (A, λ, ι) is then obtained using Theorem 5.4. Using the IKO-to-surface conversion algorithm from [13, Thm. 5.1] we can realize this codomain as a Jacobian (or a product of elliptic 13

We included the assumption p ∤ N (a) for consistency with Theorem 2.7. But, in fact, our algebraic treatment works equally well in the inseparable case.

19

curves with the product polarization), where an explicit isomorphism φ′ can be found through another use of [73, Thm. 5.3]. The algebraic data a′ , b′1 , b′2 can then be converted into interpolation data and pushed through φ′ to obtain the desired output. ⊓ ⊔ Remark 5.7. Corollary 5.6 is heuristic due to several calls to the powersmooth KLPT2 algorithm from [13], which relies on some heuristics. Note that the improved KLPT2 algorithm from [78] can likely be made heuristic-free (perhaps under GRH; this would work with very similar ideas as in the case of 1-dimensional KLPT [97]). 5.3

Constructing g-matrices with a given orientation

An important application of the algebraic viewpoint is the construction of superspecial PPASs with a prescribed orientation. Indeed, on the geometry side there is no systematic way to find orientations other than ad-hoc constructions, as in Section 3 or Appendix C, or CM reductions, which only provide orientations by orders with a relatively small discriminant. As an entry point, we consider the next lemma: Lemma 5.8. Let g be a g-matrix and let a ∈ M2 (O) \ QId2 be a symmetric element with respect to Rosati. Then its centralizer Cent(a) ⊂ M2 (Bp,∞ ) is isomorphic to the quaternion algebra C = Q(a) ⊗ Bp,∞ over Q(a), and Rosati acts as quaternion conjugation on C. This shows that one can obtain orientations as follows. Take a symmetric element a ∈ M2 (O) and consider the intersection M2 (O) ∩ Cent(a). This intersection is invariant under Rosati as both M2 (O) and Cent(a) are. Then taking quadratic subrings of M2 (O) ∩ Cent(a) will yield orientations. This is reminiscent of the 1-dimensional case where orientations are simply quadratic subrings of maximal orders. We note that intersections of the form M2 (O) ∩ Cent(a) were intensively studied in [75] where it was shown that they are either maximal orders or Eichler orders of level p in the quaternion algebra Q(a)⊗Bp,∞ as soon as p is unramified in Q(a) [75, Thm. 2.5.27]. Our goal is an algorithm for creating superspecial PPASs that are primitively oriented by a prescribed CM order R. For convenience we assume R = ZK . We expect that the method below can be tweaked so that it covers a much more general class of CM orders, but this would add a layer of technicality that lies beyond our current scope. Note that primitivity comes for free if R = ZK , so we are merely concerned with finding a K-oriented superspecial PPAS (A, λ, ι) such that ZK ⊂ ι−1 End(A). Our approach is to generalize the 1-dimensional blueprint, where one takes an element in Bp,∞ of prescribed minimal polynomial and then puts that element into a maximal order (after which one finds a corresponding elliptic curve using the effective Deuring correspondence). Here the situation is somewhat more complex as one has to embed an element of M2 (Bp,∞ ) into a maximal order of M2 (Bp,∞ ) in a way that is compatible with the Rosati involution; this 20

compatibility is automatic in the 1-dimensional case. First we prove two useful lemmas. The first lemma can be thought of as a base-point-free orientation framework. Indeed, it is sometimes inconvenient (especially when trying to generalize 1-dimensional proofs) to work with g-matrices, and rather use the following equivalent framework. Lemma 5.9. Let Λ be a maximal order in M2 (Bp,∞ ) that is stable under conjugate-transpose. Then there exists an isomorphism of rings with involutions between Λ with conjugate-transpose and M2 (O) with some Rosati involution induced by a g-matrix. This isomorphism can be computed in polynomial time. Proof. First, we find γ such that M2 (O) = γ −1 Λγ. Such a γ can be found in polynomial time using [78] or [14] as it is equivalent to a principal ideal problem. One can assume that the reduced norm of γ is coprime to p. As M2 (O) is closed under conjugate-transpose one has that (γ −1 Λγ)∗ = γ −1 Λγ. This can be rearranged as γγ ∗ Λ = Λγγ ∗ which means that γγ ∗ generates a two-sided ideal of Λ, hence (γγ ∗ ) = (N ) for some integer N . This implies that γγ ∗ /N has norm 1 and hence the same holds for γ ∗ γ/N . Call this latter matrix g and note that it indeed concerns a g-matrix. Then it is easy to see that (Λ, ∗) is isomorphic as a ring with involution to (M2 (O), †g ) where †g denotes the Rosati involution induced by g. ⊔ ⊓ The second lemma is a very generic fact from the algorithmic theory of quaternion algebras (and might already be in the literature but we could not find a reference). Let C be a quaternion algebra over a field K, not of characteristic √ 2. It is a well-known result K( d), i.e., √ √ that C is split by a quadratic extension √ C ⊗K K( d) ∼ = M2 (K( d)), if and only if C contains K( d) as a subfield. The next√lemma shows that √ if one can find an explicit isomorphism between C ⊗K K( √ d) and M2 (K( d)), then one can find a subfield of C that is isomorphic to K( d): Lemma 5.10. Let K be a number field. Let C be a quaternion algebra over K given by a quaternion basis over K and let d ∈ K \ K 2 . Then one can decide √ whether K( d) embeds into C in quantum polynomial time. Furthermore, if it embeds, one can find an explicit embedding in quantum polynomial time. Remark 5.11. Let us emphasize that the quantum part is not necessary in practice, but it makes the lemma heuristic-free. Indeed, our proof of Lemma 5.10 in Appendix H.2 invokes a quantum algorithm from [60] but this can be replaced with a heuristic algorithm for solving quadratic forms. We now proceed to finding ZK -oriented superspecial PPASs. The following is a first step: Lemma 5.12. Given a quartic CM field K, there exists a quantum polynomialtime algorithm that finds an embedding ι : K ,→ M2 (Bp,∞ ) such that ι(ᾱ) = ι(α)∗ for all α ∈ K, or decides that no such embedding exists. 21

Proof. We first find an element a ∈ M2 (Bp,∞ ) such that a is symmetric with respect to conjugate-transpose and Q(a) ∼ = K0 . We will essentially show how one can generate an element of given trace and norm for symmetric matrices. A symmetric matrix has the following form:   sr rt where s, t ∈ Q and r ∈ Bp,∞ . Let the trace of a be M and its norm be N . This gives us two equations: s + t = M, st − n(r) = N . Such s, t, r can be found by reducing to a quadratic form in 6 variables that always admits a solution and can be solved with Castel’s algorithm [12] in polynomial time (this is a variation of an algorithm due to Simon that does not require factoring). Now we find the CM field K inside Cent(a), or decide that it cannot be found, using Lemma 5.10 with C = Cent(a) and K = Q(a). ⊔ ⊓ Remark 5.13 (continuation of Remark 5.11). Here too the word “quantum” can be omitted at the cost of introducing some heuristics. Our main technical tool for converting this into an algorithm for finding ZK -orientations is the following: Lemma 5.14. Let K ⊂ M2 (Bp,∞ ) be a quartic CM field such that complex conjugation in K amounts to conjugate-transpose in M2 (Bp,∞ ) and assume that the conductor ideal in ZK of the order ZK ∩ M2 (O) is principal and generated by a totally positive µ ∈ ZK0 that is coprime to p. Let ξ ∈ M2 (Bp,∞ ) be such that ξξ ∗ = µ. Let γ ∈ M2 (Bp,∞ ) be such that M2 (O)γ equals the left fractional ideal M2 (O)ZK generated by ZK . Let Λ = (γξ)−1 M2 (O)γξ. Then Λ∗ = Λ and ι : ZK → Λ : α 7→ ξ −1 αξ is an injective ring homomorphism such that ι(ᾱ) = ι(α)∗ for all α ∈ ZK . Corollary 5.15. If we assume that h+ (K0 ) is polynomially bounded,14 there exists a heuristic polynomial-time algorithm which upon input of a quartic CM field K returns a primitively ZK -oriented superspecial PPAS in characteristic p, or returns that no such surface exists. Proof. Repeatedly run Lemma 5.12 until the conductor ideal c of ZK ∩ M2 (O) is generated (as an ideal in ZK ) by some totally positive µ ∈ ZK0 whose norm is not a multiple of p. We expect this to happen with good probability. Indeed, 14

This is typically a mild assumption. By Lemma E.4 we have h+ (K0 )/h(K0 ) ∈ {1, 2, 4}. The Cohen–Lenstra heuristics [24] predict that the odd part of h(K0 ) is extremely small, e.g., it is just 1 for about 76% of all real quadratic number fields. By an extension of the Cohen–Lenstra heuristics (see [57, §1] for a discussion) the even part of h0 (K0 ) comes almost entirely from Cl(K0 )[2], which by genus theory is roughly of size 2t with t the number of prime factors of disc K0 . In view of the Erdös–Kac theorem this number is typically of size log disc K0 .

22

since c̄ = c we expect that c = c0 ZK for some ideal c0 ⊂ ZK0 ; the only exception here is where c has a factor pe with e odd and p a prime ideal that is ramified over K0 . We then expect c0 to be generated by some totally positive µ with probability about 1/h+ (K0 ). Using the previous technical lemma we can find an embedding of ZK inside a self-conjugate maximal order Λ ⊂ M2 (Bp,∞ ) in a way that is compatible with Rosati. Note that all ingredients can be computed efficiently, including the Cholesky decomposition from Lemma 5.3 which involves solving quadratic equations over Q in 5 variables, which can be done efficiently using Castel’s algorithm [12]. Now invoking Lemma 5.9 we get an orientation for some g-matrix in M2 (O). This can be converted into a K-oriented superspecial PPAS as in the proof of Corollary 5.6. ⊔ ⊓ 5.4

Applications

In Appendix I we discuss applications of the previously described algebraic machinery to the “one endomorphism problem”. In dimension 1 it is known that knowing one non-scalar endomorphism provides significant extra information: – Given one non-scalar endomorphism one can compute the entire endomorphism ring in sub-exponential time [45]. – Given an endomorphism of small degree (polylogarithmic in p), one can compute the full endomorphism ring in polynomial time [66]. – Given an oracle for computing non-scalar endomorphisms, one can compute the endomorphism ring in polynomial time [79]. We investigate the first two problems in dimension 2, where we observe that adjustments have to be made, as there are non-scalar (even polarized) endomorphisms that will likely not provide enough information for computing the full endomorphism ring: an example is   1 1 1 −1 on E 2 for any supersingular elliptic curve E. The proper analogue of a non-scalar endomorphism in dimension 2 is one whose minimal polynomial defines a quartic CM field over Q (a “generic” endomorphism satisfies this).

6

Orbits of the Shimura class group action

It is classical that if g = 1 and p = 0 then the action ⋆ : Cl(R) × Mk (R) → Mk (R) is “essentially” transitive, although our algebraic treatment of orientations comes with the subtlety, emphasized by Onuki [76], that there are in fact two orbits. One can jump back and forth between these orbits via (E, ι) 7→ (E, ι ◦ σ), with σ : α 7→ α denoting complex conjugation on R. In positive characteristic, on the other hand, we know that if p > 0 and p | [ZK : R] then Mk (R) is empty, while if p ∤ [ZK : R] then: 23

(i) If p splits in K then all curves in Mk (R) are ordinary and one can jump between the two orbits by quadratic twisting. (ii) If p ramifies in K then all curves in Mk (R) are supersingular; here the action becomes transitive. (iii) If p is inert in K then all curves in Mk (R) are supersingular, but in this case there are again two orbits. Instead of (E, ι) 7→ (E, ι ◦ σ), there is a neat alternative way to jump between the orbits due to Onuki: it can be assumed that all curves are defined over Fp2 , and then one can jump back and forth using the p-power Frobenius map (E, ι) 7→ (E (p) , ι(p) ). This can be assembled from [61, §13, Thm. 5 & Thm. 12] and [76, Prop. 3.3]. In higher dimension this picture is much more subtle.15 The literature does not seem to contain the ingredients needed for a complete answer, which in any case lies beyond the scope of our paper. But we can sketch the overall picture, highlighting the main ingredient: the CM type. Behind the scenes, this notion is already responsible for the (typically) two orbits in the elliptic curve case. Much of what follows is standard to specialists: our main goal is to illustrate the theory with examples that are relevant to the paper at hand. 6.1

An obstruction to transitivity

Our starting point is the ring homomorphism ϱ(A,λ,ι) : R → Endk (D(A)) : α 7→ ι(α)∗ , where ι(α)∗ denotes the pull-back map under ι(α) on the g-dimensional 1 k-vector space D(A) = H 0 (A, ΩA ) of regular 1-forms on A. This homomorphism gives D(A) the structure of an R-module, in the sense of representation theory. Lemma 6.1. If (A, λ, ι), (A′ , λ′ , ι′ ) ∈ Mk (R) lie in the same orbit under the action of C(R) then D(A) ∼ = D(A′ ) as R-modules. Proof. Every Shimura ideal class has a representative (a, µ) such that N (a) is not a multiple of p. Then the isogeny φa : A → A′ is separable, so the map φ∗a : D(A′ ) → D(A) is an isomorphism of k-vector spaces. The diagram D(A′ )

ι′ (α)∗

φ∗ a

D(A)

D(A′ ) φ∗ a

ι(α)∗

D(A)

commutes for every α ∈ R, because φa is oriented. This indeed amounts to saying that φ∗a is an isomorphism of R-modules. ⊔ ⊓ Remark 6.2. The lemma generalizes to non-horizontal isogenies: for any two CM orders R, R′ ⊂ ZK such that p ∤ [ZK : R][ZK : R′ ] it holds that if (A, λ, ι) ∈ Mk (R), (A′ , λ′ , ι′ ) ∈ Mk (R′ ) are connected by a separable oriented isogeny, then D(A), D(A′ ) are isomorphic as ZK -modules (the assumption p ∤ [ZK : R] naturally allows to extend the domain of ϱ(A,λ,ι) to ZK , and likewise for R′ ). 15

E.g., from Remark C.6 we see that Mk (R) may be non-empty even when p | [ZK : R].

24

Example 6.3. We start by shedding a different light on Onuki’s motivating example from [76, p4]. Let R = Z[i] be the ring of Gaussian integers, assume p ̸= 2 and let i ∈ k be a square root of −1. Consider E : y 2 = x3 + x over k along with the primitive R-orientations ι′ : i 7→ ((x, y) 7→ (−x, −iy))

ι : i 7→ ((x, y) 7→ (−x, iy)) ,

on E. The space D(E) is generated by dx/y, which under ι(i) pulls back to d(−x)/iy = (−1/i)dx/y = idx/y while under ι′ (i) it pulls back to −idx/y. Thus the representations map i to the multiplication maps by i and −i, respectively. Therefore (E, ι), (E, ι′ ) must lie in different orbits. In general, this gives a very efficient method for testing whether, in case (iii) above, two given oriented supersingular elliptic curves lie in the same orbit or not. In other words, the decisional version of the “effective R-vectorization problem” from [96, Prob. 2] is very easy to solve. Example 6.4. Let E1 , E2 be elliptic curves over k and let A = E1 × E2 . Then D(A) ∼ = D(E1 ) ⊕ D(E2 ). So, upon picking a generator ωi of D(Ei ) for i = 1, 2 we can view (ω1 , 0), (0, ω2 ) as a basis for D(A). The elements of End(A) can be viewed as matrices   α11 α21 , αij ∈ Hom(Ei , Ej ). α12 α22 With respect to our basis of D(A), the matrix of the pull-back operator along such a matrix (αji )i,j is given by (cij )i,j , where cij ∈ k is the constant such that ∗ αij ωj = cij ωi . Let us have a look at what this implies for the two orientations ι, ι′ from Examples 3.1 and 3.2. Using that differentials pull back to zero under inseparable isogenies, i.e., πp∗ ωi = 0 for i = 1, 2, we find that ϱ(A,λ,ι) maps √ 1   1 √ 1 + −m 0 i 2 7→ d 7→ 1 2 . 1 , i 2 2 2 0 When rewritten with respect to the basis (ω1 , ω2 ), (ω1 , −ω2 ) this becomes √ 1  1  √ 1 + −m +i 0 0 2 2 7→ , d 7→ , 0 12 − i 0 − 12 2 showing that ϱ(A,λ,ι) arises as a direct sum of two 1-dimensional representations, mapping √ √ √ 1 + −m √ 1 + −m x1 + x 2 + x3 d + x 4 d 7→ 2 2 1 1 1 1 x1 + ( ± i)x2 ± x3 + (i ± )x4 (6) 2 2 2 2 for all xi ∈ Z. A similar reasoning for ϱ(A,λ,ι′ ) gives √   1 1 √ 1 + −m +i 0 2 0 , 7→ 2 d → 7 0 21 + i 0 − 12 2 25

when expressing the images with respect to (bω1 , (1/2 − a)ω2 ), (bω1 , (−1/2 − a)ω2 ). Thus we again have a direct sum of two 1-dimensional representations, namely 1 1 1 1 x1 + ( + i)x2 ± x3 ± ( + i)x4 (7) 2 2 2 2 From (6) and (7) we see that ι, ι′ give rise to non-isomorphic R-module structures on D(A). So by Lemma 6.1 we must be in different orbits under the C(R)-action. We emphasize that there is an important difference between the obstructions from Example 6.3 and Example 6.4. In the former case, precomposition of ι′ with complex conjugation removes the obstruction. For the second example this is not true, nor is it possible to achieve this using another automorphism of R: the obstruction to transitivity is really more fundamental here. This is related to the notion of “inequivalent” CM types discussed in the next section. Example 6.5. Revisiting the Z[ζ5 ]-orientation from Example 3.3, we have D(A) ∼ = 1 ) = ⟨dx/y, xdx/y⟩. Through H 0 (C, ΩC ι(ζ5 )∗

d(ξ5 x) dx dx = = ξ5 , y y y

ι(ζ5 )∗ x

dx d(ξ5 x) dx = (ξ5 x) = ξ52 x y y y

we see that, here too, ϱ(A,λ,ι) decomposes into two 1-dimensional representations, mapping ζ5 to multiplication-by-ξ5 and multiplication-by-ξ52 , respectively. 6.2

CM types in characteristic p = 0

In the above examples, the decomposability of ϱ(A,λ,ι) into 1-dimensional subrepresentations ϱi : R → k, i = 1, . . . , g, is not a coincidence. Moreover, these 1-dimensional representations are not arbitrary. In characteristic p = 0 this is classical and captured by the notion of CM type. In this case the ϱi naturally extend their domains to all of K and take values in some subfield L ⊂ k that is isomorphic to a Galois closure of K. It can be argued [93] that the resulting size-g subset of Hom(K, L) is a CM type, in the following sense: Definition 6.6. Let K be a CM field and let L ⊂ C be isomorphic to a Galois closure of K. A CM type of K is a subset of Hom(K, L) containing exactly one element from each pair of complex conjugate embeddings φ, φ̄ : K → L. E.g., this pattern is clearly visible in Example 6.5. Famously, it was proven by Shimura and Taniyama that for p = 0 and under mild assumptions on R, the CM type is the only obstruction to transitivity. One sufficient condition is that R = ZK ,16 see [93, Thm. 5.2]: 16

The “right” sufficient condition reads that R is Gorenstein, which is implied, e.g., by the existence of an index-2 subfield K ′ ⊂ K such that R ∩ K ′ is a maximal order [4] (e.g., maximal real multiplication is a sufficient condition).

26

Theorem 6.7 (Shimura–Taniyama, 1961). Consider a CM field K and let (A, λ, ι), (A′ , λ′ , ι′ ) ∈ Mk (ZK ) have the same CM types; here k denotes an algebraically closed field of characteristic 0. There exists a unique [(a, µ)] ∈ C(ZK ) such that (A′ , λ′ , ι′ ) = [(a, µ)] ⋆ (A, λ, ι). The number of CM types of K is easily seen to be 2g , so under the aforementioned mild assumptions on R this is our best guess for the number of orbits in characteristic 0. However we note that, very exceptionally, the number of orbits may be smaller because certain CM types may not occur, even when R = ZK .17 Another important difference with the elliptic curve case is that it may be impossible to jump between orbits by precomposing the orientation with an automorphism of K. This comes from the existence of inequivalent CM types: any automorphism τ of K commutes with complex conjugation (this is because K0 can be characterized as the maximal totally real subfield of K) and therefore, if Φ is a CM type, then so is Φ′ = Φ ◦ τ , in which case Φ, Φ′ are said to be equivalent. In our main case of interest g = 2 we have from [93, Lem. 3.4]: Lemma 6.8 (Inequivalent CM types for g = 2). Let K be a CM field of degree 4 with Galois closure L and let G = Gal(L, Q). Let Hom(K, L) = ¯ φ, φ̄}. Write Φ = {id, φ} and Φ′ = {id, φ̄}. Then: {id, id, ∼ D4 then Φ and Φ′ are inequivalent, – if G ∼ = C2 × C2 or G = ′ – if G ∼ = C4 then Φ, Φ are equivalent. So the number of inequivalent CM types in these cases is 2, 2, 1, respectively. 6.3

Back to positive characteristic

We now move to our main case of interest k = Fp . We expect that under mild assumptions on R, the obstruction to transitivity from Lemma 6.1 should be the only one. Again we formulate this for maximal orders only:18 Theorem 6.9. Let k = Fp and let K be a CM field. Let (A, λ, ι), (A′ , λ′ , ι′ ) ∈ Mk (ZK ) be such that ϱ(A,λ,ι) ∼ = ϱ(A′ ,λ′ ,ι′ ) . Then there exists a unique [(a, µ)] ∈ C(ZK ) such that (A′ , λ′ , ι′ ) = [(a, µ)] ⋆ (A, λ, ι). Proof. It was shown in [43, Lem. 4.4.1] that every (A, λ, ι) ∈ Mk (ZK ) admits a lift to characteristic 0. As explained in their proof, the possible CM types of such a lift are controlled by Kottwitz’ Φ-determinant condition: explicitly, fixing an integral basis α1 , α2 , . . . , α2g of ZK , for a CM type Φ one can consider the so-called Kottwitz polynomial Y fΦ = (x1 φ(α1 ) + x2 φ(α2 ) + . . . + x2g φ(α2g )) ∈ ZK ∗ [x1 , x2 , . . . , x2g ]. φ∈Φ 17

This can only happen if the last map in (2) is not surjective, see the proof of [51, Lem. 19]. In dimension g = 2 all such examples come from the C2 × C2 case. 18 Here too, it is likely that this assumption can be relaxed significantly, perhaps to R Gorenstein and p ∤ [ZK : R] but we did not find references supporting this.

27

Here K ∗ ⊂ L is the fixed field of the group of automorphisms τ ∈ Gal(L, Q) for which τ ◦ Φ = Φ (this is known as the “reflex field” of K with respect to Φ). The Φ-determinant condition then states that a lift with CM type Φ can be found if and only if there exists a prime p∗ of K ∗ above p such that det (ι(x1 α1 + x2 α2 + . . . + x2g α2g )∗ ) ≡ fΦ mod p∗ . In particular, if ϱ(A,λ,ι) ∼ = ϱ(A′ ,λ′ ,ι′ ) then it is possible to find lifts of (A, λ, ι) and (A′ , λ′ , ι′ ) having the same CM type, and the connecting Shimura ideal class, whose existence is predicted by Theorem 6.7, will also connect (A, λ, ι) and (A′ , λ′ , ι′ ). ⊔ ⊓ It is not hard to check that if p is unramified then the Φ-Kottwitz condition cannot be satisfied with respect to more than one CM type Φ. In this case, at least under the assumption R = ZK , the number of orbits in characteristic p equals the number of orbits in characteristic 0, which is 2g in most cases. But if p ramifies then there may be multiple options for Φ, meaning that the number of orbits decreases (i.e., several CM types “coincide” mod p). √ Example 6.10 (CSIDH). Assume g = 1 and let K = Q( −p) for some prime √ number p. For simplicity we assume p ≡ 1 mod 4 so that ZK = Z[ −p] but this does not matter for our conclusions. The two possible Kottwitz polynomials are √ √ x1 ± −px2 ∈ ZK [x1 , x2 ] (in both cases K ∗ = K). Modulo p∗ = ( −p) both √ polynomials collide to x1 , which equals det(ι(x1 + −px2 )∗ ) ∈ Fp [x1 , x2 ] for the √ Frobenius orientation ι : −p 7→ πp on any supersingular elliptic curve over Fp . So in this case the CM types coincide, i.e., there is only one orbit, in accordance with case (ii) at the beginning of this section. Example 6.11. Revisiting Example 6.4, one easily checks that both (A, λ, ι) and (A, λ, ι′ ) satisfy the Kottwitz condition for a unique CM type, namely {id, φ} and {id, φ̄}, respectively, where √ √ √ 1 + −m 1 − −m √ φ: 7→ , d 7→ − d 2 2 (and these CM types are inequivalent). So here we expect 22 = 4 orbits. Example 6.12 (R2-D2). For the R2-D2 orientations described in Example 3.4, one checks that ϱ(A,λ,ι) maps   √ √ 0 d/cτ d 7→ −p 7→ 0 , cτ 0 when expressed with respect to the basis (ω, 0), (0, ω ′ ), where ω, ω ′ denote regular 1-forms on E, E (p) , respectively. One checks that   √ √ √ ∗  √ det ι x1 + x2 d + x3 −p + x4 d −p = x21 − dx22 . √ √ This satisfies the Kottwitz condition with respect to all CM types of Q( d, −p). So here we expect a unique orbit, coming from a 4-to-1 collision (this is modulo the disclaimer √ √ that we have naively applied Theorem 6.9 to the non-maximal order Z[ d, −p]). The resulting transitivity of the Shimura class group action in this setting plays an important role in the attack from [50]. 28

Remark 6.13. In general, for C2 × C2 fields, one checks that all 4 Kottwitz polynomials have the same reduction mod p if and only if p ramifies in both imaginary quadratic subfields. If p ramifies in exactly one imaginary quadratic subfield then we are left with 3 distinct reductions. As mentioned, in the unramified case the 4 Kottwitz polynomials have distinct reductions. In summary, for a given CM order R in a CM field K, a rough roadmap to understanding the orbits of C(R) on the set of primitively R-oriented superspecial PPAVs is as follows. Let us assume for simplicity that R = ZK . By Theorem 6.7 the number of orbits is at most the number 2g of CM types of K. But the actual number of orbits is usually smaller: – We first recall that it may (exceptionally) happen that there are no primitively ZK -oriented PPAVs in characteristic 0 with a certain given CM type Φ. In view of the proof of Theorem 6.9 this then also reduces the number of orbits over Fp . Note that this property is necessarily shared by the entire equivalence class of Φ. – The most important decrease comes from the fact that the abelian varieties in certain orbits may not be superspecial. E.g., recall from (i) that if g = 1 then we end up with ordinary elliptic curves as soon as p splits in K. In higher dimension this is more subtle and a full characterization is lacking, but Appendix K contains the details for g = 2 under the assumption that p does not ramify in K; this (slightly) extends results by Goren [42]. – As we have just discussed, if p ramifies in K then several CM types may “coincide” mod p. This is controlled by Kottwitz’ determinant condition. A detailed understanding of all this, as well as of the precise assumptions on R under which Theorems 6.7 and 6.9 remain true, is what prevents us from giving a complete orbit description as we did for g = 1 at the beginning of the section. Remark 6.14. Any oriented superspecial PPAV (A, λ, ι) can be defined over Fp2 , so we can consider its Frobenius conjugate (A, λ, ι)(p) = (A(p) , λ(p) , ι(p) ). We believe that (A, λ, ι)(p) always lies in the orbit of (A, λ, ι ◦ σ), perhaps under mild assumptions on R. This would extend Onuki’s observation for g = 1 and we believe that it should follow from Ekedahl’s product criterion [39, Prop. 2.4]; see [42, §2] for an accessible statement. But we have not analyzed this in detail.

7

Security considerations

We conclude with some security aspects of cryptosystems built from Shimura class group actions. Most threats we consider are analogs of existing attack scenarios in the case g = 1, that we expect to carry over to higher dimension. But the necessary tools are often insufficiently developed, due to limited attention and greater technical difficulty. The first 4 aspects have guided us in the parameter selection for the R2-D4 key exchange protocol from Appendix F.1: 29

Endomorphism ring computation. It is to be expected that the vectorization problem for Shimura class group actions on oriented superspecial PPAVs reduces to the problem of computing their endomorphism rings; this would be in complete analogy with the elliptic curve case [18,96]. We note that the endomorphism ring computation problem has several interpretations (e.g., computing an explicit basis of 4g 2 self-maps, determining its structure as an abstract order with involution, computing an IKO-style matrix, . . . ) but they are most likely all equivalent: see [73] for the surface case, while in arbitrary dimension some aspects are treated in [78]. Up to our knowledge, the fastest known algorithms run in time p1/3+o(1) if g = 1,

p4/5+o(1) if g = 2,

2

(log p)O(g ) pg−1 if g > 2,

see [95], [47] and [27, Thm. 6.15], respectively. In practice this attack scenario is largely overruled by Kuperberg’s quantum attack, which we discuss next. Generic attacks on the abelian hidden shift problem. The vectorization problem for commutative group actions can be modeled as an instance of the “abelian hidden shift problem” [23], for which several quantum sub-exponential time algorithms were devised by Kuperberg [58,59]. These run in time L#G (1/2) with G the acting group; so in our case #G = h(R). The concrete cost of Kuperberg’s algorithm is not well-understood, even in the elliptic curve case; one of the fuzzy factors is the cost of an oracle query [8,20], and this becomes even more intricate as the dimension grows. In Appendix F.1 we work with log2 h(R) ≈ 2048, which is on par with CSIDH-4096, commonly believed to reach NIST-I security. In the g-REGA setting, it is customary to sample the secret keys from a strict subset of the acting group, but classical meet-in-the√ middle approaches allow to solve the vectorization problem in time O( #K) where K denotes the key space, i.e., the set of expressions of the form (4). We fix this at 256 bits for NIST-I. Using non-maximal orders. In the elliptic curve case, the vectorization problem associated with a non-maximal order R reduces to any overorder in which R has a smooth index, by “walking up the volcano”. This lowers the size of the class group and therefore weakens the problem, see e.g. [16, §6.3]. In higher dimension this picture is more complicated, but it is certain that in many scenarios (e.g., if the order is Bass), such ascending walks are again possible; see [3] and Appendix J for more context. So it seems wise to work with maximal orders, or at least with orders R for which [ZK : R] is very small.19 This is also a protective measure against the active “overorder attack” described below. What about “imprimitive” CM types? This discussion is specific to higher dimension. We mentioned that key exchange from the R2-D2 orientation discussed in Example 3.4 got broken in [50], in the sense that the vectorization 19

It may also be secure to work with CM orders R whose index in ZK is large, but then it should be free of small factors so that ascension is infeasible, as in SCALLOP [35].

30

problem for C(R) reduces to that for Cl(R1 ), Cl(R2 ) with R1 , R2 the two (largest possible) imaginary quadratic subrings of R. The attack relies on the colliding inequivalent CM types discussed in Example 6.12 and does not obviously generalize to arbitrary C2 × C2 orientations: this is a compelling open question. More generally, one might wonder whether there is a general security issue with mod-p reductions of oriented PPAVs (A, λ, ι) whose CM type Φ is imprimitive, meaning there is a CM subfield K ′ ⊂ K and a CM type Φ′ of K ′ such that Φ consists of those embeddings whose restriction to K ′ is an element of Φ′ . It is known that this is equivalent (in characteristic 0) to A being isogenous to a product of lower-dimensional abelian varieties [93, Thm. 5.2(3)]. All CM types of C2 × C2 fields are imprimitive, while they are always primitive in the cases C4 , D4 . Genus theory attacks. In the elliptic curve case, the decisional Diffie–Hellman assumption for class group actions can often be broken using genus theory [19,15]. This attack strategy generalizes to higher dimension, as was illustrated in [19, §6] and worked out in full generality in [50]. It can be countered by making sure one acts with elements from C(R)2 (which is automatic if #C(R) is odd). Backdoors and active attacks. One realistic threat is that a malicious authority or another adversary could lure Alice or Bob into acting with their secret key on a dishonestly generated PPAV (A, λ, ι), primitively oriented only by an overorder R′ ⊋ R rather than R; then in this case the key could be recovered along the lines of Remark 4.8. This attack can be prevented by public key validation, i.e., by checking that A is superspecial, which can be done efficiently thanks to recent work [28], and that ι is a primitive R-orientation. If R has a large index in ZK , however, the non-primitivity of ι might be hard to detect; see our corresponding discussion at the end of Section 3. Thus, for this reason as well, it is safer to consider orientations by orders that are near-maximal.

References 1. N. Alamati, L. De Feo, H. Montgomery, and S. Patranabis. Cryptographic group actions and applications. In Asiacrypt 2020, volume 12492 of Lecture Notes in Computer Science, pages 411–439. Springer, 2020. 2. B. Allombert, J.-F. Biasse, J. K. Eriksen, P. Kutas, C. Leonardi, A. Page, R. Scheidler, and M. T. Bagi. Faster SCALLOP from non-prime conductor suborders in medium sized quadratic fields. In PKC 2025, volume 15676 of Lecture Notes in Computer Science, pages 333–363. Springer, 2025. 3. S. Arpin, S. Marseglia, and C. Springer. Isogeny graphs of abelian varieties and singular ideals in orders. Preprint available at https://arxiv.org/abs/2508. 03570. 4. H. Bass. Torsion free and projective modules. Transactions of the American Mathematical Society, 102(2):319–327, 1962. 5. A. Basso, G. Borin, R. Rueger, and S. Schaeffler. CORAL: Faster isogeny group action for post-quantum NIKE. In Crypto 2026, volume 16803 of Lecture Notes in Computer Science, pages 506–536. Springer, 2026.

31

6. G. Bisson. Computing endomorphism rings of abelian varieties of dimension two. Mathematics of Computation, 84(294):1977–1989, 2015. 7. G. Bisson and M. Streng. On polarised class groups of orders in quartic CM-fields. Mathematical Research Letters, 24(2):247–270, 2017. 8. X. Bonnetain, M. Duparc, D. Lazzarini, L. Maino, C. Martindale, C. Petit, S. Schaeffler, A. Schrottenloher, and A. Sferlazza. Quantum security analysis of unrestricted isogeny-based group actions. Preprint available at https://eprint.iacr. org/2026/2215. 9. R. Bröker, D. Gruenewald, and K. Lauter. Explicit CM theory for level 2-structures on abelian surfaces. Algebra & Number Theory, 5(4):495–528, 2011. 10. E. H. Brooks, D. Jetchev, and B. Wesolowski. Isogeny graphs of ordinary abelian varieties. Research in Number Theory, 3:art. no. 28, 2017. 11. N. Bruin, E. V. Flynn, and D. Testa. Descent via (3, 3)-isogeny on Jacobians of genus 2 curves. Acta Arith., 165(3):201–223, 2014. 12. P. Castel. Solving quadratic equations in dimension 5 or more without factoring. In ANTS-X, volume 1 of The Open Book Series, pages 213–233. MSP, 2013. 13. W. Castryck, T. Decru, P. Kutas, A. Laval, C. Petit, and Y. B. Ti. KLPT2 : Algebraic pathfinding in dimension two and applications. In Crypto 2025, volume 16000 of Lecture Notes in Computer Science, pages 167–200. Springer, 2025. 14. W. Castryck, J. K. Eriksen, R. Invernizzi, and F. Vercauteren. The principal ideal problem for endomorphism rings of superspecial abelian varieties. Research in Number Theory. To appear (proceedings of ANTS-XVI). 15. W. Castryck, M. Houben, F. Vercauteren, and B. Wesolowski. On the decisional Diffie–Hellman problem for class group actions on oriented elliptic curves. Research in Number Theory, 8(4):art. no. 99, 2022. Proceedings of ANTS-XV. 16. W. Castryck, R. Invernizzi, G. Lorenzon, J. Meers, and F. Vercauteren. Orient Express: Using Frobenius to express oriented isogenies. In Latincrypt 2023, volume 14168 of Lecture Notes in Computer Science, pages 145–173. Springer, 2023. 17. W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes. CSIDH: An efficient post-quantum commutative group action. In Asiacrypt 2018, volume 11274 of Lecture Notes in Computer Science, pages 395–427. Springer, 2018. 18. W. Castryck, L. Panny, and F. Vercauteren. Rational isogenies from irrational endomorphisms. In Eurocrypt 2020, volume 12106 of Lecture Notes in Computer Science, pages 523–548. Springer, 2020. 19. W. Castryck, J. Sotáková, and F. Vercauteren. Breaking the decisional Diffie– Hellman problem for class group actions using genus theory: Extended version. Journal of Cryptology, 35(4):art. no. 24, 2022. 20. J. Chávez-Saab, J.-J. Chi-Dominguez, S. Jaques, and F. Rodriguez-Henriquez. The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents. Journal of Cryptographic Engineering, 12(3):349–368, 2022. 21. M. Chen, A. Leroux, and L. Panny. SCALLOP-HD: Group action from 2dimensional isogenies. In PKC 2024, volume 14603 of Lecture Notes in Computer Science, pages 190–216. Springer, 2024. 22. M. Chenu and B. Smith. Higher-degree supersingular group actions. Mathematical Cryptology, 1(2):85–101, 2022. 23. A. Childs, D. Jao, and V. Soukharev. Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology, 8(1):1–29, 2014. 24. H. Cohen and H. W. Lenstra. Heuristics on class groups of number fields. In Number Theory Noordwijkerhout 1983, pages 33–62, Berlin, Heidelberg, 1984. Springer.

32

25. L. Colò and D. Kohel. Orienting supersingular isogeny graphs. Journal of Mathematical Cryptology, 14:414–437, 2020. 26. K. Conrad. Galois groups of cubics and quartics (not in characteristic 2). Expository paper, available at https://kconrad.math.uconn.edu/blurbs/ galoistheory/cubicquartic.pdf. 27. M. Corte-Real Santos, H. Kir, O. Taibi, and B. Wesolowski. Rapid mixing in superspecial isogeny graphs. Preprint available at https://eprint.iacr.org/2026/ 2429. 28. M. Corte-Real Santos, G. Lorenzon, and K. Reijnders. Supersingularity and superspeciality verification of abelian surfaces. Preprint available at https: //eprint.iacr.org/2026/2259. 29. J.-M. Couveignes. Hard homogeneous spaces. Unpublished note available at https: //eprint.iacr.org/2006/291. 30. D. A. Cox. Primes of the Form x2 +ny 2 : Fermat, Class Field Theory, and Complex Multiplication. Pure and Applied Mathematics. Wiley, 2nd edition, 2013. 31. P. Dartois, J. K. Eriksen, T. B. Fouotsa, A. Herlédan Le Merdy, R. Invernizzi, D. Robert, R. Rueger, F. Vercauteren, and B. Wesolowski. PEGASIS: Practical effective class group action using 4-dimensional isogenies. In Crypto 2025, volume 16000 of Lecture Notes in Computer Science, pages 67–99. Springer, 2025. 32. P. Dartois, J. K. Eriksen, R. Invernizzi, and F. Vercauteren. qt-Pegasis: Simpler and faster effective class group actions. In Eurocrypt 2026, volume 16544 of Lecture Notes in Computer Science, pages 636–665. Springer, 2026. 33. P. Dartois, A. Leroux, D. Robert, and B. Wesolowski. SQIsignHD: New dimensions in cryptography. In Eurocrypt 2024, volume 14651 of Lecture Notes in Computer Science, pages 3–32. Springer, 2024. 34. L. De Feo, C. D. de Saint Guilhem, T. B. Fouotsa, P. Kutas, A. Leroux, C. Petit, J. Silva, and B. Wesolowski. Séta: Supersingular encryption from torsion attacks. In Asiacrypt 2021, volume 13093 of Lecture Notes in Computer Science, pages 249–278. Springer, 2021. 35. L. De Feo, T. B. Fouotsa, P. Kutas, A. Leroux, S.-P. Merz, L. Panny, and B. Wesolowski. SCALLOP: Scaling the CSI-FiSh. In PKC 2023, volume 13940 of Lecture Notes in Computer Science, pages 345–375. Springer, 2023. 36. B. A. Dina, S. Ionica, and J. Sijsling. Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication. Mathematics of Computation, 92:349–383, 2023. 37. Y. A. Drozd, V. V. Kirichenko, and A. V. Roiter. Hereditary and Bass orders. Math. USSR-Izvestiya, 1(6):1357–1375, 1967. Translated from Izv. Akad. Nauk SSSR Ser. Mat. 31 (1967), 1415–1436. 38. D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. 39. T. Ekedahl. On supersingular curves and abelian varieties. Mathematica Scandinavica, 60:151–178, 1987. 40. A. Enge and E. Thomé. Computing class polynomials for abelian surfaces. Experimental Mathematics, 23(2):129–145, 2014. 41. D. Goldstein and M. Schacher. Norms in central simple algebras. Pacific Journal of Mathematics, 292(2):373–388, 2018. 42. E. Z. Goren. On certain reduction problems concerning abelian surfaces. Manuscripta mathematica, 94(1):33–44, 1997. 43. E. Z. Goren and K. E. Lauter. Class invariants for quartic CM fields. Annales de L’Institut Fourier, 57(2):457–480, 2007.

33

44. C. Greither. On the two generator problem for the ideals of a one-dimensional ring. Journal of Pure and Applied Algebra, 24(3):265–276, 1982. 45. A. Herlédan Le Merdy and B. Wesolowski. The supersingular endomorphism ring problem given one endomorphism. IACR Communications in Cryptology, 2(1):art. no. 6, 2025. 46. M. Houben. Efficient post-quantum commutative group actions from orientations of large discriminant. In Asiacrypt 2025, volume 16248 of Lecture Notes in Computer Science, pages 141–173. Springer, 2025. 47. M. Houben and L. L. Pham. Computing endomorphisms of superspecial principally polarized abelian surfaces in time and memory p4/5+o(1) . Preprint available at https://eprint.iacr.org/2026/2530. 48. J. G. Huard, B. K. Spearman, and K. S. Williams. Integral bases for quartic fields with quadratic subfields. Journal of Number Theory, 51(1):87–102, 1995. 49. T. Ibukiyama, T. Katsura, and F. Oort. Supersingular curves of genus two and class numbers. Compositio Mathematica, 57(2):127–152, 1986. 50. R. Invernizzi, J. K. Eriksen, A. Sferlazza, P. Tasbihgou, and F. Vercauteren. Cryptanalysis of higher-dimensional module actions via twisting and genus theory. Private communication. 51. S. Ionica and E. Thomé. Isogeny graphs with maximal real multiplication. Journal of Number Theory, 207:385–422, 2020. 52. G. Ivanyos. Algorithms for algebras over global fields. PhD thesis, Hungarian Academy of Sciences, 1996. 53. E. Kani. The number of curves of genus two with elliptic differentials. Journal für die reine und angewandte Mathematik, 1997(485):93–122, 1997. 54. A. Y. Kitaev. Quantum measurements and the Abelian stabilizer problem. Unpublished note available at https://arxiv.org/abs/quant-ph/9511026. 55. M.-A. Knus, A. Merkurjev, M. Rost, and J.-P. Tignol. The Book of Involutions, volume 44 of American Mathematical Society Colloquium Publications. American Mathematical Society, 1998. 56. D. Kohel, K. Lauter, C. Petit, and J.-P. Tignol. On the quaternion ℓ-isogeny path problem. LMS Journal of Computation and Mathematics, 17(A):418–432, 2014. Proceedings of ANTS-XI. 57. P. Koymans and C. Pagano. On the distribution of Cl(K)[l∞ ] for degree l cyclic fields. Journal of the European Mathematical Society, 24(4):1189–1283, 2022. 58. G. Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing, 35(1):170–188, 2005. 59. G. Kuperberg. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In TQC 2013, volume 22 of Leibniz International Proceedings in Informatics, pages 20–34, 2013. 60. P. Kutas and M. Montessinos. Efficient computations in central simple algebras using Amitsur cohomology. Journal of Algebra, 665:255–281, 2025. 61. S. Lang. Complex multiplication, volume 255 of Grundlehren der Mathematischen Wissenschaften. Springer, 1983. 62. S. Lang. Algebraic Number Theory, volume 110 of Graduate Texts in Mathematics. Springer, 2nd edition, 1994. 63. K. Lauter and D. Robert. Improved CRT algorithm for class polynomials in genus 2. In ANTS-X, volume 1 of The Open Book Series, pages 437–461. MSP, 2013. 64. F. Lemmermeyer. Kuroda’s class number formula. Acta Arithmetica, 66(3):245– 260, 1994. 65. H. Lenstra, J. Pila, and C. Pomerance. A hyperelliptic smoothness test. II. Proceedings of the London Mathematical Society, 84(1):105–146, 2002.

34

66. J. Love and D. Boneh. Supersingular curves with small noninteger endomorphisms. In ANTS-XIV, volume 4 of The Open Book Series, pages 7–22. MSP, 2020. 67. S. Marseglia. Cohen–Macaulay type of orders, generators and ideal classes. Journal of Algebra, 658:247–276, 2024. 68. C. Martindale. Isogeny graphs, modular polynomials, and applications. PhD thesis, Université de Bordeaux and Universiteit Leiden, 2018. 69. K. McMurdy. Explicit representation of the endomorphism rings of supersingular elliptic curves. Unpublished note available at https://pages.ramapo.edu/ ~kmcmurdy/research/McMurdy-ssEndoRings.pdf. 70. J. S. Milne. Abelian varieties. Course notes available at https://www.jmilne. org/math/CourseNotes/av.html. 71. J. S. Milne. Algebraic number theory. Course notes available at https://www. jmilne.org/math/CourseNotes/ant.html. 72. J. S. Milne. Complex multiplication. Course notes available at https://www. jmilne.org/math/CourseNotes/cm.html. 73. M. Montessinos. Equivalent computational problems for superspecial abelian surfaces. Preprint available at https://eprint.iacr.org/2026/120. 74. J. Neukirch. Algebraic Number Theory, volume 322 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, Heidelberg, 1999. Translated from the 1992 German original by Norbert Schappacher, with a foreword by G. Harder. 75. M.-H. Nicole. Superspecial abelian varieties, theta series and the Jacquet-Langlands correspondence. PhD thesis, McGill University, 2005. 76. H. Onuki. On oriented supersingular elliptic curves. Finite Fields and Their Applications, 69:art. no. 101777, 2021. 77. A. Page and D. Robert. Introducing Clapoti(s): Evaluating the isogeny class group action in polynomial time. Unpublished note available at https://eprint.iacr. org/2023/1766. 78. A. Page, D. Robert, and J. Soumier. On the conversion of module representations for higher dimensional supersingular isogenies. In Crypto 2026, volume 16803 of Lecture Notes in Computer Science, pages 415–446. Springer, 2026. 79. A. Page and B. Wesolowski. The supersingular endomorphism ring and one endomorphism problems are equivalent. In Eurocrypt 2024, volume 14656 of Lecture Notes in Computer Science, pages 388–417. Springer, 2024. 80. L. Panny, C. Petit, and M. Stopar. KLaPoTi: An asymptotically efficient isogeny group action from 2-dimensional isogenies. IACR Communications in Cryptology, 2(3):art. no. 5, 2025. 81. M. Peters. Quadratische Formen über Zahlringen. Acta Arithmetica, 24(2):157– 164, 1973. 82. D. Robert. The geometric interpretation of the Tate pairing and its applications. Preprint available at https://eprint.iacr.org/2023/177. 83. D. Robert. The module action for isogeny based cryptography. Preprint available at https://eprint.iacr.org/2024/1556. 84. D. Robert. On the efficient representation of isogenies. Survey written for NuTMiC 2024, available at https://eprint.iacr.org/2024/1071. 85. D. Robert. Some notes on algorithms for abelian varieties. Compilation of notes available at https://eprint.iacr.org/2024/406. 86. D. Robert. Breaking SIDH in polynomial time. In Eurocrypt 2023, volume 14008 of Lecture Notes in Computer Science, pages 472–503. Springer, 2023. 87. A. Rostovtsev and A. Stolbunov. Public-key cryptosystem based on isogenies. Unpublished note available at https://eprint.iacr.org/2006/145.

35

88. S. P. Sanon. Endomorphism rings of ordinary abelian varieties. PhD thesis, Technische Universität Kaiserslautern, 2022. 89. G. Shimura. Abelian varieties with complex multiplication and modular functions, volume 46 of Princeton Mathematical Series. Princeton University Press, 1998. 90. C. L. Siegel. Sums of mth powers of algebraic integers. Annals of Mathematics, 46(2):313–339, 1945. 91. J. H. Silverman. The Arithmetic of Elliptic Curves, volume 106 of Graduate Texts in Mathematics. Springer, 2nd edition, 2009. 92. B. K. Spearman and K. S. Williams. Unramified quadratic extensions of a quadratic field. The Rocky Mountain Journal of Mathematics, 25(2):783–788, 1995. 93. M. Streng. Complex multiplication of abelian surfaces. PhD thesis, Leiden University, 2010. 94. J. Voight. Quaternion algebras, volume 288 of Graduate Texts in Mathematics. Springer, 2021. 95. B. Wesolowski. The supersingular isogeny problem in time and memory p1/3+o(1) . Preprint available at https://eprint.iacr.org/2026/1486. 96. B. Wesolowski. Orientations and the supersingular endomorphism ring problem. In Eurocrypt 2022, volume 13277 of Lecture Notes in Computer Science, pages 345–371. Springer, 2022. 97. B. Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In FOCS 2022, pages 1100–1111. IEEE Computer Society Press, 2022. 98. K. S. Williams. Integers of biquadratic fields. Canadian Mathematical Bulletin, 13(4):519–526, 1970.

A

Background on the background

A.1

Cryptographic group actions

Let X be a finite set and G a finite commutative group in which one can compute efficiently. A cryptographic group action ⋆ : G × X → X is an action of G on X meeting some hardness properties, most notably one-wayness: given x1 , x2 ∈ X it is (computationally) hard to retrieve g ∈ G, if it exists, such that g ⋆ x1 = x2 . This problem is often referred to as vectorization in G. An effective group action (EGA) is one where the group action can be evaluated efficiently at all inputs. Only fairly recently, it was discovered how to build effective cryptographic group actions from isogenies between elliptic curves, see [31,32,77,80]. For certain applications such as non-interactive key exchange it is enough to have a so-called restricted effective group action (REGA). More explicitly, the action is called a g-REGA for some generating subset g = {g1 , . . . , gn } of G if n is polylogarithmic in |G| and there exist efficient algorithms to compute gi ⋆ x, gi−1 ⋆ x for all gi ∈ g, x ∈ X. Most isogeny-based group actions in the literature fall into this category, see e.g. [17,25,22,16,46,5]. This will also be the case for the Shimura class group actions studied in this paper, where potential generalizations of [32] to construct an EGA from this are left as future work. We refer to [1] for more details on REGAs and EGAs and their range of applications. 36

A.2

Polarized isogenies

In the next few paragraphs we recall some basic facts and terminology needed for studying the Shimura class group action. All statements below are well-known to specialists and kept concise; we refer the reader to [93,72,70] and the references included below for more details. Abelian varieties and isogenies. Let k be an algebraically closed field of characteristic p, where p is either a prime or 0. An abelian variety over k is a smooth projective algebraic variety, equipped with a base point 0 ∈ A and geometric morphisms A × A → A : (P, Q) 7→ P + Q, A → A : P 7→ −P turning A into an algebraic group; elliptic curves are abelian varieties of dimension 1. A homomorphism φ : A1 → A2 between abelian varieties A1 , A2 is a morphism such that φ(0) = 0; this is automatically a group homomorphism at the level of points; if dim A1 = dim A2 and φ is surjective then it is called an isogeny. The set of endomorphisms (= self-homomorphisms) of an abelian variety A becomes a ring when equipped with point-wise addition and composition; it is denoted End(A). We identify Z with the subring of End(A) consisting of scalar multiplications and write End0 (A) = End(A) ⊗Z Q for the endomorphism algebra. Assuming p > 0, an abelian variety A/k of dimension g is called superspecial if it is isomorphic to E g for some supersingular elliptic curve E/k. If g ≥ 2 then the choice of E does not matter: by a theorem of Deligne [41] any two products of g supersingular elliptic curves are isomorphic. Principal polarizations. A polarization on an abelian variety A is the isogeny λ : A → A∨ ∼ = Pic0 (A) : P 7→ [t−P D − D] attached to an ample divisor D on A (where t−P denotes point-wise translation by −P ). The reader not familiar with the language of divisors can just think of a polarization as an isogeny to a certain companion abelian variety, called the dual abelian variety, and satisfying a certain “positivity” condition; this is good enough for almost all that follows. If this isogeny is of degree 1 then it is called a principal polarization and we call (A, λ) a principally polarized abelian variety, or PPAV in short (in the specific case of surfaces we will often write PPAS). While elliptic curves have a unique, canonical, principal polarization, this is not true in general for abelian varieties. Example A.1 (Jacobians). Consider a smooth projective curve C of genus g ≥ 1 along with the Abel–Jacobi map u : C ,→ Jac(C) ∼ = Pic0 (C) : P 7→ [P − P0 ], where P0 ∈ C is some fixed base point. The codimension 1 subvariety of Jac(C) consisting of all sums of g − 1 points in the image of u can be seen as a divisor D on Jac(C). The associated polarization λ : Jac(C) → Jac(C)∨ is a principal polarization, known as the canonical principal polarization on Jac(C). Example A.2 (products). If (A1 , λ1 ), (A2 , λ2 ) are PPAVs, with principal polarizations coming from divisors D1 , D2 , then the product abelian variety A1 × A2 37

comes with the product polarization λ1 × λ2 , attached to the divisor D1 × A2 + A1 × D2 , which is again principal. Rosati involution. With every homomorphism φ : A1 → A2 comes a dual ∨ homomorphism φ̂ : A∨ 2 → A1 (which, in the case of a surjective homomorphism, is obtained by pulling back divisors on A2 under φ). If λ1 , λ2 are principal polarizations on A1 , A2 then this gives rise to an adjoint homomorphism φ† = λ−1 1 ◦ φ̂ ◦ λ2 : A2 → A1 . When applied to endomorphisms of a PPAV (A, λ), this defines an involution on End(A) called the Rosati involution, which extends by linearity to the entire endomorphism algebra End0 (A). The aforementioned positivity condition on λ is reflected in the fact that the quadratic form α 7→ Tr(αα† ) on End0 (A), where Tr(x) denotes the trace of the multiplication-by-x map, viewed as a linear map on the Q-vector space End0 (A), is positive-definite. Example A.3. Any homomorphism φ : A1 ×A2 → B1 ×B2 between two products can be seen as a matrix   φ11 φ21 φ12 φ22 of homomorphisms φij : Ai → Bj . If A1 , A2 , B1 , B2 come equipped with principal polarizations, then with respect to the respective product polarizations we have  † †  φ11 φ12 † φ = , (8) φ†21 φ†22 which can be thought of as a “conjugate-transpose”. This naturally generalizes to homomorphisms between products of arbitrarily many abelian varieties. Polarized isogenies. If φ : A1 → A2 is an isogeny and λ2 is a principal polarization on A2 then φ̂◦λ2 ◦φ is a polarization on A1 , which cannot be principal in general, if only for degree reasons. According to a theorem of Mumford, if λ1 is a principal polarization on A1 then the polarizations on A1 are exactly those isogenies of the form λ1 ◦α with α a totally positive endomorphism on A1 : by this we mean that α = α† and the (necessarily real) eigenvalues of the multiplication-byα map are positive. Applying this to the foregoing, this means that for φ̂ ◦ λ2 ◦ φ to be a polarization, there must exist a totally positive α ∈ End(A1 ) such that the diagram α

A1

A1

φ

A2 λ2

λ1

A∨ 1 38

φ b

A∨ 2

commutes. We then say that φ : (A1 , λ1 ) → (A2 , λ2 ) is a polarized isogeny with respect to α, or an α-isogeny for short. An important special case is α = N ∈ Z>0 . We note that the degree of an N -isogeny equals N g ; the integer N itself is then called its reduced degree, denoted degrd(φ). An isomorphism between PPAVs is a 1-isogeny. We state the next result for later use [70, Prop. 13.8]: Proposition A.4. Let (A1 , λ1 ) be a PPAV, let H ⊂ A1 be a finite subgroup whose order is not a multiple of p, and let α ∈ End(A1 ) be totally positive. Let φ : A1 → A2 be a separable isogeny with kernel H. There exists a principal polarization λ2 on A2 such that φ : (A1 , λ1 ) → (A2 , λ2 ) is an α-isogeny if and only if H is maximal with the property that eα (P, λ1 (Q)) = 1,

∀P, Q ∈ H,

where eα denotes the α-Weil pairing on A1 . Moreover λ2 is unique in this case. Example A.5 (IKO matrices). Let E be a supersingular elliptic curve over k and assume that p > 0; fix an isomorphism ϑ : O → End(E) from a suitable maximal order O ⊂ Bp,∞ in the unique quaternion algebra ramified at p and ∞. Consider the superspecial abelian surface A = E 2 equipped with the product polarization λ1 . In this case Mumford’s theorem says that the principal polarizations on A are precisely the maps of the form λ1 ◦ ϑ(g) where   sr g= , s, t ∈ Z>0 , r ∈ O, st − rr̄ = 1, r̄ t and ϑ is applied entry-wise; the abbreviation IKO stands for Ibukiyama, Katsura and Oort, the authors of [49] where this is detailed; see Section 5. A.3

Omitted proofs

Proof (of Lemma 2.4). Let ε1 , . . . , εg−1 be a set of fundamental units of R0 , chosen such that they are all positive under some fixed real embedding. Since (R, ε2i ) ∈ PR for all i, it is clear that all Shimura classes for which a = R are among expressions of the form e

g−1 [(R, εe11 · · · εg−1 )], ei ∈ {0, 1}.

+ The lemma follows because aā = µ1 R = µ2 R iff µ−1 1 µ2 ∈ R0 is a unit.

(9) ⊓ ⊔

Remark A.6. Not all expressions of the form (9) are valid Shimura classes: this eg−1 is the case only if εe11 · · · εg−1 is totally positive. It may well happen that this is true only when e1 = e2 = . . . = eg−1 = 0; in such cases [(a, µ)] is always uniquely determined by a (however, the existence of µ still imposes a condition on a). Moreover, even in the case of a totally positive unit ε ̸= 1, the class [(R, ε)] may still be trivial: if ε = αᾱ for some α ∈ R, then (R, ε) = (αR, αᾱ) ∈ PR . 39

Proof (of Lemma 2.6). Consider a Shimura ideal (a, µ) with a ⊂ R and let n be an integer such that nµ a is integral. Then n n n̄ 2 n µ )] = [( a2 , n2 )], [(a, µ)]2 = [(a2 , µ2 )] = [( a2 , µ µ µ̄ µ ⊔ ⊓

where we have used that n = n̄, µ = µ̄. Remark A.7. Based on computational evidence, we expect the dichotomy [C(R) : C(R)Z ] ∈ {1, #C(R)[2]} to hold for any CM order R ⊂ K.

Proof (of Theorem 2.7). Although it is hard to pinpoint a reference not putting additional assumptions on R and k, or not working in the language of complex tori [89] or Deligne modules [65], the arguments are standard. We highlight the constructive aspects of the proof, because these indicate how to work with the action, and are more concise about the remaining details. Let (A1 , λ1 , ι1 ) ∈ Mk (R) and [(a, µ)] ∈ C(R). We show how to construct (A2 , λ2 , ι2 ) = [(a, µ)] ⋆ (A1 , λ1 , ι1 ), a priori as an element of Mk (K), but we will then be able to conclude that we always land in Mk (R). By replacing a with an equivalent fractional ideal if needed and scaling µ accordingly, we can assume that a is integral of norm not divisible by p. We then consider the finite subgroup \ H= ker ι1 (x) x∈a

of A1 , which has order NK/Q (a). Let φ : A1 → A2 := A1 /H be the corresponding quotient isogeny (in the language of a-multiplications, this amounts toPacting with a on the unpolarized abelian variety A1 , see [72, P §7]). Writing µ = i xi y¯i for xi , yi ∈ a and letting zi = xi y¯i /µ ∈ R so that i zi = 1, for any P, Q ∈ H we have Y Y eι(µ) (P, λ1 (Q)) = eι(µ) (ι(zi )(P ), λ1 (Q)) = eι(xi )ι(yi )† (P, λ1 (Q)) i

=

Y

i

eι(yi )† (ι(xi )(P ), λ1 (Q)) =

i

Y

eι(yi )† (0, λ1 (Q)) = 1

i

where we have used some standard properties of the Weil pairing which, e.g., can be found in [82, §3.1], and the fact that λ1 (Q) lies in the kernel of the dual of ι(yi )† . So by Proposition A.4 there is a unique principal polarization λ2 on A2 turning φ into an ι1 (µ)-isogeny. We then let ι2 : K → End0 (A2 ) be the push-forward orientation, i.e., ι2 : α 7→ (φ ◦ ι1 (α) ◦ φ† )/(φ ◦ φ† ). 40

From the multiplicativity of the unpolarized action [72, Prop. 7.28] it is not hard to deduce that acting in this way with (ab, µν) amounts to the same thing as first acting with (a, µ), then with (b, ν). Since it is straightforward that Shimura ideals of the form (µR, µµ̄) with µ ∈ R act trivially, this defines an action of C(R) as wanted, and freeness is easily established. To see that this lands in Mk (R) ⊂ Mk (K) it is enough to observe that every ideal class admits two representing ideals with coprime norms, see e.g. [63, Proof of Lem. 27] for more details on this step. ⊓ ⊔

B

Endomorphism rings of some well-known supersingular elliptic curves

We include explicit descriptions of the endomorphism rings of certain “extremal” supersingular elliptic curves: – y 2 = x3 + x in characteristic p ≡ 3 mod 4, of j-invariant 1728: being the cryptographers’ default example of a supersingular elliptic curve, this is of course very well-known and included for completeness only, – y 2 = x3 + 1 in characteristic p ≡ 5 mod 6, of j-invariant 0: an explicit description of its endomorphism ring can be found in [69, Prop. 3.2] but this description is wrongly attributed to y 2 = x3 − 1, see Remark B.3, – y 2 = x3 + 12x2 + 18x in characteristic p ≡ 5 mod 8, which has j-invariant 8000: we are unaware of prior work describing the endomorphism ring as explicitly as in Lemma B.4 below; in [56, Lem. 3] it was studied as an abstract maximal order in Bp,∞ but, unfortunately, that statement contains a typo, see Remark B.5 below. We do not cover other congruence classes of p, but we note that also the maximal orders from [56, Lem. 4] for the cases p ≡ 1 mod 4 contain typos, as was pointed out in [14, Ftn. 4]. Since [69,56] are frequently cited references and the typos have been copied into the existing literature, we hope that this appendix helps in cleaning up the landscape. Lemma B.1. Let p ≡ 3 mod 4 be a prime number and consider the quaternion algebra   −1, −p Bp,∞ = Q ramified at p and ∞, with the usual generators 1, i, j, k (i.e., we have i2 = −1, j 2 = −p and k = ij = −ji) over Q. Fix a square root i ∈ Fp2 of −1. The elliptic curve E : y 2 = x3 + x over Fp with j-invariant 1728 admits the endomorphism ι : (x, y) 7→ (−x, iy) satisfying ι2 = [−1] and 1 7→ [1],

i 7→ ι,

j 7→ πp , 41

k 7→ ιπp

(10)

defines a ring isomorphism   i+j 1+k Z 1, i, , → End(E), 2 2 where πp denotes the p-th power Frobenius endomorphism on E. Proof. As mentioned, this is standard, and easier than the lemmata below, so we will be concise. It is immediate that ι2 = [−1] and, using p ≡ 3 mod 4, it is easy to check that ιπp = −πp ι. Thus the assignment (10) defines an isomorphism Bp,∞ → End0 (E) at the level of algebras. To complete the proof, it suffices to observe that (i + j)/2, (1 + k)/2 map to endomorphisms on E, which in view of [91, Cor. III.4.11] is equivalent to E[2] ⊂ ker(ι + πp ), ker([1] + ιπp ), but that is immediate from E[2] = {0, (0, 0), (i, 0), (−i, 0)}. This is indeed enough, because an explicit calculation shows that Z⟨1, i, (i + j)/2, (1 + k)/2⟩ is a subring of Bp,∞ and a discriminant computation shows that it concerns a maximal order. Lemma B.2. Let p ≡ 5 mod 6 be a prime number and consider the quaternion algebra   −3, −p Bp,∞ = Q ramified at p and ∞, with the usual generators 1, i, j, k (i.e., we have i2 = −3, j 2 = −p and k = ij = −ji) over Q. Fix a primitive 3rd root of unity z ∈ Fp2 . The elliptic curve E : y 2 = x3 +1 over Fp with j-invariant 0 admits the endomorphism ω : (x, y) 7→ (zx, y) satisfying ω 2 + ω + [1] = 0. Writing Ω = [2]ω + [1] and πp for the p-th power Frobenius endomorphism on E, the assignment 1 7→ [1],

i 7→ Ω,

j 7→ πp ,

k 7→ Ωπp

defines an isomorphism   −1 + i 3 + i + 3j + k Z 1, , j, → End(E) 2 6

(11)

of rings. Proof. It is easy to check that the (horizontal) line connecting two points of the form (zx0 , y0 ), (z 2 x0 , y0 ) has (x0 , y0 ) as its third point of intersection with E. This implies that ω 2 + ω + [1] = 0, and as a special case we find that (0, 1) and (0, −1) are points of order 3. An easy calculation shows Ω 2 = [−3]. Since πp2 = [−p] and πp ω = ω 2 πp so that Ωπp = −πp Ω, the assignment from the statement of the lemma is seen to 42

define an isomorphism between Bp,∞ and End0 (E). Clearly (−1 + i)/2 7→ ω, so it suffices to show that [3] + Ω + [3]πp + Ωπp = [4] + [2]ω + [4]πp + [2]ωπp

(12)

annihilates E[6]: then the left-hand side of (11) lands inside End(E), and this left-hand side is a maximal order, as can be checked explicitly. It obviously annihilates E[2], so it suffices to concentrate on E[3]. An analysis of the 3-division polynomial 3x(x3 + 4) of E shows that, besides (0, ±1), the points of order 3 are √ √ √ (t, ± −3), (zt, ± −3), (z 2 t, ± −3) with t = (−4)−(p−2)/3 ∈ Fp . We now do a case-by-case analysis of how πp acts on these points, keeping in mind that they are of order 3: – on (0, ±1) it acts as the identity, so expression (12) acts as ω − [1] which clearly kills √ these points, −3) it acts by negation, easily seen to make expression (12) vanish, – on (t, ± √ – on (zt, ± −3) it acts as −ω, again making expression (12) vanish after reduction modulo [3],√ – similarly, on (z 2 t, ± −3) it acts as −ω 2 , which similarly makes expression (12) vanish modulo [3]. This concludes the proof. Remark B.3. In contrast with what is claimed in [69, Prop. 3.2] the statement fails for E : y 2 = x3 − 1 as soon as p √ ≡ 3 mod 4. In this case 3 is a square in Fp and one finds that the points (t, ± 3) ∈ E[3] with t = 4−(p−2)/3 ∈ Fp are fixed by Frobenius. Expression (12) acts on these points as ω − [1] which fails to annihilate them. Lemma B.4. Let p ≡ 5 mod 8 be a prime number and consider the quaternion algebra   −2, −p Bp,∞ = Q ramified at p and ∞, with the usual generators 1, i, j, k (i.e., we have i2 = −2, j 2 = −p and k = ij = −ji) over Q. Fix a square root z ∈ Fp2 of −2. The elliptic curve E : y 2 = x3 + 12x2 + 18x over Fp with j-invariant 8000 admits the endomorphism  2  −y z 18 ϑ : (x, y) 7→ , y(1 − ) 2x2 4 x2 satisfying ϑ2 = [−2] and 1 7→ [1],

i 7→ ϑ,

j 7→ πp ,

k 7→ ϑπp

defines a ring isomorphism   1 + i + j i + 2j ± k Z 1, i, , → End(E) 2 4 43

(13)

(14)

where the sign ± should be read as + if p ≡ 5, 13 mod 48 and as − if p ≡ 29, 37 mod 48, and πp denotes the p-th power Frobenius endomorphism. Proof. In the proof all occurrences of ± should be read as + if p ≡ 5, 13 mod 48 and as − if p ≡ 29, 37 mod 48, and conversely for ∓. Throughout we fix a square root i ∈ Fp of −1. It is easy to check that ϑ is a well-defined endomorphism of degree 2 satisfying ϑ2 = [−2]. It is also easy to see that πp2 = [−p] and ϑπp = −πp ϑ, showing that (13) defines an isomorphism between Bp,∞ and End0 (E). It thus suffices to show that E[2] ⊂ ker([1] + ϑ + πp ),

E[4] ⊂ ker(ϑ + [2]πp ± ϑπp ),

because this implies that the left-hand side of (14) indeed lands inside End(E), and this left-hand side is a maximal order, regardless of the sign chosen, as can be checked via an explicit discriminant calculation. We do this in an artisanal way. First, write O = (0, 0), T0 = (−6 + 3iz, 0), T1 = (−6 − 3iz, 0) for the points of order 2 on E. Using ϑ(O) = 0,

ϑ(T0 ) = ϑ(T1 ) = O

and πp (O) = O,

πp (Tℓ ) = T1−ℓ for ℓ = 0, 1

one indeed checks that [1] + ϑ + πp annihilates E[2] as wanted. The remainder of the proof is a bit more tedious. By explicit calculation, the points of order 4 are seen to be groupable as follows: – the halves of O, which have x-coordinates 3iz, −3iz, – the halves of T0 , with x-coordinates √ √ −6 + 3iz + 6 1 − iz, −6 + 3iz − 6 1 − iz, – the halves of T1 , with x-coordinates √ √ −6 − 3iz + 6 1 + iz, −6 − 3iz − 6 1 + iz. These x-coordinates all live in Fp2 , i.e., 1 + iz and 1 − iz are squares in Fp2 . This follows, e.g., from πp2 = [−p], implying that for any point P ∈ E[4] it holds that πp2 (P ) = [−p]P = −P where we have used p ≡ 1 mod 4. For the same reason none of the corresponding y-coordinates is defined over Fp2 , i.e., the points of order 4 all have field of definition Fp4 . It is immediate to see how [2]πp = πp [2] acts on these halves: the respective results are O, T1 , T0 , independent of which half was chosen. Thus it suffices to show that ϑ(1 ± πp ) = (1 ∓ πp )ϑ also maps the halves of O to O, the halves of T0 to T1 and the halves of T1 to T0 , with the sign depending on p mod 48 as in the statement of the lemma. 44

Let us first concentrate on the halves of O. Since O ∈ ker ϑ and since ϑ2 = [−2], these halves must be mapped inside {T0 , T1 } under ϑ. But this means that (1 ± πp )ϑ maps every half of O to T0 + T1 = O as wanted. Now consider a half of Tℓ for ℓ ∈ {0, 1}. Since ϑ(Tℓ ) = O this half must be mapped to a half of O under ϑ. It follows that (1 ∓ πp )ϑ maps the half of Tℓ to a sum of two halves of O with different x-coordinates. It is clear that this is indeed a point of order 2 different from O, hence an element of {T0 , T1 }, but we need to show that it concerns T1−ℓ . We concentrate on a half H of T0 (the other case is analogous). An explicit calculation shows that ϑ(H) = (−3iz, y0 ) for some y-coordinate y0 ∈ Fp4 . Then πp ϑ(H) = (3iz, y0p ) and the usual addition formula shows that the x-coordinate of (1 ∓ πp )ϑ(H) is given by 2  p 1 1 p ∓y0 − y0 (y0 ± y0 )2 − 12 = ((y 2 )p ± 2y0p+1 + y02 ) − 12. − 12 = 6iz 72 72 0 Since y02 = (−3iz)3 + 12(−3iz)2 + 18(−3iz) = 108(2 − iz) this equals   3 −6 ± 3 · 108(p−1)/2 (2 − iz)(p+1)/2 = −6 ± 3 (2 − iz)(p+1)/2 , p with ( p· ) the Legendre symbol. So upon setting this equal to the x-coordinate of T1 , it suffices to show   3 ± (2 − iz)(p+1)/2 = −iz. p Note, as a sanity check, that both sides square to 2, but we have to argue that we have the same square root of 2 on both sides. For this we rely on the congruence √ √ (2 + 2)(p+1)/2 ≡ 2 mod p √ 3, 13 mod 16 assuming p is inert: to in Z[ 2], which holds if and only if p ≡ √ prove this, the main trick is to rewrite 2 + 2 = ζ −1 (1 + ζ)2 for a primitive 8th root of unity ζ. So using p ≡ 5 mod 8 we find that the equality holds with + if and only if p ≡ 5, 13 mod 48 and with − if and only if p ≡ 29, 37 mod 48, as wanted. Remark B.5. The two orders in (14) are isomorphic via j 7→ −j, so also if p ≡ 29, 37 mod 48 then it is possible to give an isomorphism from the maximal order with a + sign, but the isomorphism changes. These orders are essentially taken from [56, Lem. 3] but, there, the third basis element reads (1 + j + k)/2 rather than (1 + i + j)/2. This is an error: for the sign − the resulting order is not maximal but of index 3 (for the sign + it is). 45

C

R2: three families of Fp -rational orientations

In this section we study families of oriented PPASs defined over Fp , where the orientations are such that the p-th power Frobenius endomorphism is among the orienting endomorphisms; in this context, we will denote this Frobenius endomorphism by Πp to avoid confusion with p-th power Frobenius maps between elliptic curves, for which we keep writing πp . We have already encountered R2D2 in Example 3.4. The other orientations are called R2-C4 and R2-D4. Besides paying tribute to a series of astromech droids, these names make reference to the Galois group (of the Galois closure) of the underlying CM field K, which is either isomorphic to D2 ∼ = C2 × C2 , C4 or D4 (indeed, A4 and S4 are impossible in the CM case). The R2 stands for “rational and 2-dimensional”.20 Our main motivation for including Πp in the ring of orienting endomorphisms is that its representation comes “for free”, i.e., we do not need to carry around corresponding interpolation data; see Section 4.3. This comes with important gains, similar to why, in the elliptic curve case, CSIDH stands out in terms of efficiency. For each of the families, the starting surface is the Weil restriction A = WFp2 /Fp (E) ∼ =F̄p E × E (p) of a well-chosen supersingular elliptic curve E/Fp2 , equipped with the product polarization λ. Recall: the p-th power Frobenius endomorphism on A is given by   0 πp Πp = πp 0 with πp : E → E (p) the Frobenius isogeny. In R2-D2 we use a curve E for which πp2 = −p, from which it follows that Πp2 = −p. In particular this requires that √ our orienting order R contains −p. For this reason, for R2-C4 and R2-D4 one must proceed differently: indeed, C4 -fields and D4 -fields that are CM cannot contain any imaginary quadratic subfields. Instead we choose E/Fp2 such that πp2 = p, so that Πp2 = p. To our knowledge, the use of PPAS over Fp on √ which the p-th power Frobenius endomorphism does not act as −p has not been considered in a cryptographic context before, so these constructions may be found interesting for independent reasons. Remark C.1. Since Πp commutes with all other orienting endomorphisms, all oriented PPAS in the orbit of (A, λ, ι) under the action of C(R) can again be assumed to be defined over Fp . For use in Appendix G, let us also note that the assumptions πp2 = ±p give rise, respectively, to isomorphisms A(Fp ) ∼ = E(Fp2 ) ∼ =



Z (p ∓ 1)Z

2  , A(Fp2 ) ∼ = E(Fp2 ) × E(Fp2 ) ∼ =

Z (p ∓ 1)Z

4

of abelian groups. 20

We invite the reader to complete our series with a key exchange protocol for which the name C-3PO would be well-suited.

46

More precisely, we consider the following method for generating Frobeniusoriented PPASs over Fp , which produces all possible Galois groups. As we have mentioned, we must start from a supersingular elliptic curve E/Fp2 on which πp2 = p, with known endomorphism ring, and let (A, λ) be its Weil restriction. Our strategy is to let q  √ K=Q a+b p √ for a, b ∈ Z such that a + |b| p < 0 (so that it concerns a quartic CM field) that will be determined later. We look for an orientation of the form     q α βπp √ √ 0 πp ι : p 7→ Πp = , a + b p 7→ πp β p1 πp απp πp 0 for suitable α ∈ End(E), β ∈

1 Hom(E (p) , E)πp ⊋ End(E) p

of trace tr(α) = tr(β) = 0. An easy calculation shows that the right-most matrix commutes with Πp and is negated when taking the conjugate-transpose. Let us compute 

α βπp πp β p1 πp απp

2



pβ 2 + α2 0 0 πp β 2 πp + p1 πp α2 πp





0 (αβ + βα)πp = + πp (αβ + βα) 0 √ = (−p n(β) − n(α))ι(1) + tr(αβ)ι( p)

where we have used that tr(β) = tr(α) = 0. Thus for a = −p n(β) − n(α) and b = tr(αβ) the map ι : K → End0 (A) is well-defined. Our key tool to control the Galois group of K is the following lemma: Lemma C.2. Under the above assumptions on a, b, the Galois group (of the Galois closure) of K is isomorphic to ∼ C2 × C2 if a2 − b2 p is a square, 1. D2 = 2. C4 if a2 − b2 p is not a square but p(a2 − pb2 ) is, 3. D4 if neither a2 − pb2 nor p(a2 − pb2 ) is a square. In particular, if p ≡ 3 mod 4 then K is either a C2 × C2 -field or a D4 -field. Proof. The classification can be found in [26, Lem. 4.7]. As for the last claim, the classification shows that Gal(K, Q) ∼ = C4 if and only if a2 − b2 p = pk 2 for some ′ k ∈ Z. In particular a = pa for some integer a′ such that pa′2 = b2 + k 2 . Since p ≡ 3 mod 4 this is only possible if a′ , b, k are all even. But then we can take out a factor 4 and the argument repeats, leading to a contradiction by infinite descent. ⊓ ⊔ In the concrete orientations below, the curve E will be constructed as a twist of some well-known supersingular elliptic curve E0 : y 2 = f (x) defined over Fp : E : vy 2 = f (x),

v ∈ Fp2 non-square. 47



Note that πp2 = −p on E0 (assuming p > 3) and therefore we indeed have πp2 = p on E. The twisting isomorphisms τ : E → E0 : (x, y) 7→ (x, uy),

τ (p) : E (p) → E0 : (x, y) 7→ (x, up y),

where u ∈ Fp4 \ Fp2 satisfies u2 = v, combine (component-wise) into an isomorphism of PPAVs T : WFp2 /Fp (E) → E02 (for the product polarizations). Using πp τ = τ (p) πp and πp τ (p) = −τ πp one checks !     e p α βπp α e −βπ 0 −πp −1 −1 T ◦ Πp ◦ T = ◦T = , T◦ , πp β p1 πp απp πp 0 e πp πp βe − p1 πp α where the (quasi-)endomorphisms α e = τ ατ −1 and βe = τ βτ −1 denote the “lollipops” of α, β. Thus, one can also think of ι as an orientation of (E02 , λ0 ), where for any 1 1 = End(E0 ) α e ∈ End(E0 ), βe ∈ End(E0 ) πp πp with trace 0, we obtain an orientation by q √ Z[ a + b p]

(15)

e − n(e e the advantage of this viewpoint is that with a = −p n(β) α) and b = tr(e αβ); it allows us to work directly in End(E0 ), but it becomes less apparent that the orienting endomorphisms on the Weil restriction are Fp -rational. Remark C.3. This viewpoint also makes for a clearer link with the machinery from Section 5.3: applying Lemma 5.8 to g = Id2 and the symmetric element   0 −πp P = ∈ M2 (End(E0 )), πp 0 we are looking for quadratic subrings of Q(P ) ⊗Q End(E0 ) of the form (15). Example C.4 (R2-D4). In view of Lemma C.2, let us assume p ≡ 3 mod 4. We start from E0 : y 2 = x3 + x, whose endomorphism ring is of course very well known, see Lemma B.1: it is isomorphic to the maximal order   i+j 1+k −1, −p O0 = Z⟨1, i, , ⟩ ⊂ Bp,∞ = 2 2 Q where an isomorphism O0 → End(E0 ) maps i to (x, y) 7→ (−x, iy) and j to p-th power Frobenius πp . 48

We proceed as above and look for suitable trace-0 elements α ∈ O0 , β ∈ O0 1j , where we have dropped the e· ’s to lighten notation. A Z-basis of the trace-0 sublattice of O0 is given by i, i+j 2 , k, so a general trace-0 element is α = a1 i + a 2

i+j + a3 k. 2

For β, a direct computation of the reduced trace on 1j O0 shows that 1j , ji , 1+k 2j form a Z-basis of its trace-0 sublattice, so β=

1 1 + k
b1 + b2 i + b3 j 2

for integers a1 , a2 , a3 , b1 , b2 , b3 . This yields p+1 2 p+1 2 a2 − pa23 − b21 − b1 b3 − b − b22 , 4 4 3 b = a2 b1 + (a1 + a2 )b3 − 2a3 b2 .

a = −a21 − a1 a2 −

For each choice of ai , bi such that a2 − b2 p is a non-square (generically the case) we obtain an orientation of type D4 by Lemma C.2. The condition a + √ |b| p < 0 is automatically satisfied because every quartic number field contained in M2 (Bp,∞ ) is necessarily totally imaginary. As for the primitivity, an easy calculation shows q √ disc Z[ a + b p] = 256b4 p2 (a2 − b2 p). (16) From [48, Thm. 1 and Tbl. B] we see that for p ≡ 3 mod 4 this equals disc K as soon as b = ±1 and a2 − p is square-free. So in these cases the order is maximal and our orientation is automatically primitive. A near-maximal example where |b| = 4 will be studied in Appendix F. Example C.5 (R2-C4). We follow the same recipe to realize C4 . Lemma C.2 tells us that we must move away from characteristics p ≡ 3 mod 4. We therefore start from the elliptic curve E0 : y 2 = x3 + 12x2 + 18x over Fp2 , where p ≡ 5 mod 8. We refer to Lemma B.4 for an explicit description of its endomorphism ring, which is isomorphic to the maximal order     1 + i + j i + 2j ± k −2, −p Z 1, i, , ⊂ Bp,∞ = , 2 4 Q with the sign depending on whether p ≡ 5, 13 mod 48 or p ≡ 29, 37 mod 48. For concreteness, we proceed under the assumption that p ≡ 5, 13 mod 48, corresponding to the +-sign. The trace-0 condition imposes i + 2j + k α = a1 i + a2 (i + j) + a3 , 4   1 1+i+j i + 2j + k β= b1 + b2 i + b3 − b3 j 2 4 49

for integers a1 , a2 , a3 , b1 , b2 , b3 , so we end up with expressions a = −2a21 − (p + 2)a22 − 4a1 a2 − a1 a3 − (p + 1)a2 a3 3p + 1 2 p+3 2 − a3 − b21 − 2b22 − b1 b3 − b2 b3 − b , 8 8 3 b = −a1 b3 + 2a2 b1 + a3 b1 − a3 b2 . Again this will generically result in orientations of type D4 . To end up in the C4 case, we write p = x2 +y 2 as a sum of two squares (possible because p ≡ 1 mod 4) and look for a non-trivial zero of the quadratic form xa − pb ∈ Z[a1 , a2 , a3 , b1 , b2 , b3 ]. Then 0 = (xa − pb)(xa + pb) = (p − y 2 )a2 − p2 b2 = p(a2 − pb2 ) − a2 y 2 so that p(a2 − pb2 ) is a square as wanted. Controlling primitivity for R2-C4 is harder than for R2-D4. Indeed, by construction the factor a2 − pb2 is a square away from factors p, and following [48, Thm. 1 and Tbl. C] this makes our order non-maximal, typically. An example family of solutions is where p = 1 + 4m2 for some integer m ≡ 5 mod 6 (so that p ≡ 5 mod 8 and p ̸≡ 29, 37 mod 48): we can take a1 = −m+1, a2 = −1, a3 = 2, b1 = −1, b2 = m, b3 = 2

⇒

a = −2p, b = −2

yielding a2 − pb2 = 16pm2 . So disc K is smaller than (16) by a factor m2 , at least. Remark C.6. Many of the examples we found satisfy p | a, b and consequently p3 | a2 − b2 p (since p(a2 − b2 p) has to be a square), in which case one checks that p √ a+b p γ= √ p is integral. If we want our orientation to extend to Z[γ] ⊂ ZK then      q 1 β α βπp √ 0 πp p απp ι( a + b p) = = 1 1 πp β p1 πp απp πp 0 p πp α p πp βπp should factor through Πp , i.e., the right-most factor should really be an element of End(A). However, this is not always the case. The bottleneck is the bottomright entry, which is not always free from denominators; recall that we sample β from (1/p) Hom(E (p) , E)πp . E.g., again for p = 1 + 4m2 we can consider a1 = −2m2 − m + 1, a2 = −2m − 1, a3 = 4m + 2, b1 = 2m − 1, b2 = −2m2 + 3m, b3 = −4m + 2 (leading to a = −2p2 , b = −2p) and one checks that the coefficient at k of jβj equals b2 + b3 /4 ≡ 2m + 1 ̸≡ 0 mod p. So this example shows that Mk (R) can be non-empty even if p | [ZK : R]: this cannot occur in dimension g = 1. 50

D

Proofs from Section 4 (except for Lemma 4.3)

D.1

Proof from Section 4.1

Proof (of Lemma 4.1). If K = Frac(R) is Galois (cases C2 × C2 , C4 ) then ℓR necessarily factors into prime ideals of equal degree 4/r for r ∈ {1, 2, 4} and the analysis is easy. In the D4 -case there is an exception to this: it may happen that ℓR = p1 p2 p for degree-1 primes p1 , p2 and a degree-2 prime p. But then necessarily p is self-conjugate and this does not lead to a suitable factorization of ℓR. ⊓ ⊔ D.2

Proofs from Section 4.2

Proof (of Theorem 4.4). The product polarization on Aui gives that ιAi (α)† = (ιi (αk,j )† )1≤k,j≤u = (ιi (ᾱk,j ))1≤j,k≤u = ιAi (α∗ ) for any α ∈ Mu (R). Moreover, ιAi (α)† ◦ ιAi (α) = ιAi (nIdu ) because ιAi : ∗ Mu (R) → End(Aui ) is an injective  ring homomorphism and α α = nIdu ∈ Mu (R). Then, Φ† =

φ† Idu −α†A 1 αA2 φ Idu

. Using α∗ α = αα∗ = nIdu , φ† ◦ φ = ι1 (d),

φ ◦ φ† = ι2 (d), the four blocks of Φ† Φ are † (1, 1) : φ† φ Idu + αA α = ι1 (d + n)Idu = ι1 (N )Idu , 1 A1 † † (1, 2) : φ† αA − αA φ† Idu = 0, 2 1

(2, 1) : αA2 φ Idu − φ αA1 Idu = 0, † (2, 2) : αA2 αA + φφ† Idu = ι2 (n + d)Idu = ι2 (N )Idu , 2

where in (1, 2) and (2, 1) we used that φ is oriented, hence φ† ◦ι2 (α)† = ι1 (α)† ◦φ† and φ ◦ ι1 (α) = ι2 (α) ◦ φ. Since ιi (N ) = [N ], it follows that Φ† Φ = [N ] and Φ is an N -isogeny of PPAVs of dimension 2ug, of degree N 2ug . (i) Φ(P, 0) = (φ Idu (P ), −αA1 (P )) for P ∈ Au1 ; taking P = (P1 , 0, . . . , 0) the first coordinate of the image is φ(P1 ). (ii) For P ∈ Au1 [N ], † Φ(−αA (P ), φ Idu (P )) = 1 † † † (−φ αA (P ) + αA φ(P ), αA1 αA (P ) + φ† φ(P )) = (0, [N ]P ) = 0. 1 2 1 † The map P 7→ (−αA (P ), φ Idu (P )) is injective on Au1 [N ]: indeed, if both coor1 dinates vanish, then P ∈ Au1 [nR0 ] ∩ Au1 [dR0 ]; coprimality of nR0 and dR0 then implies that xn + yd = 1 for suitable x, y ∈ R0 , hence P = 0. Since N is coprime to the base field characteristic and #Au1 [N ] = N 2ug = deg Φ, the image coincides with ker Φ. For the second equality, since nR0 + N R0 = nR0 + dR0 = R0 , then nR0 and N R0 are coprime, hence αA1 acts as an automorphism on Au1 [N ]: indeed, A1 [N ] is a finite group and if P ∈ Au1 [N ] and αA1 (P ) = 0, then

51

P ∈ Au1 [nR0 ] ∩ Au1 [N R0 ], and again P = 0 by coprimality of nR0 and N R0 . Then, substituting P 7→ αA1 (P ) and using −ι1 (n)Idu = ι1 (d)Idu on Au1 [N ], and φ ◦ ι1 (α) = ι2 (α) ◦ φ, we obtain the stated subgroup. ⊔ ⊓ Remark √ 4.5). We have that Φ = Ψ2 ◦Ψ1 with Ψ1 , Ψ2 √ D.1 (continuation of Remark both N -isogenies and ker Ψ1 = N ker Φ, hence √ † ker Ψ1 = {(−αA (P ), φ Idu (P )) | P ∈ Au1 [ N ]}. 1 The Rosati dual Φ† is again of the shape of the theorem, up to sign flips in the αAi ’s, so the same argument yields √ † (Q), φ† Idu (Q)) | Q ∈ Au2 [ N ]} ker Ψ2† = {(αA 2 √ † = {(αA φ Idu (P ), ι1 (d)Idu (P )) | P ∈ Au1 [ N ]}. 2 One computes Ψ1 and Ψ2† from their kernels and glues them along an isomorphism between their codomains; the details of this gluing in the middle are technical, but are discussed in [33, App. F], for instance. ∗ ∗
Proof (of Proposition 4.6). Since α∗ = XY −Y , we have X  ∗  X X + Y ∗ Y (Y X − XY )∗ α α= . Y X − XY XX ∗ + Y Y ∗ ∗

Under the hypotheses of (a) we have X ∗ X = XX ∗ = xIdm and Y ∗ Y = Y Y ∗ = yIdm , so both diagonal blocks equal (x + y)Idm and the off-diagonal blocks vanish. The conclusion for αα∗ follows similarly. The hypotheses of (b) are exactly the conditions under which α∗ α equals n Id2m . For (c), the claim follows by induction on k. The case i = 0 is proven by ϑ̄0 ϑ0 = ϑ0 ϑ̄0 = NK/K0 (ϑ0 ). For i ≥ 1, a scalar matrix ϑIdm satisfies (ϑIdm )∗ (ϑIdm ) = (ϑIdm )(ϑIdm )∗ = NK/K0 (ϑ) Idm and commutes with every matrix, so (a) applies at each step with X = αi−1 and Y = ϑi Id2i−1 , adding the term NK/K0 (ϑi ) to n. For (d), the claim again follows by induction and similarly as for (c), since the case i = 0 holds by the hypotheses on α0 and the hypotheses of (a) apply at Pi−1 every step i ≥ 1 with X = αi−1 , x = n1 + j=1 NK/K0 (ϑ′j ), and Y = ϑ′i Id2k+i−1 . The last statement follows taking α0 as the matrix from [85, Lemma 4.2]. ⊔ ⊓

E

Proof of Lemma 4.3

This appendix is devoted to a detailed proof of Lemma 4.3. We also prove an easy corollary. Let us first recall the statement of the Lemma. Lemma 4.3. Assume that K is a C2 × C2 CM field, and let K0 be the real quadratic subfield and K1 , K2 the imaginary quadratic subfields. If Z× K contains 52

no roots of unity other than ±1, then | ker κZK | ≤ | coker κZK | ≤

1 2q(K)

Y

e(ℓ),

ℓ prime

Y 1 | coker NK/K0 | e(ℓ), 4q(K) ℓ prime

× where q(K) = [Z× K : ZK0 ] ∈ {1, 2}, e(ℓ) is the ramification index of a prime ℓ in K, and NK/K0 : Cl(ZK ) → Cl+ (ZK0 ) denotes the ideal class norm map.

Corollary E.1. Assume that K is a C2 × C2 CM field with Z× K containing no roots of unity other than ±1. Let R be an order in K and Ri = R ∩ Ki for i = 1, 2. Then, C1 C2 Y e(ℓ) | ker κR | ≤ 2q(K) ℓ prime





d

 

1 i where Ci = fi p prime, p|fi 1 − K p p , with fi = [ZKi : Ri ] the conductor of Ri , and dKi the discriminant of Ki , for i = 1, 2.

Q

Proof. If ([a1 ], [a2 ]) ∈ Cl(R1 ) × Cl(R2 ) is in the kernel of κR , then ([a1 ZK1 ], [a2 ZK2 ]) ∈ Cl(ZK1 ) × Cl(ZK2 ) is in the kernel of κZK . This yields a well-defined group homomorphism ψ : ker κR → ker κZK whose kernel consists of the pairs in ker κR of classes of invertible ideals of R1 , R2 that become principal when extended to ZK1 , ZK2 , respectively. Hence, h(R2 ) h(R1 ) · | ker ψ| ≤ h(ZK1 ) h(ZK2 ) where h denotes the class number, and    Y  h(Ri ) dKi 1 = fi 1− h(ZKi ) p p p prime p|fi

using [30, Theorem 7.24], and remembering the assumption that the only roots of unity in ZK (and hence in ZKi and Ri ) are ±1. Together with Lemma 4.3, the inequality | ker κR | ≤ | ker ψ|| ker κZK | concludes the proof. ⊔ ⊓ To prove the lemma we will make use of the following results from [64]. Lemma E.2 ([64, 1.3]). Let K be a C2 × C2 extension of Q and let K0 , K1 , K2 be the three intermediate quadratic fields. The map j : Cl(ZK0 ) × Cl(ZK1 ) × Cl(ZK2 ) → Cl(K) : ([a0 ], [a1 ], [a2 ]) 7→ [a0 ZK a1 ZK a2 ZK ] 53

b → Cl(ZK ) where is a group homomorphism. Taking the restriction map b j:C b = {([a0 ], [a1 ], [a2 ]) ∈ Cl(ZK ) × Cl(ZK ) × Cl(ZK ) | C 0 1 2 NK0 /Q (a0 )NK1 /Q (a1 )NK2 /Q (a2 ) = 1} gives a surjection coker b j ↠ coker j and | coker b j| =

2d−2

Q

ℓ prime e(ℓ) , × [Z : H]

where d is the number of infinite primes that ramify in K/Q, e(ℓ) is the ramification index of a prime ℓ in the extension K/Q, and H ≤ Z× is the subgroup of integer units that are in the image of the norm map NK/Q . Lemma E.3 ([64, 1.5]). Let K be a CM C2 × C2 field, with quadratic subfields K0 , K1 , K2 . Then h(ZK ) =

1 q(K)h(ZK0 )h(ZK1 )h(ZK2 ) 2

× × × where h denotes the class number and q(K) = [Z× K : ZK0 ZK1 ZK2 ] is the unit index.

Moreover, we will need the following formulas for the narrow class number h+ and the order of the Shimura class group. Lemma E.4. Let L be a number field, then h+ (ZL ) =

2r

× + h(ZL ), [Z× L : (ZL ) ]

where r is the number of real embeddings σi : L ,→ C, i ∈ {1, . . . r}. Proof. There is an exact sequence 1→

Z× L× u 7→ [uZL ] [a] 7→ [a] u 7→ u L − − − − → −−−−−−−→ Cl+ (ZL ) −−−−−−→ Cl(ZL ) → 1. × + × )+ (L (ZL )

The formula follows from surjectivity of the sign map sgn : L× → {±1}r sending elements x ∈ L to ( sgn(σ1 (x)), . . . , sgn(σr (x)) ) ∈ {±1}r , with kernel (L× )+ . ⊔ ⊓ Lemma E.5. Let K be a CM C2 × C2 field. If Z× K contains no roots of unity other than ±1, then |C(ZK )| =

1 h(ZK1 )h(ZK2 )| coker NK/K0 | 2

where NK/K0 : Cl(ZK ) → Cl+ (ZK0 ) is the ideal class norm map. 54

Proof. From the exact sequence in Section 2.2, it follows that × + |C(ZK )| = [(Z× K0 ) : NK/K0 (ZK )]

h(ZK ) . | im NK/K0 |

Using Lemma E.3, and Lemma E.4 applied to K0 , we can rewrite this as 1 h+ (ZK0 ) × + × + × h(ZK1 )h(ZK2 )q(K)[Z× K0 : (ZK0 ) ][(ZK0 ) : NK/K0 (ZK )]. 8 | im NK/K0 | With the assumption that Z× K contains no roots of unity other than ±1, then × × × × q(K) = [Z× : Z Z Z ] = [Z× K K0 K1 K2 K : ZK0 ], yielding |C(ZK )| =

1 × | coker NK/K0 |h(ZK1 )h(ZK2 )[Z× K : NK/K0 (ZK )]. 8

Again under the assumption that Z× K contains no roots of unity other than ±1, × ⊓ it is not difficult to show that [Z× K : NK/K0 (ZK )] = 4, which ends the proof. ⊔ We are now ready to prove Lemma 4.3. Proof. First observe that if ([a1 ], [a2 ]) ∈ Cl(ZK1 ) × Cl(ZK2 ) is in the kernel of κZK , then ([1], [a1 ], [a2 ]) ∈ Cl(ZK0 ) × Cl(ZK1 ) × Cl(ZK2 ) is in the kernel of the map j from Lemma E.2, namely there is an injection ker κZK ,→ ker j, from which we have | ker κZK | ≤ | ker j| =

h(ZK0 )h(ZK1 )h(ZK2 ) | coker j|. h(ZK )

Using Lemma E.3, then | ker j| =

2 | coker j|, q(K)

where one can see that q(K) ∈ {1, 2}, following e.g. [71, Proposition 5.12]. Hence, | ker j| ≤

Y 2 1 | coker b j| ≤ e(ℓ) q(K) 2q(K) ℓ prime

using Lemma E.2 for the second inequality, with d = 1 (as the real infinite prime of Q ramifies in K) and [Z× : H] = 2 (as −1 is not a norm in the totally imaginary field K). This proves the bound on | ker κZK |. On the other hand, | coker κZK | =

|C(ZK )| 1 | ker κZK | = | coker NK/K0 || ker κZK | h(ZK1 )h(ZK2 ) 2

by Lemma E.5, which proves the bound on | coker κZK |. 55

⊔ ⊓

Example E.6. We consider the R2-D2 orientation √ √ introduced in Example 3.4 and used in Section F.2 below. Here K = Q( d, √ −p) for a prime p > 3 and a √ d), and say K1 = Q( −p), square-free integer d coprime to p. Then K = Q( 0 √ K2 = Q( −dp). Assume that d = q1 q2 , where q1 , q2 > 3 are prime. Assume moreover p ≡ d ≡ 3 mod 4. Then disc ZK = 24 p2 q12 q22 by [98, Thm. 3]. There are then exactly four ramified primes in K/Q, namely 2, p, q1 , q2 , and since each of them is ramified in exactly two quadratic subfields, we have e(2) = e(p) = e(q1 ) = e(q2 ) = 2. From Lemma 4.3 it follows that | ker√κZK | ≤ 8/q(K). Since the extension K/K0 is ramified at a prime ideal of Q( d) above p, the norm map NK/K0 is surjective on Cl+ (ZK0 ), hence | coker κZK | ≤ 4/q(K).

F

Key exchange from R2

We now delve into the details of generating concrete parameters for a Diffie– Hellman style key exchange protocol built from Shimura class group actions, along the usual diagram depicted in Figure 1. We emphasize that the construca

b

a

r g1 1 g2 2 ···ga r

(A, λ, ι) b

(AA , λA , ιA ) b

r g11 g22 ···gb r

b

r g11 g22 ···gb r

(AB , λB , ιB )

a

a

r g1 1 g2 2 ···ga r

(AAB , λAB , ιAB )

Fig. 1. Diffie–Hellman key exchange based on Shimura class group actions, for a set of “generators” g = {g1 , . . . , gr } ⊂ C(R) and exponents sampled from {−B, . . . , B}r .

tion below was done for proof-of-concept purposes only: we leave considerable room for optimization, and the security remains to be assessed more thoroughly. For the appealing reasons mentioned in Section 4.4, we concentrate on the R2 orientations from Appendix C (see also Example 3.4), where the entire orbit is defined over Fp . The “best” family to work with seems to be R2-D4. Indeed, in R2-C4 the parameters are quite constrained, hindering parameter generation, while R2-D2 has security issues [50]. F.1

Key exchange from R2-D4

Recall that R2-D4 is a (not necessarily primitive) orientation by R = Z[γ] with q √ √ a + |b| p < 0. γ = a + b p, Note that

√ γ̄γ = d := −a − b p ∈ R0+ 56

so in order to represent ι(γ), as explained in Section 4.3 we can stay in dimension √ √ 2 as soon as we can write N − d = α2 for some α = s + t p ∈ Z[ p]. This spells out as: – 2st = b, – s2 + pt2 = N + a, showing that we cannot let b = ±1, which is a necessary condition for Z[γ] to be maximal. We choose b = 4, and then we can assume that s = 2, t = 1 so that a = p + 4 − N .21 Enforcing complete splitting of small primes. For an efficient evaluation of the Shimura class group action in the g-REGA model, we want that A[ℓ] is “easily accessible”, for every small odd prime ℓ involved in the construction of g. In view of Remark C.1 the most natural sufficient condition is ℓ | p − 1, so that A[ℓ] ⊂ A(Fp2 ). Then ℓ splits completely in R if and only if a ± 4 are both non-zero quadratic residues modulo ℓ. Interestingly, since a = p + 4 − N ≡ 5 − N mod ℓ, this condition does not explicitly depend on a and/or p. So the idea is to collect small prime numbers ℓ1 , ℓ2 , . . . , ℓr modulo which both 9 − N and 1 − N are non-zero quadratic residues; for a fixed value of N we expect this to hold for a proportion 14 of the primes (within the wiggle room one typically has when choosing N , one can give preference to the value giving rise to the smallest ℓi ). We then choose p = M cℓ1 ℓ2 · · · ℓr + 1 with M a large factor of N and c a small cofactor ensuring √ that p is a prime number. Here, more precisely, we take N = M 2 so that A[ N ] ⊂ A(Fp2 ) for the purpose of meet-in-the-middle. Realization as an instance of R2-D4. For an incorporation into the R2-D4 family we need |a| > p/4 and consequently N = p + 4 − a > 5p/4. This comes about as follows. Recall from Example C.4 that our task is to find integers a1 , a2 , a3 , b1 , b2 , b3 such that p+1 2 p+1 2 a2 − pa23 − b21 − b1 b3 − b − b22 , 4 4 3 4 = b = a2 b1 + (a1 + a2 )b3 − 2a3 b2 . a = −a21 − a1 a2 −

These formulae can be rewritten as −4a = A2 + B 2 + 4b22 + p(a22 + 4a23 + b23 ), 8 = Ab3 + Ba2 − 4a3 b2 , 21

The reason we skip b = 2 is that in this case a = p+1−N . Since we will choose p such that p − 1 and N share a large prime power M , implying a2 − b2 p ≡ (2 − N )2 − 4 ≡ 0 mod M , it follows that disc K plummets in view of [48, Thm. 1 and Tbl. B].

57

where A = 2a1 + a2 and B = 2b1 + b3 . So the bound |4a| > p is immediate. Typically this is not enough: we want some extra leeway in order for the following solving strategy to succeed: iterate over positive integers n = 1, 2, 3, . . . and over all vectors (a2 , 2a3 , b3 ) ∈ Z × 2Z × Z of squared-Euclidean length n until we can find a corresponding vector (A, B, 2b2 ) of squared-Euclidean length −4a − np in the affine plane H : b3 X + a2 Y − 2a3 Z = 8, where moreover we want that A ≡ a2 mod 2 and B ≡ b3 mod 2, so that a1 = (A − a2 )/2 and b1 = (B − b3 )/2 are integers. This can be turned into an efficient algorithm, but for generating the concrete parameters below we have used a simplified search by restricting to a3 = 0 and gcd(a2 , b3 ) = 1; this is good enough for our proof-of-concept purposes, although it increases the expected number of n’s to be tried and therefore requires a somewhat larger gap between |4a| and p. To proceed, we use the extended Euclidean algorithm to compute λ, µ ∈ Z such that 1 = λb3 + µa2 . Then for any x, b2 the tuple (8λ + xa2 , 8µ − xb3 , 2b2 ) lies in H. Expressing that it has squared-Euclidean length −4a − np amounts to 2

(nx + 8(λa2 − µb3 )) + 4nb22 = −4na − n2 p − 64. This asks to represent the right-hand side by the positive definite binary quadratic form X 2 + 4nY 2 . If this right-hand √ side is prime, √ then we expect it to be representable with probability 1/2h(Z[ −4n]) ≈ 1/ n by [30, Thm. 9.12] and in that case a corresponding representation can be found efficiently using Cornacchia’s algorithm. Three remarks are in order: – We model −4na − n2 p − 64 as a random integer of size polynomial in p, so that we expect success after a number of tries that is polylogarithmic in p. However if 3 | a and p ≡ 2 mod 3 then using 3 ∤ n (indeed, n is a sum of coprime squares) one sees that −4na − n2 p − 64 is always divisible by 3, so in these cases the modeling is clearly flawed.22 But in our parameters below we have 3 ∤ a and p ≡ 1 mod 3 and this is not a concern. – If this integer can indeed be represented as c2 + 4nd2 for certain c, d ∈ Z, then there is no guarantee that c = nx + 8(λa2 − µb3 ) for some x ∈ Z. This may seem a strong additional assumption but luckily it is not: one checks that (λa2 − µb3 )2 ≡ −1 mod n and therefore c2 ≡ (8(λa2 − µb3 ))2 mod n. E.g., if n is prime then this implies c ≡ ±8(λa2 − µb3 ) mod n so by changing the sign of c if needed we can ensure that c is of the form nx + 8(λa2 − µb3 ). If n is not prime then this may fail but in any case, in view of the Erdös–Kac theorem, the inverse probability of success is in the order of log n rather than in the order of n as one might expect at first sight. – If n is even then −4na − n2 p − 64 ≡ 0 mod 4 so the primality assumption forces n to be odd. It is then easy to check that the requirements A ≡ a2 mod 2 and B ≡ b3 mod 2 are automatic. 22

Other deviating features are that if n is even then −4na − n2 p − 64 ≡ 0 mod 4, while if n is odd then −4na − n2 p − 64 ≡ 1 mod 4. We did not observe a noticeable effect on the runtime of our method.

58

Artifact of p ≡ 3 mod 4: N cannot be a power of 2. Ideally, we would like N to be a large power of 2, but this conflicts with M | p − 1 given the R2-D4 assumption p ≡ 3 mod 4. It should be clear to the reader that this assumption is not crucial: e.g., Example C.5 where p ≡ 5 mod 8 also produces instances of type D4 . Switching to p ≡ 1 mod 4 will be more technical (by lack of a uniform description of Bp,∞ ) but should be perfectly doable. We will by-pass this by letting M = 3f , N = 32f for some exponent f . Group size. Recall from (16) that the discriminant of Z[γ] equals 216 p2 (a2 − 16p). But Z[γ] is not a maximal order; in fact it has index b2 = 16 in the order √ √ Z[γ, p], by which our PPASs are still naturally oriented; consequently Z[γ, p] 8 2 2 has discriminant 2 p (a − 16p). This order is still not maximal, but almost: using that a = p + 4 − 32f and p ≡ 1 mod 3f for some large f , one verifies a2 − 16p ≡ 4 mod 8,

a2 − 16p ≡ 9 mod 27,

and then from [48, Thm. 1 and Tbl. B] it follows that the discriminant of the maximal order is 26 p2 (a2 − 16p)/9, if we assume that (a2 − 16p)/36 is squarefree (very likely true for the parameters below). We believe that the orientation √ by Z[γ, p] is typically primitive, but recall from Remark 4.8 that it is not crucial to know this for sure, as long as the security is based on the maximal order in view of potential hidden stabilizer attacks, as well as to avoid potential “walking up the volcano” attacks (see Section 7). In any case the relevant discriminant is √ of order p2 a2 and, since we expect h+ (Z[ p]) to be very small (see the footnote to Corollary 5.15), in view of the Brauer–Siegel theorem it is fair to estimate the size of the Shimura class group as p|a|. Remark F.1. In particular this is unbounded: by letting |a| grow we can reach arbitrarily large group sizes while working exclusively with varieties defined over 2 Fp ; this is impossible in dimension g = 1. This being said, as soon √ as |a| ⪆ p 2 we necessarily have N ⪆ p and p − 1 can no longer host M = N as a factor, which creates trouble for representing the orientation ι using meet-in-the-middle. One can circumvent this by using smaller values of M and publishing auxiliary PPASs as part of the orientation data. E.g., one can let N = M 3 be a cube and choose parameters such that M | p − 1. To represent ι(γ), note that our N -isogeny ι(γ)+α necessarily factors as a composition κ3 ◦κ2 ◦κ1 of M -isogenies: κ

κ

κ̂

1 2 3 (A, λ) −→ (B, λB ) −→ (C, λC ) ←− (A, λ).

If we provide interpolation data on A[M ] then this is enough for recovering the outer isogenies in this diagram. We can then append ker κ2 ⊂ B[M ] to our description of (A, λ, ι) as a PPAS. When evaluating the action, this whole diagram can be pushed through. This is somewhat reminiscent of the technique used in [46], but a full generalization of the method from [46] is left for future research. 59

Concrete parameters. We have generated parameters aiming for a Shimura class group size of roughly 2048 bits, which should be compared with CSIDH4096, aiming for NIST-I security. We choose |a| ≈ N ≈ p to maximize the room available in p − 1 for packing small primes ℓ (but this also maximizes the field size, so other choices can be made here). We must in fact take N slightly larger than p to create leeway for the generation of corresponding R2-D4 parameters. Within our range of interest, it turns out that N = 32f with f = 333 admits a more-than-average number of small primes ℓ modulo which 9 − N and 1 − N are non-zero squares. Concretely we can use the following 56 primes ℓi 23, 43, 53, 61, 67, 97, 101, 103, 173, 197, 211, 227, 233, 257, 277, 283, 293, 307, 313, 359, 373, 383, 397, 419, 433, 443, 457, 491, 521, 563, 577, 601, 613, 673, 683, 691, 733, 743, 769, 787, 809, 811, 859, 883, 887, 911, 977, 983, 1069, 1151, 1163, 1187, 1193, 1237, 1249, 1259, let p = 2 · 3f +2 · 7 · ℓ1 · · · ℓ56 + 1, and then set a = p + 4 − N as required (observe the extra factor 32 which is convenient for gluing in the middle). The respective bit lengths of p and |a|, N are 1021 and 1056, making for a Shimura class group estimate of 2077 bits. Using trial division we checked that (a2 − 16p)/36 contains no squares of primes smaller than 240 , so this discriminant factor is most likely square-free, but we could not check this rigorously.23 Concrete R2-D4 parameters can be found with a2 = 1758, a3 = 0, b3 = 565 so that n = a22 + b23 = 3409789, which is prime. The reader can then verify that also −4na − n2 p − 64 is prime and representable by the form X 2 + 4nY 2 , eventually yielding a1 =

72447886291797740848322932962051593473734748284190344 65405345610109441454835644829643664359635439561189660 15384207541540878628641645549368269105214510733042954

b1 = −23283876993666509430775004052081427936666742195999741 02931752144318449614324311336034511014331071303795311 71042137236046983177009402579859540412085437180984222 b2 =

23122390115850551190499797644857286144606472585743281 92024567734772318935855806010161778248613700364778186 274082288575193881983650751959251785841361677700367

for the remaining R2-D4 parameters. These integers are roughly of size 3f . Isogeny computations involved. Recall the count from (4): to reach a key space size having roughly 256 bits, we want (2B + 1)2·56 ≈ 2256 , 23

One way to get around this is by randomizing the cofactor c, used to construct p, until a2 − 16p is easy to factor (i.e., a prime number times a smooth cofactor).

60

showing that B = 2 suffices. This means that each arrow in Figure 1 amounts to at most 2 · 56 · 2 = 224 actions by Shimura ideals of the form (a, ℓi ). Each such action involves the computation of 2 isogenies of reduced degree 3f that “meet in the middle”, plus some linear algebra to determine the kernel, followed by an isogeny of reduced degree ℓi . All these isogenies are between PPAVs of dimension 2. F.2

Key exchange from R2-D2

We mention once again that the vectorization problem from the R2-D2 orientation, as it was introduced in Example 3.4, can be reduced to vectorization problems for the √ ideal-class groups of the underlying imaginary quadratic rings √ Z[ −p] and Z[ −dp] and therefore does not reach the security level one would hope [50]. We nevertheless include a quick, high-level discussion. On one hand, we do this for the sake of context for [50]. On the other hand, it allows us to highlight an interesting connection between R2-D2 orientations and the “higher-degree” supersingular group actions studied by Chenu–Smith [22], used√in Orient Ex√ press [16]. These concern actions by Cl(Z[ −dp]) on the set of Z[ −dp]-oriented elliptic curves (E, ι). Generators. Following Section 4.1 the generating set g is built from the group √ √ homomorphism κR : Cl(Z[ −dp]) × Cl(Z[ −p]) → C(R). That is, we pick a set of “easy” ideal classes p √ [m1 ], [m2 ], . . . , [ms ] ∈ Cl(Z[ −dp]), [l1 ], [l2 ], . . . , [lt ] ∈ Cl(Z[ −p]) and let g be the collection of images of ([mi ], 1), i = 1, . . . , s and (1, [li ]), i = 1, . . . , t. Abusing language, we will say that we act with [mi ] when in fact acting with κR ([mi ], 1), and likewise for [li ]. The ideals li are chosen as in CSIDH. That is, we set things up such that ℓ1 ℓ2 · · · ℓt | p + 1 for distinct small odd √ √ prime numbers ℓi and we let li = (ℓi , −p − 1). Then l̄i = (ℓi , −p + 1) is a representative of [li ]−1 . For the ideals mi , we consider distinct small odd prime numbers mi such that m1 m2 · · · ms | p + 1 and such that for all i = √ 1, 2, . . . , s there exists ai ∈ Z such that d ≡ a2i mod m√i . We then let mi = (mi , −dp − ai ) so that [mi ]−1 is represented by m̄i = (mi , −dp + ai ). The sets {ℓ1 , . . . , ℓt } and {m1 , . . . , ms } need not be disjoint. Remark F.2. Recall from Lemma 4.3 that κR is “almost” an isomorphism. See Example E.6 for a specialization of this lemma to R2-D2. Parameters. The data needed for setting up R2-D2 are in accordance with those needed for the “square-free” case of Orient Express [16]. There too, one looks for a supersingular elliptic curve E/Fp2 on which πp2 = −p, admitting a degree-d isogeny τ : E → E (p) such that τ̂ ◦ π√ p = πp ◦ τ , and such that many small odd primes ℓ divide p + 1 and split in Z[ −dp]. Therefore, we can recycle the parameters from [16, §5]. 61

Acting on the starting surface. Interestingly, the higher-degree supersingular group action can be “embedded” in a Shimura √ class group action. Indeed, −dp], it is not hard to show given an elliptic curve (E, ι) that is oriented by Z[ √ that ι( −dp) factors as πp

τ

E −→ E (p) −→ E for a degree-d isogeny τ satisfying τ̂ ◦ πp = πp ◦ τ [16, Lem. 1], so we can build an R-oriented PPAS from this exactly as in R2-D2. In view of the Weil restriction involved, let us denote this surface as W (E, ι) ∈ MFp (R). It is then easy to verify the rule κR ([m], 1) ⋆ W (E, ι) = W ([m] ⋆ (E, ι)), whence the said embedding. This means that during public-key generation, acting with the [mi ]’s can be done at the cost of an Orient Express action, as claimed. In particular, this evaluation only uses isogenies between elliptic curves over Fp2 (although Orient Express uses 2-isogenies between abelian surfaces for interpolating τ ). Subsequently acting with the [li ]’s is similar to CSIDH and also very efficient, since the orientation representation comes for free.

Acting on a public key. But acting with the [mi ]’s on a public key, which is not necessarily a Weil restriction, requires us to switch to the machinery from Section 4.3. The parameters in Orient Express are such√that 22a − d = α2 for certain integers a, α. This means that the d-isogeny ι( d) can be represented in dimension 2ug = 2 · 1 · 2 = 4 using Theorem 4.4. Unfortunately, here the dimension-halving trick from Section 4.3 does not seem to work. The asymmetry between both types of actions is summarized in Figure 2.

A0

√ mA ⊂Z[ −dp]

Adp A

√ lA ⊂Z[ −p]

AA

√ mB ⊂Z[ −dp]

√ mB ⊂Z[ −dp]

Adp B

Adp BA

√ lB ⊂Z[ −p]

√ lB ⊂Z[ −p]

AB

√ mA ⊂Z[ −dp]

Adp AB

√ lA ⊂Z[ −p]

AAB

Fig. 2. An illustration of the R2-D2 key exchange. Blue arrows represent actions computed via 1-dimensional isogenies, with a 2D representation of the orientation; green arrows represent actions computed via 2-dimensional isogenies; orange arrows represent actions computed via 2-dimensional isogenies, with a 4D representation of the orientation. Polarizations and orientations are omitted to lighten the notation.

62

G

Compressing interpolation data for R2

In this appendix we discuss the problem of compressing the interpolation data √ P, ι(γ)(P ), with P iterating over a basis of A[ √N ], in the context of the R2 orientations. To ease notation, let us write M = N . We also assume M | p ± 1 where the sign depends on whether we are working in the R2-D2 setting (+) or the R2-D4, R2-C4 settings (−). In view of Remark C.1 this ensures that all interpolation points are defined over Fp2 . Since ι(γ) is defined over Fp (indeed, it commutes with Πp ), it respects eigenvectors of Frobenius. In particular it maps the 1-eigenspace of Frobenius 2  Z A[M ](Fp ) ∼ = MZ into itself, and likewise for the −1-eigenspace (which has the same group structure). To use this for compression purposes, let us first recall that a “symplectic basis” of A[M ] is a basis P1 , P2 , Q1 , Q2 such that eM (Pi , Qj ) equals ζM if i = j and 1 if i ̸= j, where ζM ∈ Fp2 denotes some fixed primitive M th root of unity, whereas eM (Pi , Pj ) = eM (Qi , Qj ) = 1 for all i, j. Assuming M is odd (the even case is slightly more technical; note that M is odd in our protocol from Appendix F.1), we make the following case distinction: – If M | p + 1 as in R2-D2 then it is possible to choose a symplectic basis of A[M ] such that ⟨P1 , P2 ⟩ is the 1-eigenspace and ⟨Q1 , Q2 ⟩ is the −1eigenspace. – If M | p−1 as in R2-C4 and R2-D4 then one can choose it such that ⟨P1 , Q1 ⟩ is the 1-eigenspace and ⟨P2 , Q2 ⟩ is the −1-eigenspace. The second case where Π 2 = p follows from [28, Lem. 3.17 and Lem. 5.1]. The first case where Π 2 = −p is easier and well-known; e.g., it follows along the same lines as [28, Lem. 3.17]. Henceforth, we assume that P1 , P2 , Q1 , Q2 is a deterministically generated basis of the above kind. It now suffices to describe ι(γ)(Pi ), i = 1, 2 by means of 4 coefficients s, t, u, v ∈ Z/M Z. E.g., in the case of R2-D2, these indicate that ι(γ)(P1 ) = sP1 + tP2 ,

ι(γ)(P2 ) = uP1 + vP2 .

To expand the representation: we know that ι(γ)(Q1 ) = xQ1 + yQ2 ,

ι(γ)(Q2 ) = zQ1 + wQ2

for x, y, z, w ∈ Z/M Z that can be determined through Weil pairing and discrete logarithm computations (in practice M is smooth so this can be done efficiently). Concretely we find sx + ty = logζM eM (ι(γ)(P1 ), ι(γ)(Q1 )) = logζM eM (P1 , ι(d)(Q1 )), where we have used that ι(γ)† ι(γ) = ι(γ̄γ) = ι(d) using the notation from Section 4.3, and similarly obtain ux + vy from which we can extract x, y. We similarly find z, w and conclude. 63

H

Proofs from Section 5

H.1

The Shimura class group action via matrix arithmetic

Let g, a, b1 , b2 ∈ M2 (O) be algebraic data associated with an oriented superspecial PPAS, as in Section 5. Let (a, µ) be a Shimura ideal of R = Z[a, b1 , b2 ]. For γ a generator of the left M2 (O)-ideal generated by a, we consider g ′ := γ −∗ gµγ −1 ,

a′ := γaγ −1 ,

b′i := γbi γ −1 , i = 1, 2

as in the proof of Theorem 5.4. We now give a direct argumentation, essentially using matrix arithmetic only, for why this is a well-defined group action. Why g ′ is a valid g-matrix. In Remark 5.2 we already explained why g ′ is positive-definite and self-conjugate of norm 1. So in order to prove that it concerns a valid g-matrix, we need to show that g ′ ∈ M2 (O). This claim is equivalent to g −1 g ′ ∈ M2 (O) as g is an invertible element in M2 (O). This can be rewritten as γ −† µ ∈ M2 (O)γ. The ideal a can be generated by r ∈ R and µ with the property that r† r = r0 µ where the norm of r0 is coprime to the norm of a. Since γ is the generator of the extended ideal one has that sγ = r for some s ∈ M2 (O) which can be rewritten as γ = s−1 r. Note that γ −† µ ∈ M2 (O) by the Shimura property of the ideal. So we only need to show that γ −† µ vanishes on the kernel of a as then by definition it belongs to the left ideal generated by γ. One has γ −† µ = s† r−† µ = s† rµ−1 r0−1 µ = s† rr0−1 = s† r0−1 r. Here we used the identity r† r = r0 µ as r−† = rµ−1 r0−1 . This shows that indeed the above element vanishes on the ideal kernel by the properties of r0 . Why g ′ , a′ , b′1 , b′2 are valid algebraic data. Since conjugation by any invertible element is an automorphism of M2 (Bp,∞ ), one has that γaγ −1 , γb1 γ −1 , γb2 γ −1 generate a CM order isomorphic to R = Z[a, b1 , b2 ] but we also have to show that Rosati acts as conjugation on them and we also have to show that both lie in M2 (O). We will do the calculation for a but the calculation for the bi ’s is identical. We need that (γ −∗ gµγ −1 )−1 (γaγ −1 )∗ (γ −∗ gµγ −1 ) = γaγ −1 . The left-hand side can be rewritten as (γµ−1 g −1 γ ∗ )(γ −∗ a∗ γ ∗ )(γ −∗ gµγ −1 ) = γµ−1 (g −1 a∗ g)µγ −1 . Finally, γµ−1 (g −1 a∗ g)µγ −1 = γaγ −1 as a was symmetric with respect to Rosati and a and µ commute. What remains is that γaγ −1 and γbi γ −1 are indeed in M2 (O). We show it again only for a as the other cases are very similar. The condition γaγ −1 ∈ M2 (O) is equivalent to γa ∈ M2 (O)γ which is the left ideal generated by γ. The 64

left ideal generated by γ consists of exactly those endomorphisms that vanish on the kernel of a, so we need to show that γa vanishes on the kernel of a. Now γ = s−1 r, so γa = s−1 ra = s−1 ar. Now since the reduced norm of s is coprime to the norm of a and r is in a, γa will indeed vanish on the kernel of a (the proof carries over to b, as we have only used the fact that a and r commute). H.2

Omitted proofs

Proof (of Lemma 5.3). Writing  g=

sr r̄ t



with s, t ∈ Q>0 and r ∈ Bp,∞ , we can decompose this matrix as     s0 1 0 ∗ g=γ γ , γ = −1 , 0 t′ s r̄ 1 with t′ = t − s−1 n(r). We have t′ > 0 by positive-definiteness. By the Hasse– Schilling theorem [94, Thm. 14.7.4] we can write s = σσ̄ and t′ = τ τ̄ for certain quaternions σ, τ . It follows that   σ0 h=γ 0τ ⊓ ⊔

is of the requested kind.

Proof (of Lemma 5.8). First we compute what the centralizer of a is. Since the centralizer is a purely algebraic object, it is enough to prove it for matrices of the form   0s (17) 10 where s ∈ Z>0 . Indeed, quadratic fields can be generated by trace-0 elements and all pairwise isomorphic quadratic subfields of M2 (Bp,∞ ) are conjugate to each other by the Noether-Skolem theorem. The centralizer of (17) will be the set of matrices of the form   x sy y x where x, y ∈ Bp,∞ . This naturally decomposes as the tensor product of diagonal matrices (isomorphic to Bp,∞ ) and Q(a). Then we observe that if b ∈ M2 (Bp,∞ ) commutes with a, then so does b† (its Rosati involution). Indeed, if ab = ba, then b† a† = a† b† and then b† a = ab† as a† = a. This shows that Rosati induces an involution on C = Q(a) ⊗ Bp,∞ but we also need a stronger statement. Observe that for any element c ∈ C, the element c† c is symmetric with respect to Rosati. Due to the positivity of the Rosati involution, c† c will generate a totally real quadratic subfield of C. However, since C is isomorphic to Q(a) ⊗ Bp,∞ , the only such subfield is the 65

center. Thus Rosati defines a standard involution on C (i.e., for every c ∈ C, the element c† c lies in the center [94, Rmk. 3.2.5]) and for quaternion algebras there exists a unique such involution which is quaternion conjugation. ⊔ ⊓ Proof (of Lemma 5.10). The decision version is folklore (e.g., it follows from [52, §6]), hence we focus on the embedding problem. √ First, we compute an explicit √ isomorphism between C ⊗K K( d) and M2 (K( d)) in quantum polynomial √ time [60]. Using this isomorphism we can find an element s ∈ C ⊗K K( d) for which s2 = 0. Now if we write √ √ √ √ s = (s1 + r1 d) + (s2 + r2 d)i + (s3 + r3 d)j + (s4 + r4 d)k then we get that s1 = r1 = 0 as its trace is 0 and if we square it and look at the rational part we get n(s2 i + s3 j + s4 k) = −d n(r2 i + r3 j + r4 k) which implies that the norm of (s2 i + s3 j + s4 k)/(r2 i + r3 j + r4 k) equals −d. Now we only have to show that the trace of this element is 0. The trace of this element is s2 r2 i2 + s3 r3 j 2 + s4 r4 k 2 −2 n(r2 i + r3 j + r4 k) √ which is 0 as the numerator equals the coefficient of d in s2 . This proves our lemma. ⊔ ⊓ Proof (of Lemma 5.14). We first note that ξ, γ indeed exist, respectively because of Lemma 5.3 and the fact that M2 (O) is a principal ideal ring. Next we claim that the conductor ideal can be characterized as c = { α ∈ K | αγ ∗ ∈ γ −1 M2 (O)}. To see this: it is clear that γ −1 M2 (O) can be characterized as the set of matrices x ∈ M2 (Bp,∞ ) such that ZK x ⊂ M2 (O). Let α ∈ K. Using that γ ∗ M2 (O) = (M2 (O)γ)∗ = (M2 (O)ZK )∗ = ZK M2 (O) along with the commutativity of K we see that ZK αγ ∗ M2 (O) = αZ2K M2 (O) = αZK M2 (O), whence the claim. As a consequence we have κ := γµγ ∗ ∈ M2 (O). Below we show that in fact κ ∈ GL2 (O). Assuming this, the lemma follows fairly easily. Indeed, let Λ′ = γ −1 M2 (O)γ be the right order of M2 (O)γ = M2 (O)ZK and observe using Z2K = ZK that this right order contains ZK . Then its conjugate Λ contains ξ −1 ZK ξ and the computation Λ∗ = ξ ∗ γ ∗ M2 (O)γ −∗ ξ −∗ = ξ −1 γ −1 κM2 (O)κ−1 γξ = ξ −1 γ −1 M2 (O)γξ = Λ shows that it is closed under conjugate-transpose. The fact that ι(ᾱ) = ι(α)∗ for all α ∈ ZK follows from (ξ −1 αξ)∗ = ξ ∗ α∗ ξ −∗ = ξ −1 α∗ ξ for all α ∈ K, where in turn the last equality follows from the fact that ξξ ∗ = µ commutes with α. Proving that κ ∈ GL2 (O) amounts to showing n(γµγ ∗ ) = 1. To establish this, it suffices to produce for every prime number ℓ | n(µ) some element µℓ ∈ c 66

such that ℓ ∤ n(γµℓ γ ∗ ). It is indeed allowed to skip the primes ℓ ∤ n(µ) (which include p by assumption) because in those cases ZK ∩ M2 (O) is locally maximal at ℓ, implying that also n(γ) must be an ℓ-adic unit, and therefore ℓ ∤ n(γµγ ∗ ). Instead of finding µℓ directly, we will produce an element νℓ ∈ Kℓ such that γνℓ γ ∗ ∈ GL2 (Oℓ ), where Kℓ = K ⊗Z Zℓ , Oℓ = O ⊗Z Zℓ . This is good enough indeed, because if we then pick νℓ′ ∈ K with the same l-adic valuation as νℓ for every non-zero prime ideal l | ℓZK (which is always possible by the Chinese remainder theorem), then also γνℓ′ γ ∗ ∈ GL2 (Oℓ ). It then suffices to let µℓ = nνℓ′ for a suitable integer n; e.g., we can consider any positive integer m such that mνℓ′ is an integral multiple of µ and choose n such that n ≡ 1 mod ℓ and n ≡ m modulo all prime divisors of m different from ℓ. Recall that ZK is contained in the right order of M2 (O)γ, which implies that γ −1 M2 (O) is closed under left-multiplication with elements from ZK . It is then also true that γ −1 M2 (Oℓ ) is closed under left-multiplication by ZK,ℓ = ZK ⊗Z Zℓ . Fix an isomorphism Bp,∞ ⊗Z Zℓ ∼ = M2 (Qℓ ), which through component-wise application also yields an isomorphism M2 (Bp,∞ ⊗Z Zℓ ) ∼ = M4 (Qℓ ). We can then consider the Zℓ -lattice L = γ −1 L0 , L0 = Z4ℓ (18) by viewing the elements of L0 as column vectors. Observe that this is again closed under left-multiplication by ZK,ℓ . This gives L the structure of a ZK,ℓ module. A crucial observation is that this module is free of rank 1. To see why, consider the module Y M Ml over Kℓ ∼ Kl γ −1 Q4ℓ = = non-zero prime ideals l | ℓZK

l | ℓZK

where Kl denotes the completion of K at l and the decomposition on the left is obtained by acting on the whole module with subsets of Kℓ of the form {0} · · · × Kl × · · · × {0}. Each Ml is a vector space over Kl and, since both Kℓ and γ −1 Q4ℓ have dimension 4 as vector spaces over Qℓ , we have dimKl Ml = 1 for all l, i.e., γ −1 Q4ℓ is a free Kℓ -module of rank 1. Switching to the “integral side”, namely the module Y M ZK,l , L = γ −1 Z4ℓ = Ll over ZK,ℓ ∼ = l | ℓZK

l | ℓZK

and using that the ZK,l ’s are PIDs, we can deduce the same desired statement: L is a free rank-1 module over ZK,ℓ . In other words L = ZK,ℓ v

(19)

for some v ∈ Q4ℓ . We now consider a Qℓ -bilinear form ⟨·, ·⟩ on Q4ℓ such that ⟨µv, w⟩ = ⟨v, µ∗ w⟩ for all v, w ∈ Q4ℓ and all µ ∈ M2 (Bp,∞ ). While such a bilinear form exists for general reasons [55, §1], let us make this explicit by noting that   0 1 ā = H −1 aT H, H= , −1 0 67

independently of the chosen isomorphism: this merely uses that ā = tr(a)−a. We can then let ⟨v, w⟩ = v T diag(H, H)w. Then using ⟨γ ∗ v, γ −1 w⟩ = ⟨v, γγ −1 w⟩ = ⟨v, w⟩ for all v, w ∈ Q4ℓ we find that the dual lattice of L with respect to this form is given by L∗ = { v ∈ Q4ℓ | ⟨v, L⟩ ⊂ Zℓ } = γ ∗ L0 . (20) But on the other hand, through (19) the form also induces a bilinear map Kℓ × Kℓ → Qℓ : (r, s) 7→ ⟨rv, sv⟩ = ⟨v, r̄sv⟩. Note that the right-hand side is a Qℓ -linear expression in r̄s. It is a standard property of the trace function that there must exist some δ ∈ Kℓ× such that ⟨v, r̄sv⟩ = TrK/Q (δr̄s), where we have extended the domain of TrK/Q to Kℓ by Zℓ -linearity. Indeed, this only requires that the trace pairing remains non-degenerate on Kℓ , which is immediate. Thus from this perspective we can also write L∗ = δ −1 D−1 v

(21)

with D the ideal of ZK,ℓ generated by the different ideal of K. Now ZK,ℓ is a principal ideal ring, again because ZK,ℓ is a product of PIDs, so we can rewrite this as L∗ = ZK,ℓ νℓ−1 v for some generator νℓ of δD. As the notation suggests, this is the element we are after. Indeed, comparing expressions (18), (19), (20) and (21) we see that γ −1 L0 = L = νℓ L∗ = νℓ γ ∗ L0 from which it follows that γνℓ γ ∗ ∈ GL2 (Oℓ ), as wanted. ⊔ ⊓

I

On the one endomorphism problem in dimension 2

The machinery from Section 5 allows us to prove 2-dimensional analogues of the first two statements in Section 5.4, which we recall here: – Given one non-scalar endomorphism on a supersingular elliptic curve, one can compute the rest of the endomorphism ring in subexponential time [45]. – Given an endomorphism of small degree (polylogarithmic in p) on a supersingular elliptic curve in characteristic p, one can compute the full endomorphism ring in polynomial time [66]. Our result strongly relies on Corollary 5.15, which for technical reasons was restricted to cases where R = ZK is a maximal order; for this reason we make the same restriction here. Theorem I.1. Let (A, λ, ι) be a superspecial PPAS oriented by ZK for a quartic CM field K and assume that h+ (K0 ) is polynomially bounded. There exists a heuristic sub-exponential quantum algorithm that computes the endomorphism ring of A. If the discriminant of K is polynomial in the input size, then the endomorphism ring of A can be computed heuristically in classical polynomial time. 68

Proof. As a first step we compute a ZK -oriented superspecial PPAV (A′ , λ′ , ι′ ) along with corresponding algebraic data g, a, b1 , b2 using Corollary 5.15, which is where the assumption on h+ (K0 ) comes into play. Then one can solve vectorization using Kuperberg’s algorithm between (A, λ, ι) and (A′ , λ′ , ι′ ). This has no solution if these oriented PPASs lie in different orbits. In that case one can retry with ι′ replaced with ι′ ◦ τ for some automorphism τ of K (which by Remark 6.14 amounts to taking the Frobenius conjugate in the case of complex conjugation), but if (A, λ, ι) and (A′ , λ′ , ι′ ) come from inequivalent CM types then this brings no solace. In those cases we retry with a new (A′ , λ′ , ι′ ) generated by Corollary 5.15: it is a heuristic assumption that this reaches all CM types up to equivalence. Note that this step is never needed for C4 -fields, because here all CM types are equivalent by Lemma 6.8. In any case, after O(1) tries we find [(a, µ)] ∈ C(ZK ) such that (A, λ, ι) = [(a, µ)] ⋆ (A′ , λ′ , ι′ ). Evaluating this action algebraically as described in Section 5.2, we end up with a g-matrix for A, from which its endomorphism ring can be extracted using [73]. If the size of the Shimura class group is polynomial in the input size, then instead of running Kuperberg one can simply compute this group and apply the action of every group element to (A′ , λ′ , ι′ ) until (A, λ, ι) is reached. ⊔ ⊓ Remark I.2. The reader might wonder why we have a specific statement for small discriminant CM orientations. The reason is that if one obtains an oriented superspecial PPAS by using CM reduction, then one immediately knows an orientation by a relatively small CM order. The above theorem then shows that in this case one can compute the full endomorphism ring in polynomial time, generalizing a result of Love and Boneh [66] to dimension 2.

J

The Gorenstein and Bass conditions

There are two standard ring-theoretic conditions on a CM order R ⊂ ZK that enter the Shimura class group action: Gorenstein and Bass. Gorenstein is the (mild) hypothesis under which the characteristic-0 Shimura–Taniyama transitivity theorem is expected to hold (see the footnote to Theorem 6.7 in Section 6.2). Bass is the hypothesis under which the ascending-walk picture mentioned in Section 7 is available [3]. Bass implies Gorenstein, but not conversely. This appendix records both notions, two sufficient conditions for Bass, and the index bound on the integer-polarized subgroup C(R)Z ⊆ C(R). Definition J.1. An order S in a number field is Gorenstein if it has Cohen– Macaulay type 1 at every maximal ideal m ⊂ S, that is, dimS/m ((S : m)/S) = 1 for every m. Equivalently, every fractional S-ideal a with (a : a) = S is invertible. The equivalence between the Cohen–Macaulay type condition and the invertibility of every proper fractional ideal is described in Marseglia [67, Proposition 3.4], where the two formulations go back to Bass [4]. If R is Gorenstein, every proper fractional R-ideal is invertible; this is the setting in which C(R) acts on proper-ideal classes and in which Theorem 6.7 describes orbits. 69

If R is not Gorenstein, then there exist proper fractional R-ideals a with (a : a) = R that are not invertible. In this case, the invertible-ideal action of C(R) does not cover these additional proper classes. Further, lifting non-transitivity on proper classes to a statement on PPAVs requires in addition that the extra classes admit a principal polarization of the prescribed CM type; the bimodule framework of [3] treats the non-Gorenstein case. Lemma 2.6 shows that for any CM order R, every square in C(R) is integerpolarized, so [C(R) : C(R)Z ] divides #C(R)[2]. The Bass hypothesis gives this bound a graph-theoretic meaning on the crater and underlies the volcano picture used in Section 7. Definition J.2. An order R in a number field L is called Bass if every overorder of R is Gorenstein. Equivalently, every fractional R-ideal is generated as an R-module by at most two elements. Remark J.3. The equivalence between the two formulations is treated in [67, Prop. 4.6]. This covers the classical results of Bass [4] and Drozd–Kirichenko– Roiter [37]. Two elementary sufficient conditions place R in the Bass-class: – Index-2 subfield. If R contains the maximal order of a subfield K ′ ⊂ K of index 2, then R is Bass. Maximal real multiplication (R ⊃ ZK0 ) is the main case we use, see [3, §2] and [67, Prop. 4.6]. – Fourth-power-free discriminant. If disc(R) is fourth-power-free in Z, then R is Bass, see [44, Thm. 3.6]. We give an example of a non-Bass CM order. √ Example J.4. Let K = Q(ζ5 ), a quartic CM field with K0 = Q( 5). Consider the two CM orders of conductor 2ZK R = Z + 2ZK , R′ = ZK0 + 2ZK . Complex conjugation sends ζ5 to ζ5−1√= ζ54 , so ZK = Z[ζ5 ] is stable under conjugation. The real subfield K0 = Q( 5) is pointwise fixed. Hence both R and R′ are closed under complex conjugation. The prime 2 is inert in ZK , so ZK /2ZK ∼ = F16 , R/2ZK ∼ = F2 and R′ /2ZK ∼ = F4 . Nakayama’s lemma (see e.g. [38]) gives µR (ZK ) = dimF2 (ZK /2ZK ) = 4 > 2, µR′ (ZK ) = dimF4 (ZK /2ZK ) = 2. By Definition J.2, R is not Bass and R′ is Bass. We write 2ZK = R · 2 + R · 2ζ5 + R · 2ζ52 + R · 2ζ53 and explain why all four generators are necessary to represent 2ZK . Write ZK = ⟨1, ζ5 , ζ52 , ζ53 ⟩Z , and 2ZK = ⟨2, 2ζ5 , 2ζ52 , 2ζ53 ⟩Z . 70

Using R = Z + 2ZK , we obtain R · 2 + R · 2ζ5 + R · 2ζ52 + R · 2ζ53 =

3 X

(Z + 2ZK ) · 2ζ5i

i=0

=2

3 X

Zζ5i + 4

i=0

3 X

ZK ζ5i

i=0

= 2ZK + 4ZK = 2ZK . P3 Here i=0 Zζ5i = ZK , and ZK ζ5i = ZK because each ζ5i is a unit of ZK . Let m = 2ZK , the maximal ideal of R above 2. Then ∼ (2ZK )/m(2ZK ) = (2ZK )/(4ZK ) −−→ ZK /(2ZK ) ∼ = F16 , where 2x 7−→ x.

Since R/m ∼ = F2 , the field F16 has dimension 4 as an F2 -vector space. By Nakayama’s lemma, the minimal number of generators of (2ZK )m over the local 2ZK = 4. Therefore the ring Rm equals this dimension µRm ((2ZK )m ) = dimF2 4Z K four displayed generators are necessary. Thus the fractional R-ideal 2ZK is not generated by at most two elements, and Definition J.2 shows that R is not Bass. For R′ , we have ZK0 ⊂ R′ and [K : K0 ] = 2, so the index-2 subfield criterion shows that R′ is Bass. The equality µR′ (ZK ) = 2 follows from dimF4 (F16 ) = 2. The structure of C(R) is given by the relative-norm presentation of equation (2) in Section 2.2. Hasse’s norm theorem for the quadratic extension K/K0 in [74, Cor. VI.4.5] describes the elements of K0× /NK/K0 (K × ) in terms of local Hasse symbols at the places of K0 ramifying in K/K0 . This is the input that controls the integer-polarized classes on a elements level. For R = ZK , Streng [93, Lem. I.8.4, Thm. III.2.2] shows that the cokernel of the type norm map into C(ZK ) has exponent dividing 2; the analogous result in dimension g = 3 is [36], where the exponent is 2 or 4 depending on the Galois type. In the integer-polarized version we expect a sharper statement, for which we have computational evidence in the maximal-order case. Conjecture J.5. Let K be a CM field and let R ⊆ ZK be a CM order. Then [C(R) : C(R)Z ] ∈ {1, #C(R)[2]}. Remark J.6. Our computational evidence is for maximal orders across the tested Galois types for g ∈ {2, 3}. Computations for non-maximal orders and higher dimensions are in progress and already provide further evidence for our claim.

K

Superspecial reduction

Reduction. We recall the superspecial reduction results Goren established for CM abelian surfaces in the primitive quartic case [42]. Goren did not consider the 71

biquadratic C2 × C2 case because his setup only allowed for so-called “primitive” CM types (see Section 7 for a definition). His argument, however, carries over almost verbatim and gives Proposition K.2 below, which we record as a new result even though its proof is analogous to Goren’s. As in [42], we restrict throughout this appendix to R = ZK and to primes p unramified in K; the ramified case is left for future work (see the end of this appendix). Proposition K.1. Let K be a cyclic quartic CM field, let p be a prime number not ramifying in K, and let (A, λ, ι) ∈ Mk (ZK ) with k = Q. Let L ⊂ k be a number field over which A is defined. Let p̄ ⊂ ZL be a prime ideal above p. Assuming the reduction A mod p̄ is good, it is superspecial if and only if p neither splits completely nor is inert in K. ⊔ ⊓

Proof. See [42, Thm. 1].

In other words, in the C4 case we have superspecial reduction if and only if pZK = p1 p2 for two degree-2 prime ideals pi of K. In the cases C2 × C2 and D4 , the factorization pattern of p in K alone does not distinguish superspecial from non-superspecial and the CM type Φ comes into play. It should be clear, however, that the reduction type can only depend on Φ up to equivalence. Proposition K.2. We inherit the assumptions from Proposition K.1 but now assume that K is biquadratic. We can assume, by precomposing ι with complex conjugation if needed, that the CM type of (A, λ, ι) is of the form Φ = {id, τ } for some τ ∈ Gal(K, Q). Let K1 be the fixed field of the subgroup Φ. Assuming the reduction A mod p̄ is good, it is superspecial if and only if p is inert in K1 . Proof. We can assume that L contains K and is Galois over Q. Ekedahl’s product criterion [39, Prop. 2.4], as discussed in [42, §2], says that A mod p̄ is superspecial if and only if σ Φ̄ext = Φext where σ ∈ Gal(L, Q) denotes a Frobenius element of p̄ (i.e., an automorphism such that σ(p̄) = p̄ which reduces to the p-th power Frobenius automorphism of ZL /p̄ over Fp ) and Φext denotes the set of elements of Gal(L, Q) whose restriction to K is contained in Φ (and likewise for Φ̄ext ). Now let σ res be the Frobenius element of p̄ ∩ K (unique since p does not ramify). This equals the restriction of σ to K, so Ekedahl’s criterion becomes: A mod p̄ is superspecial if and only if σ res ∈ / {id, τ }. The result follows. ⊓ ⊔ In other words, in the C2 × C2 case we have superspecial reduction if and only if pZK = p1 p2 for two degree-2 prime ideals pi of K and the splitting is complete in K0 or in the imaginary quadratic subfield different from K1 . As a sanity check, consider our recurring orientations by # " r √ 1 + −p − 4 p+1 Z , 2 4 72

in characteristic p ≡ 3 mod 4 from Examples 3.1 and 3.2, shown to come from two inequivalent CM types in Examples 6.4 and 6.11. By Proposition K.2 combined with the lifting statement from [43, Lem. 4.4.1] (which was used in our proof of Theorem 6.9), this must mean that p splits in K0 and is inert in the two imaginary quadratic subfields K1 , K2 . This is indeed easily checked. Proposition K.3. Let K be a quartic CM field with Galois closure M such that Gal(M, Q) = ⟨x, y | x2 , y 4 , (xy)2 ⟩ ∼ = D4 and that K = M ⟨x⟩ . Let Φ = {id, y} be a fixed CM type on K. Under the remaining assumptions of Proposition K.1, where we can assume M ⊂ L w.l.o.g., and with p unramified in M , the reduction A mod p̄ is superspecial if and only if the Frobenius element of p̄ ∩ M equals y 2 or xy. Proof. This is [42, Thm. 2] in cases (3) and (6). The two cases together are again seen to be equivalent to the product criterion of Ekedahl. ⊔ ⊓ This closes the unramified cases for dimension 2 (assuming R = ZK ). The ramified case, where p | disc(K/Q), is not covered by [42, Thm. 1 and Thm. 2]. In forthcoming work we treat this case by replacing the unramified product criterion with a Lie-type Dieudonné module calculation. The Shimura–Taniyama formula gives the Newton polygon, and the Lie type gives the a-number. Superspeciality is then the condition that all slopes are 1/2 and that a = g.

73

Related documents

• Strata Hasse Invariants on Proper Abelian Type Shimura Varieties and Applications to Galois Representations#642198
• Square-Free and Dual-Square-Free Abelian Groups#256602
• Ekedahl-Oort strata with a superspecial factor in unitary Shimura varieties#1357691
• The truncated symbol of a differential symmetry breaking operator#1399717
• Semisimplicity, purity and Mumford-Tate conjecture for hyper-Kähler varieties#1217625