Mingjie Chen
email: m.chen.1@bham.ac.uk

Antonin Leroux
email: antonin.leroux@polytechnique.org

SCALLOP-HD: group action from 2-dimensional isogenies

We present SCALLOP-HD, a novel group action that builds upon the recent SCALLOP group action introduced by De Feo, Fouotsa, Kutas, Leroux, Merz, Panny and Wesolowski in 2023. While our group action uses the same action of the class group Cl(O) on O-oriented curves where O

for a large prime f and small d as SCALLOP, we introduce a different orientation representation: The new representation embeds an endomorphism generating O in a 2 e -isogeny between abelian varieties of dimension 2 with Kani's Lemma, and this representation comes with a simple algorithm to compute the class group action. Our new approach considerably simplifies the SCALLOP framework, potentially surpassing it in efficiency -a claim to be confirmed by implementation results. Additionally, our approach streamlines parameter selection. The new representation allows us to select efficiently a class group Cl(O) of smooth order, enabling polynomial-time generation of the lattice of relation, hence enhancing scalability in contrast to SCALLOP. To instantiate our SCALLOP-HD group action, we introduce a new technique to apply Kani's Lemma in dimension 2 with an isogeny diamond obtained from commuting endomorphisms. This method allows one to represent arbitrary endomorphisms with isogenies in dimension 2, and may be of independent interest.

Introduction

The group action framework is a powerful abstract tool to build cryptographic protocols such as non-interactive key exchange [CLM + 18], signatures [BKV19], threshold schemes [CS20,DFM20], ring signatures [BKP20], group signatures [BDK + 23], partial-blind signatures [KLLQ23], updatable encryption [LR22], and, among other things, various applications as discussed in [ADFMP20].

Isogenies provide the only known way to instantiate this framework in a manner resistant to quantum computers. There are two achievable flavours of group action: the "restricted" group action (REGA) such as the one introduced for the CSIDH key exchange in [CLM + 18], and the "full" variant (EGA) introduced for the CSI-FiSh signature scheme in [BKV19]. While the restricted variant is already interesting, the full variant is required by the more elaborate constructions.

Unfortunately, isogeny-based group action suffer from various problems. First, the underlying hard problem can be solved in subexponential time by a quantum computer [BLMP19, BS20,Pei20] which renders their security hard to estimate and reduces their efficiency. Second, current methods for instantiating the full variant require subexponential precomputation as demonstrated in [BKV19,DFFK + 23] and reaffirmed in a recent blog post by Panny4 . This makes it computationally infeasible to obtain the full variant that meets the quantum security requirements from NIST.

The second obstacle is what motivated the introduction of the recent SCAL-LOP scheme in [DFFK + 23] where the precomputation (while still subexponential) is much more practical than in the setting of . The authors of SCALLOP demonstrated the interest of their constructions by scaling the parameters to sizes known to be computationally unreachable in the setting of CSI-FiSh. However, the efficiency of SCALLOP is much worse than CSIDH, and the amount of precomputation required to reach the higher levels of security (equivalent to the CSIDH-8192 variant of [CSCDJRH22] for instance) promises to be quite extensive.

The improvements in scalability achieved by SCALLOP, when compared to CSI-FiSh, arise from using a distinct group and set in the group action. However, in order to define their group action, the set elements are no longer just jinvariants of supersingular elliptic curves, but curves together with extra data called "orientation". The necessity of carrying the orientation and computing the group action on the orientation is what renders the efficiency of SCALLOP bad in comparison to CSI-FiSh.

Recently, the field of isogeny-based cryptography has seen a major breakthrough with the successful cryptanalysis of the SIDH key exchange scheme by [CD23,MMP + 23,Rob23]. This result was obtained by embedding isogenies between elliptic curves (isogenies of dimension 1) inside isogenies of higher dimension (2, 4 and 8) using Kani's Lemma [Kan97]. Since then, these novel ideas have been used several times to build some post-quantum protocols such as encryption [BMP23], signature [DLRW23], or VRF [Ler23]. In short, our new construction SCALLOP-HD uses these ideas to represent orientations more efficiently and this leads to various improvements over SCALLOP that we list in the next section.

Contribution.

In this work, we revisit the SCALLOP group action with the high dimensional isogenies at the heart of the attacks against SIDH. We show that these new techniques, and in particular, the idea of Robert [Rob22] that an arbitrary degree isogeny can be efficiently represented using high dimension isogenies allows us to simplify the framework of SCALLOP. Concretely, the improvements of SCALLOP-HD compared to the original SCALLOP can be summarized as follows:

1. A new orientation representation that uses the embedding techniques based of higher dimensional isogenies. 2. A simplified algorithm to compute the group action using Kani's Lemma in dimension 2 that we expect will improve the efficiency. 3. The improvement from a subexponential to a polynomial complexity of the computation of the class group's lattice of relation: the bottleneck in the precomputation required by SCALLOP. This leaves only the complexity required for performing lattice reduction algorithms on the lattice of relation the non-polynomial time part in precomputation of the SCALLOP-HD group action.

In doing so, we introduce a novel way of applying Kani's Lemma in dimension 2 by building isogeny diamonds from two endomorphisms lying in the same quadratic order. This can be used to represent orientations and endomorphisms in dimension 2. We believe this new technique is interesting in its own right, and it was recently used in [Ler23] to provide a new algorithm to perform the Deuring correspondence using isogenies in dimension 2. We also briefly discuss another example where this new technique can be used in a recent endomorphism division algorithm in Remark 13.

Organization of the paper. The rest of this paper is organized as follows.

In Section 2, we introduce necessary mathematical background. Then, Section 3 explains how to construct group action from isogenies and outlines the progress towards obtaining a scalable EGA. In Section 4, we present the new orientation representation alongside the resulting group action formula. Section 5 introduces the SCALLOP-HD group action. Section 6 discusses some remarks on the secruity of SCALLOP-HD. We conclude in Section 7 by summarizing the paper and discussing future work.

Preliminaries

2.1 Quaternion algebras, supersingular elliptic curves, isogenies and the Deuring correspondence Quaternion algebras Let p be a prime and let B p,∞ denote the unique (up to isomorphism) quaternion algebra ramified precisely at p and ∞. We fix a Q-basis ⟨1, i, j, k⟩ of B p,∞ that satisfies i 2 = -q, j 2 = -p and k = ij = -ji for some integer q. A fractional ideal I in B p,∞ is a Z-lattice of rank 4. We denote by n(I) the norm of I as the largest rational number such that n(α) ∈ n(I)Z for any α ∈ I. An order O is a subring of B p,∞ that is also a fractional ideal. An order is called maximal when it is not contained in any other larger order. A fractional ideal is

integral if it is contained in its left order O L (I) = {α ∈ B p,∞ | αI ⊂ I}, or equivalently in its right order O R (I) = {α ∈ B p,∞ | Iα ⊂ I}.
Supersingular elliptic curves and isogenies Let E, E 1 , E 2 be elliptic curves defined over a finite field of characteristic p. An isogeny from E 1 to E 2 is a nonconstant rational map that is simultaneously a group homomorphism. An isogeny from a curve E to itself is an endomorphism. The set End(E) of all endomorphisms of E forms a ring under addition and composition. End(E) is either an order in an imaginary quadratic field and E is called ordinary, or a maximal order in B p,∞ , in which case E is called supersingular.

The Deuring correspondence Fix a supersingular elliptic curve E 0 , and an order O 0 ≃ End(E 0 ). The curve/order correspondence allows one to associate to each outgoing isogeny φ : E 0 → E 1 an integral left O 0 -ideal, and every such ideal arises in this way (see [Koh96] for instance). Through this correspondence, the ring End(E 1 ) is isomorphic to the right order of this ideal. This isogeny/ideal correspondence is defined in [Wat69], and in the separable case, it is explicitly given as follows.

Definition 1. Given I an integral left O 0 -ideal coprime to p, we define the Itorsion E 0 [I] = {P ∈ E 0 (F p 2 ) : α(P ) = 0 for all α ∈ I}. To I, we associate the separable isogeny φ I of kernel E 0 [I]. Conversely given a separable isogeny φ, the corresponding ideal is defined as I φ = {α ∈ O 0 : α(P ) = 0 for all P ∈ ker(φ)}.

We summarize properties of the Deuring correspondence in

Quadratic orders and orientations on supersingular elliptic curves

Let d be a positive square-free integer and

K = Q( √ -d) be an imaginary quadratic field with discriminant D K . Let O ⊆ K be an order with discrim- inant D O . Explicitly, O = Z[ D O + √ D O 2 ]. Any element α ∈ O can be written as x + y D O + √ D O 2
with x, y ∈ Z, and {1, α} is a Z-basis of O if and only if y = 1. One can compute the norm of α and thus derive the norm form f O of O:

f O (x, y) = x 2 + D O xy + y 2 D O (D O -1) 4 .
* K /O * → (O K /(f )) * /(O/(f )) * → Cl(O)
→ 1, and they showed that

(O K /(f )) * /(O/(f )) * ∼ = F * f if f splits in K, F * f 2 /F * f if f is inert in K.
In particular, this suggests that Cl(O) is always cyclic as it is isomorphic to a quotient of a cyclic group, and Cl(O) is easy to compute in these cases. Furthermore, this implies that #Cl

(O) = f --1 f 1 |O * K |/2 .
Quadratic orders and their class groups are playing an increasingly important role in isogeny-based cryptography, in particular since Colò and Kohel introduced orientations on supersingular elliptic curves in [CK20]. In what follows, we recall the basic definitions and important properties regarding orientations. Definition 2. Let E be a supersingular elliptic curve over F p 2 , K be an imaginary quadratic field and O ⊆ K be a suborder. Then a K-orientation on E is a ring homomorphism ι : K → End(E) ⊗ Q. This K-orientation induces an O-orientation on E if ι(O) = End(E) ∩ ι(K). In this case, the pair (E, ι) is called a O-oriented curve and E is a O-orientable curve.

Note that here we use O-orientation to indicate the primitive O-orientation from [CK20].

Let E ′ be another supersingular curve and φ : E → E ′ be an isogeny. Let ι be a K-orientation on E, then there is an induced K-orientation ι ′ = φ * (ι) on

E ′ defined to be φ * (ι)(ω) := 1 deg(φ) φ • ι(ω) • φ ∈ End(E ′ ) ⊗ Q. An isogeny of K-oriented elliptic curves φ : (E, ι) → (E ′ , ι ′ ) is an isogeny φ : E → E ′ such that ι ′ = φ * (ι)
; we call this a K-oriented isogeny. A K-oriented isogeny is a K-isomorphism if it is an isomorphism of the underlying curves.

For a fixed imaginary quadratic order O ⊆ K, we consider the collection of all O-oriented curves and define the following set:

S O (p) = {(E, ι) | (E, ι) is an O-oriented curve}/ ∼,
where two oriented curves are equivalent if they are K-isomorphic.

Here we recall the following conditions for the set S O (p) to be non-empty.

Proposition 3 ([Onu21,Proposition 3.2]). The set S O (p) is not empty if and only if p does not split in K and does not divide the conductor of O.

When S O (p) is non-empty, the set of invertible O-ideals acts on it. Specifically, let a be an such an ideal and (E, ι E ) ∈ S O (p), then

a ⋆ (E, ι E ) := (E a , ι Ea ),
where E a is the codomain of the isogeny ϕ a whose kernel is E[a] := ∩ a∈a ker ι E (a) and ι Ea is the induced orientation on E a by ϕ a . Principal O-ideals act trivially on (E, ι E ), therefore this action induces an action of Cl(O) on S O (p). It was shown in [Onu21] that this is action is free and it has one or two orbits.

New isogeny representation in higher dimensions

An isogeny representation is a way to effectively represent the isogeny so that there is an efficient algorithm for evaluating the isogeny on given points. Common representations include rational maps, isogeny chains, and kernel representation. However, these methods are no longer compact or efficient when the degree d of the isogeny is a large prime and the kernel points are defined over a large degree extension field of F p .

The Deuring correspondence allows us to efficiently represent such isogenies with their corresponding ideals in maximal quaternion orders, this is call the ideal representation. This, however, reveals the endomorphism rings for both the domain and codomain curve. To remedy the situation, Leroux in [Ler22a] introduced another representation called the suborder representation which is not strictly an isogeny representation but satisfies a weaker definition as introduced in [CII + 23] and requires to reveal the endomorphism ring of the domain curve.

Finally, Robert [Rob22] suggested to use the techniques used in SIDH attacks [CD23,MMP + 23,Rob23] to obtain a new isogeny representation, by embedding the desired isogeny between supersingular elliptic curves into an isogeny between abelian varieties of higher dimension. While not named as such in Robert's paper, we refer to it as high dimension representation in our paper. This new representation doesn't reveal the endomorphism rings and is much more efficient than suborder representation. It consists only of evaluation of the isogeny to be represented on points of smooth order, and in the right setting it can be pretty easy to compute. While used destructively at first, it has been recently used constructively for building various protocols [DLRW23, Ler23,BMP23,DMS23]. For a detailed account of of the "old" isogeny representations, like the kernel or ideal representation, see [Ler22b]. In what follows, we explain in more details the idea of high dimension representation in dimension 2. The main result behind this representation is Kani's Lemma [Kan97] that we present below as Lemma 4.

Lemma 4 (Kani). Let us consider a commutative diagram of isogenies between principally polarized abelian varieties of dimension g

A ′ φ ′ / / B ′ A ψ O O φ / / B ψ ′ O O
where φ and φ ′ are a-isogenies and ψ and ψ ′ are b-isogenies for integers a, b. The isogeny F : A × B ′ -→ B × A ′ given in matrix notation by

F := φ ψ ′ -ψ φ ′
is a d-isogeny between abelian varieties of dimension 2g with d = a + b, for the product polarisations.

If

ker φ ∩ ker ψ ′ = {0}, the kernel of F is ker(F ) = {( φ(x), ψ ′ (x)) | x ∈ B[d]}.
Similarly, if ker φ ∩ ker ψ = {0}, then

ker( F ) = {(φ(x), ψ(x)) | x ∈ A[d]}.
The commutative diagram in Lemma 4 is often called as an isogeny diamond. Following the notations introduced in [Ler23], we call a 2 dim-representation of an isogeny φ : A → B between two elliptic curves A, B any data from which the isogeny F obtained by applying Lemma 4 with g = 1 can be computed efficiently. The idea is that φ can be recovered from F by pre-composition with any embedding A → A×B ′ that acts as the identity on A, and post-composition with the canonical projection

B × A ′ → B.
To represent the orientation of our SCALLOP-HD group action in Section 4.1, we will use the 2 dim-representation of an endomorphism with a commutative diagram obtained from two commuting endomorphisms.

Remark 5. One could also embed the isogeny φ in isogenies between abelian varieties in dimension 4 or 8, as discussed for the SQISignHD protocol in [DLRW23]. The higher the dimension, the easier it is to generate the isogeny diamond, however, the complexity of computing isogenies between abelian varieties scales exponentially with the dimension. This is why it is generally better to use the smallest possible dimension. In SQISignHD, it is argued that dimension 2 isogenies do not provide a clear advantage over the original SQISign scheme [DFKL + 20] due to the complexity to set-up the isogeny diamond, which is the main reason why SQISignHD works with dimension 4 and dimension 8. In our case, thanks to the idea of using isogeny diamond built from commuting endomorphisms, we will be able to work dimension 2 to achieve better efficiency.

Group action in isogeny-based cryptography

Informally, a group action is a map of the form ⋆ : G × X → X, where G is a group and X is a set, such that for any g 1 , g 2 ∈ G and any x ∈ X, we have

g 1 ⋆ (g 2 ⋆ x) = (g 1 g 2 ) ⋆ X.
We revisit here the concepts of effective group action (EGA) and restricted effective group action (REGA) from [ADFMP20], which capture the essence of two types of group actions used in isogeny-based cryptography. To clarify the distinction between the two and align with subsequent discussions, we exclude details concerning the set X -specifically, membership testing, unique representation, and the existence of the origin in X. Definition 6. (EGA) A group action (G, X, ⋆) is effective if the following properties are satisfied:

1. The group G is finite and there exist efficient (PPT) algorithms for:

(a) Membership testing, i.e., to decide if a given bit string represents a valid group element in G. (b) Equality testing, i.e., to decide if two bit strings represent the same group element in G. (c) Sampling, i.e., to sample an element g from a distribution D G on G. (d) Operation, i.e., to compute gh for any g, h ∈ G. (e) Inversion, i.e., to compute g -1 for any g ∈ G.

2. There exists an efficient algorithm that given (some bit-string representation of ) any g ∈ G and any x ∈ X, outputs g ⋆ x.

Definition 7. (REGA) Let (G, X, ⋆) be a group action and let g = {g 1 , . . . , g n } be a (not necessarily minimal) generating set for G. The action is said to be g-restricted effective if the following properties are satisfied:

1. G is finite and n = poly(log |G|).

2. There exists an efficient algorithm that given any i ∈ [n] and any bit string representation of x ∈ X, outputs g i ⋆ x and g -1 i ⋆ x. Existing instantiation of this definition from isogenies are all based on the ideal class group action. Specifically, it's the action of Cl(O) on S O (p) for some imaginary quadratic O as defined in Section 2.2. This action can be made a REGA immediately by choosing a generating set g = {l 1 , . . . , l n }, where each l i is a prime ideal of small norm. To further convert this action into an EGA, challenges arise in sampling elements from a distribution D G on G, and computing the action g ⋆ x for g ∈ G sampled from D G and x ∈ X. In this paper, we restrict our interest to the uniform distribution U G .

In [BKV19], Beullens, Kleinjung, and Vercauteren laid out a general strategy to turn the class group action from a REGA to an EGA as follows:

1. Offline phase:

1.1 Class group computation -Compute a generator g of the class group Cl(O), which is possible because generically Cl(O) is cyclic. 1.2 Construct the lattice of relations L -This lattice is generated by the column vectors of the following matrix

         1 0 0 . . . 0 0 0 1 0 . . . 0 0 0 0 1 . . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 0 . . . 1 0 r 1 r 2 r 3 . . . r n #Cl(O)          , where r ′ i s are integers such that [l i ] = [g ri ]. 1.
i=n i=1 l ei i ) ⋆ (E, ι E ) for (E, ι E ) ∈ S O (p).
This strategy allowed Beullens, Kleinjung and Vercautern to extend the REGA behind the CSIDH key exchange [CLM + 18] to an EGA, leading to the construction of the signature scheme CSI-FiSh. They worked with the imaginary quadratic order Z[ √ -p] which has a discriminant of 154 digits. The primary challenge for them was computing the class group Cl(Z[ √ -p]), and the remaining steps were efficient, essentially due to the fact that they could use a relatively small n and consequently, a lattice with rather small dimension. However, their method can't be scaled for bigger prime p due to the infeasibility of the class group computations.

To address this, SCALLOP[DFFK + 23] proposed the use of a distinct class of quadratic orders of the form

O = Z[f √ -d],
where f is a large prime and d is a small positive integer. While this sidesteps the class group computation challenges as discussed in Section 2.2 and enhances scalability, it introduces representation complexities for the set elements -oriented curves (E, ι E ). In order to achieve an efficient representation, an generator of O of smooth norm should be found, constraining the choice of f and yielding a class group with a non-smooth size. Consequently, the second step of precomputation -computing the lattice of relation -remains subexponential in time due to the need to solve discrete logarithms in groups with subexponential order sizes. Moreover, SCALLOP demands more computations to perform the group action, rendering it much slower than CSI-FiSh.

The security of CSIDH, CSI-FiSh and SCALLOP relies on the hardness of the vectorization problem. Abstractly, for a transitive group action, this problem is defined as follows.

Problem 8. (Vectorization) Given x, y ∈ X, find g ∈ G such that y = g ⋆ x.

According to [Wes22,Proposition 3], the fastest known generic classically method to solve the vectorization problem associated to the group action has complexity l O (1)|D O | 1/4 where l denotes the length of the input. In the setting of SCALLOP, this is log

(p + |D O |) O(1) min(p 1/2 , f 1/2 ) [DFFK + 23, Section 4].
The main quantum approach to solve the vectorization problem is given by Kuperberg's abelian hidden-shift algorithm [Kup05] and descendants, where the hidden "shift" corresponds to the secret group element g given x and y = g ⋆ x.

Despite known to take sub-exponential time, determining the precise quantum cost for concrete group actions is hard. Since 2020, a series of papers [BLMP19,BS20,Pei20,CSCDJRH22] studied the quantum security of CSIDH, leading to the conclusion that CSIDH-512 and CSIDH-1024 could not achieve NIST security level 1. Instead, [BS20] recommended that the CSIDH prime p should be upgraded to at least 2260 or 5280 bits, according to what they named as aggressive and conservative modes, respectively. [CSCDJRH22] recommended to use a CSIDH prime of 4096 bits for the level 1 security and 6144 bits for level 2. These analyses, together with the desire of obtaining EGAs from isogeny, have spurred the urgency to scale. Since the ideas of the quantum algorithms essentially work for all CRS style group action, we will also model the security of SCALLOP using the analyses for CSIDH. Specifically, this means we match the size of the field characteristic p and the class group size #Cl(O) with that of CSIDH to estimate the quantum security level of SCALLOP. In this line of research, CSI-FiSh was only able to scale to achieve the security level of CSIDH-512, and SCALLOP managed to scale to achieve the security level of CSIDH-1024.

2 dim-representation of orientations and endomorphisms

In this section, we introduce a new representation called 2 dim-representation of orientations and endomorphisms. Since representing an endomorphism θ amounts to representing any θ + n ∈ Z[θ], representing orientations and endomorphisms are essentially the same thing in different languages. Therefore, even though the results in this section are mostly stated with respect to orientations, they apply to endomorphisms as well.

In Section 4.1, we introduce the definition of our 2 dim-representation for orientations and discuss how to recover the orientation from the 2 dim-representation, then in Section 4.2, we show that any orientation (endomorphism) admits a 2 dim-representation that can be computed in polynomial time. Finally, in Section 4.3, we conclude with a formula that computes the Cl(O)-action on the set S O (p) with set elements given by 2 dim-representations.

While our 2 dim-representation is introduced to represent orientations appearing in SCALLOP-HD, this technique can be applied in other algorithms in isogeny as well.

2 dim-representation

Let (E, ι E ) be an O-oriented supersingular elliptic curve. Motivated by the idea of 2 dim representation of isogenies, we introduce the following definition.

Definition 9. Let O be an imaginary quadratic order with discriminant D O and odd conductor f . Given an O-oriented supersingular elliptic curve

(E, ι E ), take any ω ∈ O such that O = Z[ω] and define ω E := ι E (ω). Let β ∈ O such that n(ω) + n(β) = 2 e and gcd(n(β), n(ω)) = 1. Let P, Q be a basis of E[2 e ]. Then the tuple (E, ω, β, P, Q, ω E (P ), ω E (Q)) is called a 2 dim-representation of (E, ι E ). Given a 2 dim-representation (E, ω, β, P, Q, ω E (P ), ω E (Q)) of (E, ι E ), let β E := ι E (β), we immediately have the following isogeny diamond. E E E E. ωE ωE β E β E
From here, we can define an isogeny F E : E 2 → E 2 by the matrix

F E := ωE βE -β E ω E .
And as discussed in Section 2.3, if ker ω E ∩ ker β E = {0}, then

ker

F E = {(ω E (R), β E (R)) | R ∈ E[2 e ]}.
Since β is a translated scalar multiplication of ω E , knowing the evaluation of ω E on E[2 e ] suffices to compute ker F E .

Computing a 2 dim-representation

Now, we explain how to compute a 2 dim-representation for an O-orientation when the discriminant D O is equal to 5 mod 8.

Proposition 10. Let O be an imaginary quadratic order of discriminant equal to 5 mod 8, then any (E, ι E ) ∈ S O (p) admits a 2 dim-representation as in Definition 9.

Proof. To prove this result, it suffices we can always find e ∈ N, ω, β

∈ O such that O = Z[ω], gcd(nω), n(β)) = 1 n(ω) + n(β) = 2 e .
Using the explicit representation of O given in Section 2.2, ω = x

+ D O + √ D O 2 and β = y + z D O + √ D O 2
for some integers x, y, z. Therefore, the last condition above translates to finding an integer solution of the following equation:

x 2 + D O x + D O (D O -1) 4 + y 2 + D O yz + D O (D O -1) 4 z 2 = 2 e . (1)
Rewriting Eq. ( 1) and multiply both sides by 4 gives rise to the following:

(2x + D O ) 2 + (2y + D O z) 2 = 2 e+2 + D O (z 2 + 1). (2)
This equation can be solved efficiently by taking a random z and trying to express 2 e+2 + D O (1 + z 2 ) as a sum of two-squares with Cornacchia's algorithm. When e is large enough, we will be able to try enough z that one will give a solution. No matter what value of z we choose, we see that 2 e+2 + D O (1 + z 2 ) is either equal to 1 mod 4 or 2 times a number that is equal to 1 mod 4. As all number that can be written as a sum of two squares satisfy this constraint, we see that there is no obstacle there. Moreover, when D O = 5 mod 8, we can see that the norm of ω

= x + D O + √ D O 2
is always odd. Thus, n(ω) and n(β) are coprime since they sum to a power of 2.

We now detail the resolution of Eq. ( 2) with the OrientDiamondDim2 algorithm. The name suggests this algorithm is for building an isogeny diamond for a 2 dim-representation of an orientation. Proposition 12 shows that such a diamond can be constructed in polynomial time. We also consider a constant C that is an implicit parameter of OrientDiamondDim2. 3:

for z ∈ [1, ⌊ 2 e+1 |D O | -1⌋] do 4: M := 2 e+2 + D O (z 2 + 1). 5:
if M is a prime such that M ≡ 1 mod 4 or M = 2M ′ where M ′ is a prime such that M ′ ≡ 1 mod 4 then 6:

Use Cornacchia's algorithm to find X, Y such that

X 2 + Y 2 = M . 7: Set x = (X -D O )/2 and y = (Y -zD O )/2. 8: break 9:
end if 10: end for 11: if x = 0 and y = 0 then 12:

Return ⊥. 13: end if 14:

ω := x + D O + √ D O 2 , β := y + z D O + √ D O 2 . 15: return ω, β.
The complexity statement on Algorithm 1 only holds assuming some plausible heuristic regarding the distribution of number of the form 2 e + D(1 + z 2 ) that we state below as Heuristic 11.

Heuristic 11. Let e, D O be as in Algorithm 1. If D O = 1 mod 4, and z are sampled as random integers then the integers 2 e+2 + D O (1 + z 2 ) behave like random odd integers of the same size that are either congruent to 1 mod 4 or equal to 2 times an integer that is equal to 1 modulo 4.

Proposition 12. Assuming Heuristic 11, and

D O = 5 mod 8, OrientDiamondDim2 is correct, runs in O (poly (C log(|D O |)))
, and there exists a constant C ′ such that the computation has succeeded with probability at least:

1 -(1 -C ′ / log(|D O |)) √ C log(D O ) .
Proof. The correctness of Algorithm 1 follows from the observation that the outputs ω, β will always satisfy that O = Z Remark 13. We choose to work with isogenies in dimension 2 of degree n = 2 e for efficiency of computing such isogenies in practice, and we later choose p such that 2 e -torsion is defined over F p 2 in the set up of SCALLOP-HD. However, in other use cases of our 2 dim-representation technique for representing orientations and endomorphisms, it might be interesting to have n to be a powersmooth integer. We believe the results above generalize easily to the powersmooth situation. Therefore, our 2 dim-representation can be applied to [MW23, Algorithm 1] to replace the isogeny computations in dimension 8 with computations in dimension 2, improving its efficiency.

Class group action evaluation

Let [a] ∈ Cl(O) where a is an integral O-ideal such that gcd(n(a), 2) = 1. We now explain how to calculate the group action introduced in Section 2.2 in the context of the 2 dim-representation.

Let (E, ω, β, P, Q, ω E (P ), ω E (Q)) be a 2 dim-representation of (E, ι E ), to calculate a 2 dim-representation for (E a , ι Ea ), we can keep the same ω and β. Since gcd(n(a), 2) = 1, {ϕ a (P ),

ϕ a (Q)} form a basis of E a [2 e ]. By definition, ι Ea (ϕ a (P, Q)) = 1 n(a) ϕ a • ω E • φa (ϕ a (P, Q)) = ϕ a (ω E (P, Q)).
Let {R, S} be a basis for E a [2 e ], such as the one computed by a deterministic algorithm that computes a basis. Given P, Q, ω E (P ), ω E (Q) ∈ E[2 e ], to compute ι Ea (ω)(R) and ι Ea (ω)(S), we first write R, S as linear combinations of ϕ a (P ) and ϕ a (Q), then compute ι Ea (ω)(R) and ι Ea (ω)(S) from ι Ea (ϕ a (P )) = ϕ a (ω(P )) and ι Ea (ϕ a (Q)) = ϕ a (ω(Q)).

SCALLOP-HD group action

In this section, we introduce SCALLOP-HD, an effective group action (EGA). SCALLOP-HD builds on SCALLOP by using choosing the same group action, i.e., Cl(O) acts on

S O (p) for O = Z[f √ -d].
However, SCALLOP-HD deviates from SCALLOP by representing the set elements different. Precisely, SCALLOP-HD uses the 2 dim-representation for (E, ι E ) ∈ S O (p). It turns out that this choice significantly simplifies the group action computation, and removes some of the constraints on parameter choices, which essentially is due to the fact that we no longer need to find a generator of O of smooth norm, removing the tradeoff between the smoothness of the generator norm and the group size #Cl(O). As has been mentioned before, SCALLOP-HD has better scalability and has the potential of being more efficient.

Outline of SCALLOP-HD

It's clear from Section 3 that to introduce an EGA using the class group action, one needs to 1. specify the group and the set, 2. convert the action into a REGA by choosing the set g as in Definition 7, 3. and derive an EGA following the stragety outlined in Section 3.

To define the group action, we start with choosing the field characteristic p and the quadratic order O, they determine the group Cl(O) and the set S O (p). When making these choices, there are two aspects one needs to take into consideration -first, from a security point of view, the vectorization problem of the action should be hard; second, from an efficiency point of view, p should be of a particular form so that the torsion points involved in subsequent calculations are defined over F p 2 , and additionally O should be an order for which #Cl(O) is as smooth as possible for an efficient generation of the lattice of relation L (Section 3). In SCALLOP-HD, each element (E, ι E ) will be given using the 2 dim-representation, and we also specify the relevant parameters ω, β as a part of the group action definition. We discuss the details in Section 5.2.

To perform the group action, it's essential to possess an element from the set S O (p). Acquiring this element, given our choice of of O, isn't straightforward. We introduce the SetUpCurveHD algorithm in Section 5.3 specifically for this purpose.

Once the group action is set up, we proceed in the conventional manner to convert it into a REGA. Let {ℓ 1 , . . . , ℓ n } be the first n odd primes that split in O for n = O(log f ), then we choose the set g to consist of the ideals {l 1 , . . . , l k } with l i being one of the prime ideal above ℓ i . To further convert the REGA to an EGA, the offline phase is discussed in Section 5.4 and the online phase is discussed in Section 5.5.

Set up the group action

In this section, we explicit various choice of parameters for setting up the group action.

Choice of the quadratic order. Let O 0 = Z[ √ -d] be an imaginary quadratic order of class number equal to 1 and discriminant equal to d = 5 mod 8, as in SCALLOP, we choose O to be of the form Z + f O 0 for a large prime f . The size of f will be determined by the target security level. For the efficient precomputation of the lattice of relations (elaborated further in Section 5.4), we

want to ensure that #Cl(O) = f --1 f 1 |O * 0 |/2 is as smooth as possible.
To find a good f , we generate powersmooth integers s that have the same size as f and are divisible by 4. This is achieved by multiplying together powers of random integers below a specified smoothness bound, and then multiplying the outcome by 4. Following this, one checks whether s + 1 or s -1 is prime. If either is, it becomes the value of f . Since prime numbers are ample, this step runs in polynomial time with a polynomial size smoothness bound.

Choosing the field characteristic p. To ensure that the set S O (p) is non-empty, we need to choose p that does not split in O and does not divide the conductor f according to Proposition 3. Moreover, the form of p is determined by the torsion subgroups needed. To efficiently represent the orientation, we require that 2 etorsion is defined over F p 2 . For efficient computation of the group action, we also require to have the 1≤i≤n ℓ i -torsion defined over F p 2 . These conditions on torsion points amounts to selecting a prime of the form:

p = c2 e n i=1 ℓ i ± 1,
where c is a small cofactor.

Representing the orientation. Recall that a 2 dim-representation of an orientation is given by the tuple (E, ω, β, P, Q, ω E (P ), ω E (Q)). Once we have fixed O from the previous discussion, we can determine the integer e and ω, β ∈ O for instance using the OrientDiamondDim2 algorithm.

In SCALLOP-HD group action, ω, β will be part of public parameters, therefore, they can be omitted from the orientation representation. Furthermore, we can use a deterministic algorithm that computes a basis of E[2 e ] for any curve E, this way we omit P, Q from the representation to make it even compacter. That being said, in the actual application of SCALLOP-HD group action, the orientation representation will be of the form (E, ω E (P ), ω E (Q)).

Set up a starting curve

The computation of one O-oriented curve is necessary to set-up the scheme. This starting curve can be used to generate every other oriented curve by applying the group action. Concretely, computing one 2 dim-representation for a O-oriented curve means the following: compute any f -isogeny starting from an O 0 -oriented curve E 0 and evaluate it on a basis of E 0 [2 e ].

For this, we propose to revisit SetUpCurve [DFFK + 23, Algorithm 1] as our setting remains very similar to SCALLOP. Since the conductor f is a big prime, we cannot hope to compute any isogeny of degree f directly. The trick behind SetUpCurve is to use an endomorphism of norm f S where S is a smooth integer and to express the f isogeny as the composition of this endomorphism and an isogeny of degree S. Such endomorphisms can be found with the FullRepresent-Integer [DFLLW23, Algorithm 1] as soon as f S ≈ p. Since our ultimate goal is to evaluate the orientation on the 2 e torsion, the best option would be to take S coprime to 2, and with our choice of prime characteristic, we would have S = i ℓ i . Unfortunately, since 2 e ≈ f 2 , we have f i ℓ i ≈ p/f . This means that we must include other factors in S to reach the desired size. The only remaining available torsion is the power of 2. Since 2 e/2 ≈ f , we should have f 2 e/2 i ℓ i ≈ p. This means that we will be able to find endomorphisms of norm ℓ h 1 f 2 e/2 i>1 ℓ i for some small exponent h. In that case, we can circumvent the fact that S is not coprime to 2 by using a trick presented in [DLRW23, section 5.4] to cut the computation of the 2-dimensional isogeny in two, which allows us to divide by two the torsion requirement. For the group action computation, we prefer to use the full 2 e -torsion because the computation is more direct, but for the set-up of the scheme it is not a problem to sacrifice a bit of efficiency. The idea we just outlined gives the algorithm SetUpCurveHD that we describe below.

We start with an element (E 0 , ι 0 ) ∈ S O0 (p). Let O 0 be a maximal quaternion order such that End(E 0 ) ∼ = O 0 , and we can fix an explicit isomorphism ρ 0 : O 0 → End(E 0 ), we write ω 0 for ι 0 ( √ -d). Then, the orientation ι 0 is derived from the inclusion O 0 ⊆ O 0 and the isomorphism ρ 0 .

Algorithm 2 SetUpCurveHD(p, f ) Input: p, f, e, ω, β as defined in Section 5.2 and O0, (E0, ι0) as defined above.

Output: A 2 dim-representation for (E, ιE) ∈ S O (p) where O = Z + f O0. 1: Set h such that ℓ h 1 > p/(f 2 e/2
i>1 ℓi) and compute γ ∈ O0 of norm f 2 e/2 ℓ h 1 i>1 ℓi with FullRepresentInteger. Repeat that, until O0⟨γ, f ⟩ do not commute with ω0. 2: Compute the isogeny ψ : E0 → E ′ of degree 2 e/2 i ℓi corresponding to the ideal O0⟨γ, 2 e/2 i ℓi⟩. 3: Compute P0, Q0 a basis of E0[2 e ] and compute R0, S0 = ι(P0, Q0). 4: Compute the points P0, Q0, R0, S0 = ρ0(γ)(P0, Q0, R0, S0). 5: Make the list (φi :

E ′ → Ei) 1≤i≤m of all isogenies of degree ℓ h-1 1 from E ′ . 6: for i ∈ [1, m]: do 7: Compute Pi, Qi, Ri, Si = ([(ℓ h 1 i>1 ℓi) -1 mod 2 e/2 ])φi • ψ(P0, Q0, R0, S0). 8: Compute Ri, Si = [f ](Ri, Si). 9:
Try to use Pi, Qi, Ri, Si to build two isogenies F1 :

E 2 i → C and F2 : E 2 i → C. 10:
If it works, check that F = F2 • F1 is a dimension 2 representation for endomorphisms ωE i , βE i . 11:

If yes, verify that tr(ωE i ), n(ωE i ) is the same as tr(ω), n(ω). If yes, break from the loop. 12: end for 13: Set E = Ei, and compute a deterministic basis P, Q of E[2 e ]. 14: Use F to compute R, S = ωE(P, Q). 15: return (E, (R, S)).

Proposition 14. SetUpCurveHD is correct and terminates in O(cpoly(log(p)).

Proof. To prove correctness, we need to verify that the output (E, (R, S)) is a correct 2 dim-representation of an element in S O (p). Let us assume that the verification made in the loop passed. We will start by proving correctness under that assumption, then we will justify why the verification always passes.

When the verification passes, it means that there exists ω E ∈ End(E) of same norm and trace as ω. Thus, Z[ω E ] ∼ = Z[ω] = O, and sending ω to ω E defines a O-orientation ι E on E (we explain later in the proof why this is an optimal embedding of O into End(E)). Moreover, R, S = ω

E (P, Q) for a deterministic basis {P, Q} of E[2 e ]. Therefore, (E, (R, S)) = (E, ω E (P, Q)) is a valid 2 dim- representation of (E, ι E ) ∈ S O (p).
Now, let us justify that there always is an i that passes the verification. The element γ ∈ O 0 provides us with a principal ideal O 0 γ, whose corresponding isogeny ρ 0 (φ γ ) is an endomorphism of E 0 . Moreover, we have that (up to composing with some isomorphisms if necessary)

φ γ = ψ ′ •φ•φ f where φ f : E 0 → E has degree f , φ : E → E ′ has degree ℓ h-1 1 and ψ ′ : E ′ → E 0 has degree 2 e/2 i ℓ i . By [DFFK + 23, Proposition 16], E is an O-orientable curve unless φ f corresponds to one of the 1 + d0 f horizontal f -isogenies of domain E 0 .
Let us assume for now that it is not. The endomorphism

ω E = ι E (ω) is equal to [x] + φ f • ρ 0 (i) • φf . By design, the ideal ⟨γ, 2 e/2
i ℓ i ⟩ corresponds to the isogeny ψ′ . Thus, we have that the isogeny ψ computed in Step 2, is the isogeny ψ′ . Then, if we take the index i 0 such that φ i0 = φ, we get that E i0 is the curve E that we are looking for. Then, it can be verified that

P i0 , Q i0 is equal to [2 e/2 ]φ f (P 0 , Q 0 ), so it is a basis of E i0 [2 e/2 ]. It can also be verified that the equal- ity R i0 , S i0 = φ f • ω 0 • φf (P i0 , Q i0 ).
From there, the image points ω E (P i0 , Q i0 ) and β E (P i0 , Q i0 ) can be recovered, and this is enough to build the two isogenies F2 and F 1 as described in [DLRW23, Section 5.4]. Then, F is the correct endomorphism on E 2 constructed from isogeny diamond formed by ω E and β E , and so the check for norm and trace equality will pass.

To finish the proof of correctness, we simply need to prove that the case where φ f might be one of the bad isogenies cannot happen. In that case, we have that φ f is one of the horizontal isogenies and since O 0 has class number one, this means that φ f commutes with ω 0 which is equivalent to the fact that ideal corresponding to φ f commutes with i. Since this ideal is exactly equal to O 0 ⟨γ, f ⟩, this situation is prevented from happening.

Regarding complexity, we have ℓ h-1 1 < p/(f 2 e/2 i ℓ i ) and since we have f = O(2 e/2 ), the loop is repeated at most O(c) times. The computations over the quaternions are in O(poly(log(p)). Then, since we have the explicit isomorphism ρ 0 , we can compute ψ and evaluate ρ 0 (γ) over the 2 e -torsion in O(poly(log(p)) (remember that the 2 e -torsion is defined over F p 2 and 2 e < p). Then, the computation of each φ i is in O(poly(log(p)) and computing s i and checking the trace has O(poly(log(p)) complexity with the CheckTrace algorithm introduced in [Ler22a]. Computing the norm can be done very similarly with the same complexity. This proves the result. ⊓ ⊔

Offline phase

The remaining operations required to be done in the precomputation are exactly the same as in SCALLOP. First, we need to generate the relation lattice associated to the ideal basis (l i ) 1≤i≤n . Second, we need to find a reduced basis of this lattice. These operations can be done exactly as explained in [DFFK + 23].

The lattice of relations is generated by solving some discrete logarithms in the class group. Then, the reduced basis is found using standard lattice reduction techniques.

The only real difference between SCALLOP and our new construction is the complexity of those operations. In particular, with our choice of quadratic order, the generation of the lattice of relations takes polynomial time. Indeed, the choice of f ensures that the class group has order f --1 f 1 |O * 0 |/2 with a polynomial smoothness bound. This means that the Pohlig-Hellman method succeeds in solving discrete logarithm in polynomial time and so the full lattice of relations can be generated in polynomial time (whereas it has sub-exponential complexity in general). Unfortunately, the complexity of the basis reductions remains subexponential, which means that the overall complexity of the precomputation is still subexponential. However, as explained in [DFFK + 23], the dimension of the relation lattice is quite small in practice and so a nearly-optimal basis can be found efficiently.

Online phase

We now describe precisely an algorithm GroupAction to perform the group action for SCALLOP-HD given an ideal a = 1≤i≤n l ei i where l i is an ideal of norm ℓ i . In GroupAction below, we restrict to the case a = i l i to simplify the exposition as the generic algorithm simply consists in several executions of the sub-algorithm for i l i . Proof. Let us start by proving correctness. We discuss the details for the first two "if" cases, and for the last "if" case, we simply replace ω by ω in the following discussion. Since ω, β ∈ O we have that the endomorphisms ω E , ι E (β) commutes and since we have 2 e = n(ω) + n(β), by Lemma 4, the 2 e -isogeny F E : E 2 → E 2 is correctly computed from its kernel. Then, we have that F (0, R) = (⋆, ω E (R)) for any point R. Thus, we do have

U i = ω E (P i ), V i = ω E (Q i ) for each 1 ≤ i ≤ n. The kernel of ω E -λ i is equal to (ω E -λ i )(E[ℓ i ]) and since ωE = [2tr(ω)]-ω E , the point R i computed is a generator of ker(ω E -λ i ) = ker φ li = ker φ a ∩E[ℓ i ].
Thus, the computation of φ a is correct, and the computation of the 2 dim-representation of a⋆(E, ι E ) is correct by the formulas given in Section 4.3. The last step is merely changing the evaluation to the deterministic basis using linear algebra.

For the complexity, the 2 e -isogeny F E can be computed evaluated in O (poly (log(p)e)) = O (poly (log(p) log(f ))). Then, since the points of E[ℓ i ] are defined over F p 2 , the cost to compute the bases P i , Q i and to compute U i , V i through evaluation of F is O (poly (log(p) log(f )n)).

Finally, using the Velusqrt formulas introduced in [BDFLS20], it is possible to compute the isogeny φ a of norm 1≤i≤n ℓ i in Õ poly (log(p)n) max 1≤i≤n ℓ i . This proves the result.

⊓ ⊔

6 Some remarks on security

The security of SCALLOP-HD is identical to that of SCALLOP because the group action has the same exact structure. In this section, we take the opportunity to discuss the impact of recent developments from the papers [CII + 23,CV23] on the security of SCALLOP and SCALLOP-HD.

In [DFFK + 23], one proposed method to attack SCALLOP is to compute the ideal corresponding to the isogeny φ f of degree f connecting the O 0 -oriented curve E 0 with the O-oriented curve E. In [CII + 23], a polynomial-time quantum algorithm is introduced to perform that computation when there is an efficient way to evaluate this f -isogeny on points of powersmooth order. Since the endomorphism ω E can be written as d + φ f • ω 0 • φf for some integer d and ω 0 ∈ End(E 0 ), the security of SCALLOP then reduces to the following question:

Can we use the effective orientation ω E revealed in SCALLOP(-HD) to evaluate φ f ?

As far as we know, the answer to this question is no (at least not in polynomial time). In fact, the problem of evaluating the descending isogeny φ f was already discussed in [DFFK + 23, Section 7] even though the algorithm from [CII + 23] didn't exist at the time. The discussion presented in [DFFK + 23, Section 7] is still relevant and justifies why evaluating φ f from ω E appears hard. One possible way to reduce the search space introduced in [DFFK + 23, Section 7] would be to use non-trivial self-pairings (i.e. pairing such that e(P, P ) is not 1). However, there are no known self-pairings in the context of SCALLOP(-HD) and some negative results regarding the existence of these objects were even recently shown in [CHM + 23].

Recently, [CV23] introduced a generalization of the "lollipop method" to recover an isogeny from a partial torsion information. More concretely, it targets the following setting. Let φ : E 0 → E be an isogeny of degree f and P, Q be a basis of E 0 [N ] for some big enough integer N . The goal is to recover φ from the knowledge of T, S where T, S is a basis of E[N ] equal to X • φ(P, Q) for some secret matrix X contained in some subset of GL 2 (Z/N Z). Typically, [CV23] targets the case where X is diagonal, but they introduce a generic framework that can handle a broader variety of families of Xs. The fact that X is unknown is the main obstacle to apply the usual isogeny recovery attacks or the attack from [CII + 23]. The paper [CV23] shows how to overcome this obstacle when the parameters d, N, p allow the existence (and efficient computation) of an endomorphism ρ ∈ End(E 0 ) satisfying various constraints.

Below, we try to apply this attack to recover the isogeny φ f using the knowledge of the orientation. In particular, we will have a look at the case where X is diagonal. Indeed, when taking N as a product of split primes in O 0 , P, Q to be two generators of the eigenspaces of ω 0 in E 0 [N ] and T, S generators of the eigenspaces of ω E ∈ E[N ], we are exactly in the desired setting where the unknown matrix is diagonal (since eigenspaces of ω 0 are mapped to eigenspaces of ω E by φ f ).

When N is powersmooth, the points P, Q, T, S can be computed in polynomial time by evaluating ω 0 and ω E , and solving some discrete logarithms. The method introduced in [CD23] works by computing a non-trivial endomorphism ρ = κ • σ such that [φ f ] * σ can be computed efficiently, the matrix of the action of ρ in the basis P, Q commutes with the matrix X and deg κ ≤ N 2 /f 2 . When those conditions are satisfied, it can be shown that the image of the isogeny ψ = [σ] * φ f • κ • φf on T, S can be computed exactly, allowing for its efficient computation with higher dimensional isogenies. In a number of cases, this is enough to recover φ f directly, but not always. In the setting of SCALLOP-HD, this is not necessarily new information if the endomorphism ψ • [φ f ] * σ belongs to ι E (O). On the other hand, when it does not, then we obtain a full quaternion suborder of End(E) in that matter, and that might be enough to evaluate φ f with an adaptation of [Ler22a, Algorithm 5] and then, we can apply the attack from [CII + 23].

Thus, the question becomes: can we find such an endomorphism ρ satisfying all the previous constraints? While we do not know how to prove formally that the answer is always no, we provide examples where we can prove that finding a suitable ρ is impossible.

As far as we know, there are essentially three types of isogenies σ for which we have an efficient way to compute the push-forward [φ f ] * σ:

1. The identity. 2. The Frobenius.

Horizontal isogenies (used in the group action).

Let us consider the case where σ is the identity. We want to find ρ ∈ End(E 0 ) that acts as a diagonal matrix on the subgroups generated by P and Q. As we explained before, we have an attack if we can find ρ ̸ ∈ Z[ω 0 ] (otherwise we don't learn anything new).

Let O 0 be a quaternion maximal order isomorphic to End(E 0 ) and I, J, the two left O 0 -ideals of norm N corresponding to the subgroups generated by P and Q under the Deuring correspondence. Then, ρ will act as a diagonal matrix on the two subgroups if and only if it is contained inside the quaternion order O = (Z + I) ∩ (Z + J) which is an Eichler order of level N 2 . This is a lattice of volume equal to Cp 2 N 4 for some small constant C. And this means the four successive minimas λ 1 , λ 2 , λ 3 , λ 4 satisfy

p 2 N 4 ≤ λ 1 λ 2 λ 3 λ 4 ≤ 16Cp 2 N 4 (3)
However, since Z[ω 0 ] is contained inside O by design, and O 0 is a quadratic order of very small discriminant, we know that the two first successive minimas are 1 and n(ω 0 ) (assuming that ω 0 is the element of smallest norm in Z[ω 0 ] ∖ Z, which we can do without any loss of generality). Moreover, since ω 0 ∈ O, we can always multiply any element by ω 0 , this means that we must have λ 4 ≤ n(ω 0 )λ 3 , and so we can deduce that λ 3 ≥ pN 2 . This means that the smallest element ρ we can expect to find in O ∖ Z[i] has norm greater than pN 2 . But, to make the attack work, we need that N 2 > f 2 deg ρ. These two conditions are clearly not compatible, and this means that there is no hope to find a suitable ρ to make the attack work in this setting.

Let us now consider the case where σ is the Frobenius isogeny. When O 0 contains j (which we can assume since the class number of O 0 is 1 and it has been shown in [CPV20] that the only O 0 -oriented is F p -rational when p is big enough), finding ρ when σ is the Frobenius implies that ρ is contained inside O ∩ O 0 j. It can be verified that the successive minimum of this lattice are small linear combinations of p, pω 0 , N j, N ω 0 j and thus the solutions outside of Z[i] have norm bigger than N 2 . Thus, it is once again not possible to find ρ with N 2 > f 2 deg ρ. A similar reasoning can be applied to prove that a suitable endomorphism ρ cannot be found when σ is an O 0 -horizontal isogeny.

Thus, we have proven that the lollipop method cannot be applied to the setting of SCALLOP-HD when considering the torsion information revealed by the orientation on the points whose order is a product of split primes.

The same reasoning cannot be applied if we consider inert primes. Indeed, in that case, the matrix will probably not be diagonal. However, this also means that we don't really know what kind of matrix is required for the endomorphism ρ. Thus, it seems hard to use the lollipop method in that case.

Conclusion and future work

SCALLOP-HD represents the progression of a series of efforts to enhance the scalability of EGAs based on isogenies. Beginning with CSI-FiSh, which established the foundational strategy and gave a notable example, there was a significant challenge in computing larger class groups. SCALLOP then built upon the work of CSI-FiSh by overcoming this limitation, but needed subexponential time for generating the lattice of relation. SCALLOP-HD takes this advancement a step further, making precomputation polynomial time except for the lattice reduction algorithms. While these algorithms are theoretically subexponential in complexity, the dimensions are in fact manageable in practice.

SCALLOP-HD is heavily based on the SCALLOP group action [DFFK + 23]. The main difference stems from the way the orientation is computed. In SCAL-LOP, an effective orientation is obtained from an endomorphism of smooth degree, whereas in SCALLOP-HD, an effective orientation is obtained from a 2 dim-representation of an arbitrary degree endomorphism. The relaxation of the constraint on the degree of the endomorphism is the main advantage of SCALLOP-HD as it improves scalability and simplifies the group action computation at the cost of requiring the computation of a 2 e -isogeny between abelian variety of dimension 2.

The 2 dim-representation technique we developed in order to represent set elements in SCALLOP-HD is interesting in its own right. It has already seen applications in [Ler23] and Remark 13, bringing down the dimension needed to compute the isogenies between abelian varieties from 4 or 8 to 2.

The main remaining problem is to make an efficient implementation of SCALLOP-HD. This is a non-trivial task due to the need of isogeny computation in higher di-mension. Several algorithms and implementations already exists [CDS20,Kun22], [MMP + 23,BMP23,DLRW23,CDPMR23], but there are some on-going efforts to improve significantly the efficiency of these computations, and we intend to provide a full implementation of SCALLOP-HD once the state of the art on this topic is somewhat stable. In the end, we believe that the efficiency of SCALLOP-HD's group action computation could outperform SCALLOP's due to its simplicity.

For

  any order O, the class group Cl(O) consists of the invertible fractional ideals of O up to principal factors and is of order D o(1) O . When O = O K is the maximal order, computing Cl(O K ) takes time L D K (1/2) classically [HM89] and polynomial time quantumly [BS16]. When O = Z + f O K where f is a prime and Cl(O K ) = {1}, there is a simple characterization of Cl(O) as discussed in [FFK + 23, Appx. A]. Specifically, Cl(O) satisfies the following short exact sequence 1 → O

Algorithm 1

 1 OrientDiamondDim2(D O ) Input: An imaginary quadratic order O with discriminant D O = 5 mod 8. Output: ω, β ∈ O such that O = Z[ω], n(ω) + n(β) is a 2-power and gcd(n(β), n(ω) = 1. 1: Let e be the smallest integer such that 2 e+2 > C(log |D O |)|D O |. 2: Set x := 0, y := 0.

  [ω], gcd(n(ω), n(β)) and n(ω) + n(β) = 2 e . The complexity follows from the fact that we perform O( C log(|D O )| iteration of the loop and that the operations required inside each iteration are logarithmic in |D O |. The integers M have size C(log |D O |)|D O | and we assume that they behave like random integers under Heuristic 11, therefore there is a constant C ′ such that either M/2 or M is prime with probability higher than C ′ /(log |D O |). The bound on the success probability follows directly from there. ⊓ ⊔

Proposition 15 .

 15 Algorithm 3 GroupAction is correct and runs in Õ poly (log(p) log(f )n) max 1≤i≤n ℓ i .

Table 1 .

 1 Table 1, borrowed from [DFKL + 20]. The Deuring correspondence, a summary [DFKL + 20].

	Supersingular j-invariants over F p 2 j(E) (up to Galois conjugacy)	Maximal orders in Bp,∞ O ∼ = End(E) (up to isomorphism)
	(E1, φ) with φ : E → E1	Iφ integral left O-ideal and right O1-ideal
	θ ∈ End(E0)	Principal ideal Oθ
	deg(φ)	n(Iφ)

3

  Lattice reduction -Compute a reduced basis of L suitable for solving approximate-CVP. 2. Online phase:2.1 Solve approximate-CVP -Given g e ∈ Cl(O), solve approximate-CVP to find a decomposition g e = Group action evaluation -Compute the action (

	i=n i=1 l ei i with small exponents.
	2.2

https://yx7.cc/blah/2023-04-14.html

Acknowledgements

The first author would like to thank Christophe Petit for helpful feedback.