Mingjie Chen

Muhammad Imran

Gábor Ivanyos

Péter Kutas

Antonin Leroux

Christophe Petit

Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic p given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime. In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have O(log log p) many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer N with O(log log p) many prime factors to powersmooth elements. As a main consequence for cryptography, we obtain a quantum polynomialtime key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

Introduction

The problem of computing an isogeny between two supersingular elliptic curves is believed to be hard, even for a quantum computer. The assumption that this statement is true led to the idea of using isogenies to build post-quantum cryptography.

However, building actual cryptography from this principle is not easy and the security of concrete isogeny-based protocols is based on weaker versions of the isogeny problem, where the attacker is given more information. The nature of this additional information differs from one proposal to another but the heart of the problem remains the same.

At the core of the cryptanalytic efforts to attack the isogeny problems lies another problem: the endomorphism ring problem, which requires to compute the endomorphism ring of a curve given in input. In fact, computing isogenies and computing endomorphism rings are computationally equivalent problem for supersingular curves [EHL + 18, Wes21]. However, this equivalence result does not fully answer the following question : given a "reasonable" representation of an isogeny ϕ : E → E ′ and the knowledge of the endomorphism ring of the starting curve E, can we always efficiently compute the endomorphism ring of the codomain E ′ ? This question leads to the following problem, where the exact definition of weak isogeny representation will be given in Section 2.4.

Problem 1.1 (Isogeny to Endomorphism Ring Problem (IsERP)). Let E be a supersingular elliptic curve over F p 2 and let ϕ : E → E 1 be an isogeny of degree N for some integer N . Given End(E) and a weak isogeny representation for ϕ, compute End(E 1 ).

The answer to this question is known to be yes when the degree of ϕ is powersmooth (and this is what is used in the equivalence results mentioned above), but the question remains open for an arbitrary degree. For a prime degree, this problem can be seen as the generalization of the key recovery problem for the pSIDH scheme recently introduced by Leroux [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF]. The best known algorithm has subexponential quantum complexity in N , and the generic endomorphism ring attack has complexity exponential in log p.

Isogeny-based cryptography. Isogeny-based cryptography originates in Couveignes' seminal work [START_REF] Couveignes | Hard homogeneous spaces[END_REF] where he proposed to use the natural class group action on ordinary elliptic curves to instantiate a potentially quantum-resistant version of the Diffie-Hellman key exchange. The reasoning for that is that the discrete logarithm problem has more structure than needed to instantiate a key exchange, and this structure is exploited in Shor's algorithm [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]. Couveignes' ideas were rediscovered by Rostovtsev and Stolbunov [START_REF] Rostovtsev | Public-key cryptosystem based on isogenies[END_REF] and thus the resulting scheme is referred to as the CRS key exchange. These ideas were far from practical and a major breakthrough came with the invention of CSIDH [CLM + 18]. The idea is quite similar but one uses supersingular elliptic curves defined over F p and the acting group is the class group of Z[ √ -p]. In other words one considers supersingular curves defined over F p together with isogenies defined over F p as well.

The same idea does not apply to supersingular curves defined over F p 2 because the endomorphism rings are non-commutative (hence the natural class group action of left ideals modulo principal left ideals is a non-commutative group action). This means that providing codomains of secret isogenies (i.e., curves E A , E B ) is not enough to arrive at a shared secret that both parties can compute. Thus in order to instantiate a Diffie-Hellman-like key exchange on the full set of supersingular curves parties must provide additional information. In 2011 De Feo and Jao proposed SIDH [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF] where both parties share the images of other person's torsion basis under their secret isogeny. This motivated the following problem: Problem 1.2. Let E be a supersingular elliptic curve and let A, B be coprime smooth numbers. Let ϕ : E → E A be a secret isogeny of degree A. One is provided with the action of ϕ on E[B]. Compute ϕ.

In [START_REF] Petit | Faster algorithms for isogeny problems using torsion point images[END_REF] it was shown that this problem can be solved in polynomial time for certain parameter sets (where B > p 2 A 2 ). In order to instantiate SIDH efficiently one usually uses parameters A, B, p such that AB divides p + 1 as then all computations can be carried out over F p 2 so in some sense these initial results seemed theoretical. Then the initial idea of Petit [START_REF] Petit | Faster algorithms for isogeny problems using torsion point images[END_REF] was improved in [QKL + 21] to B > √ pA 2 which already included parameter sets which could have been used in SIDH variants. Nevertheless none of these attacks directly impacted SIDH where A and B are roughly the same size. Then in 2022 Castryck and Decru [START_REF] Castryck | An efficient key recovery attack on sidh (preliminary version)[END_REF] (and independently Maino and Martindale [START_REF] Maino | An attack on sidh with arbitrary starting curve[END_REF]) vastly improved these using ingenious techniques (utilizing superspecial abelian surfaces) which break SIDH with known endomorphism ring in polynomial time even if A and B are balanced. Finally, Robert proposed a polynomial-time attack on SIDH with unknown endomorphism ring (furthermore, he only needs B 2 > A as opposed to B > A in other attacks). These attacks have shown that using smooth degree isogenies and providing torsion point information will potentially not lead to secure and efficient cryptographic constructions (in [START_REF] Tako | Msidh and md-sidh: countering sidh attacks by masking information[END_REF] some countermeasures are proposed, but the ones that are not broken are much less efficient than the original SIDH construction). Thus, in order to navigate in the supersingular isogeny graph parties have to share some other kind of extra information.

Alternative isogeny representations. In the pSIDH protocol introduced by Leroux [Ler22a], one reveals suborder representations for isogenies of large prime degrees to build a key exchange. Suborder representations are a particular kind of weak isogeny representations, i.e. some data to represent isogenies together with an algorithm to efficiently evaluate these isogenies on any point up to a scalar. Prime degree isogenies were not really used before as one cannot write down the isogeny itself (but one can compute its codomain with non-trivial techniques). More recently, a similar type of secret isogeny was used in the SCALLOP scheme [DFFK + 23]. In SCALLOP, a partial isogeny representation is revealed to the attacker.

From a cryptanalytic point of view, the unlimited amount of torsion information provided by the isogeny representation revealed in pSIDH (and more generally, any isogeny representation) is very interesting. However, when the kernel points are not defined over a small extension, the known algorithms do not apply and it is still unclear how to exploit the isogeny representation to recover the secret isogeny.

Leroux studied the case where a specific isogeny representation (the suborder representation) is revealed, but we can generalize this setting to any isogeny representation. He showed that computing the endomorphism ring of the codomain would make pSIDH insecure, therefore motivating Problem 1.1 in the prime case.

More recently, Robert introduced yet another isogeny representation based on torsion point images and the recent SIDH attacks [START_REF] Robert | Evaluating isogenies in polylogarithmic time[END_REF]. This representation could be used (for isogenies with large prime degrees) instead of the suborder representation to derive a key exchange protocol similar to pSIDH, and this protocol would be similarly affected by our new results.

A group action for SIDH and pSIDH In [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF] the authors introduce a group action on a particular set of supersingular elliptic curves. Let E be a supersingular elliptic curve with endomorphism ring isomorphic to O. Then (O/N O) * acts naturally on the set of cyclic subgroups of E of order N . If there is a one-to-one correspondence between cyclic subgroups and N -isogenous curves, then one can look at this action as acting on a set of curves. This action was used to provide a subexponential quantum key recovery attack on overstretched SIDH parameters.

The reason the attack only works for overstretched parameter sets is that in general this group action is not easy to evaluate (thus substantial amount of extra information on the secret isogeny is needed). This motivates the following problem where the name Malleability Oracle Problem comes from the term introduced in [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF].

Problem 1.3 (Malleability Oracle Problem). Let E be a supersingular elliptic curve and let ϕ : E → E ′ be a secret isogeny with kernel generated by A. Let σ ∈ End(E). Find the j-invariant of E/⟨σ(A)⟩.

Contributions. Our main result is the following theorem on the resolution of IsERP.

Theorem 1.4. Let N = ℓ ei i ̸ = p be an odd integer that is of size polynomial in p and has O(log(log p)) divisors. Then there exists a quantum polynomial-time algorithm that solves the IsERP.

We first provide a reduction from the IsERP to the Powersmooth Quaternion Lifting Problem (PQLP). The PQLP is the problem of finding a powersmooth representative for a given class in O/N O for some integer N and maximal order O in the quaternion algebra B p,∞ .

Our reduction from the IsERP to PQLP is obtained through a quantum equivalence between the IsERP and a problem similar to Problem 1.3, which we call the Group Action Evaluation Problem. The most difficult direction of this equivalence (reducing the IsERP to the Group Action Evaluation Problem) is obtained with a quantum polynomial-time algorithm. The other reduction is classical and uses standard tools for the Deuring correspondence.

The quantum polynomial reduction relies on a special case of the well-known hidden subgroup problem (HSP), namely when the acting group is GL 2 (Z/N Z) and the hidden subgroup is a conjugate of the subgroup of upper triangular matrices. This problem was previously studied only for prime N [START_REF] Denney | Finding conjugate stabilizer subgroups in PSL and related groups[END_REF] and in this paper we provide a polynomial-time quantum algorithm for any N . Furthermore, whenever N is smooth we propose a classical polynomial-time algorithm which might be of independent interest.

We then propose a classical polynomial-time algorithm for the PQLP. The algorithm relies on several tools developed in KLPT [START_REF] Kohel | On the quaternion ℓ-isogeny path problem[END_REF]. Namely we decompose elements σ ∈ O as α 1 γα 2 γα 3 where the α i lie in a special subset of O (linear combinations of j, ij) that can be lifted efficiently to powersmooth elements, and γ is a fixed element of O of powersmooth norm. Finding γ and lifting the α i are accomplished with slightly modified subroutines of KLPT, whereas the decomposition itself is inspired by similar decompositions in other contexts [START_REF] Petit | Full cryptanalysis of lps and morgenstern hash functions[END_REF]. The lifting algorithm requires that N is odd and has O(log log p) prime factors. We look at approaches to generalize this algorithm to arbitrary N (thus solve Is-ERP for arbitrary degrees) in [CII + 23, Appendix D]. We have also implemented this algorithm for prime N in Sagemath [START_REF]The Sage Developers[END_REF], available on GitHub [git23].

The rest of the paper is organized as follows: in Section 2, we introduce some necessary background. Then, in Section 3, we introduce a quantum algorithm to solve the Borel Hidden Subgroup Problem. In Section 4 we define the Group Action Evaluation Problem and the Powersmooth Quaternion Lift Problem (PQLP). We show various reductions between the two problems and the IsERP, most importantly reducing IsERP to the PQLP. In Section 5 we describe our polynomial-time algorithm for PQLP, which leads to a resolution of the IsERP through the reductions. Finally in Section 6, we discuss the impacts of our results on isogeny-based cryptography.

Preliminaries

Below, we give a brief introduction to some necessary mathematical background. More details on elliptic curves and isogenies can be found in [START_REF] Joseph H Silverman | The arithmetic of elliptic curves[END_REF]. The book of John Voight [START_REF] Voight | Quaternion algebras[END_REF] is a good reference regarding quaternion algebras and the Deuring correspondence. In the remaining of this paper, we fix a prime p > 2.

Supersingular elliptic curves and isogenies

Let E 1 , E 2 be elliptic curves defined over a finite field F q . An isogeny is a nonconstant rational map from E 1 to E 2 that is simultaneously a group homomorphism. Equivalently, it is a non-constant rational map that sends the point of infinity of E 1 to the point of infinity of E 2 . An isogeny induces a field extension K(E 1 )/K(E 2 ) of function fields. An isogeny is called separable, inseparable or purely inseparable if the extension of function field is of the respective type.

The degree of the isogeny is the degree of the field extension K(E 1 )/K(E 2 ). The kernel of an isogeny ϕ : E 1 → E 2 is a finite subgroup of E 1 . If the isogeny is separable, then the size of the kernel is equal to the degree of the isogeny (more generally, the size of the kernel equals the separable degree of the field extension K(E 1 )/K(E 2 )). For every isogeny ϕ : E 1 → E 2 there exists a dual isogeny φ :

E 2 → E 1 such that deg(ϕ) = deg( φ) = d and ϕ • φ = [d] E2 (and φ • ϕ = [d] E1
). Isogenies (together with the zero map) from E to itself are called endomorphisms. Endomorphisms of an elliptic curve form a ring under addition and composition. An elliptic curve over a finite field is called ordinary if its endomorphism ring is commutative, and supersingular otherwise.

Quaternion algebras

The endomorphism rings of supersingular elliptic curves over F p 2 are isomorphic to maximal orders of B p,∞ , the quaternion algebra ramified at p and ∞. We fix a basis 1, i, j, k of B p,∞ , satisfying i 2 = -q, j 2 = -p and k = ij = -ji for some integer q. The canonical involution of conjugation sends an element α = a + ib + jc + kd to α = a -(ib + jc + kd). A fractional ideal I in B p,∞ is a Z-lattice of rank four. 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. The left order of a fractional ideal is defined as O L (I) = {α ∈ B p,∞ | αI ⊂ I} and similarly for the right order O R (I). Then I is said to be a right O R (I)-ideal or a left O L (I)-ideal. A fractional ideal is integral if it is contained in its left order, or equivalently in its right order; we refer to integral ideals hereafter as ideals. Eichler orders are the intersection of two maximal orders. If I is an ideal, we can define the Eichler order associated to I as O L (I) ∩ O R (I). In that case, it can be shown that O L (I) ∩ O R (I) = Z + I (see [DFKL + 20]).

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 [START_REF] Russell | Endomorphism rings of elliptic curves over finite fields[END_REF] 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 [START_REF] William C Waterhouse | Abelian varieties over finite fields[END_REF], and in the separable case, it is explicitly given as follows.

Definition 2.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

Isogeny representation

In this subsection, we look at isogenies through a more algorithmic prism. Specifically, we consider the following question: what does it mean to "compute" an isogeny? A natural answer is a rational map representation of the isogeny. Other representations are however possible, and in [PL17, Sec 2.4] and [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF] it is argued that any such representation should allow efficient evaluation at arbitrary points (for a more complete study, look at [Ler22b, chapter 4]). More formally, Leroux defines an isogeny representation as some data s ϕ associated to an isogeny ϕ : E → E ′ of degree N such that there are two algorithms: one to "verify" and one to "evaluate" ϕ.

The motivation to have a verification algorithm is found in a cryptographic context where an adversary might try to cheat by revealing something that is not a valid isogeny representation. But, in the more cryptanalatic point of view of this paper, we can assume that we work with a valid isogeny representation. This is why we take a relaxed definition of isogeny representation where we only require an evaluation algorithm (a verification algorithm can probably be derived from the evaluation algorithm anyway). Moreover, we assume that the representation is "efficient" meaning that is has polynomial size and the evaluation algorithm is polynomial-time in the log of the degree and the prime. We give a detailed version below. In our context, it is sufficient that the evaluation algorithm gives evaluation of points up to a (common) scalar which is why we qualify our isogeny representation as weak.

Definition 2.2. A weak isogeny representation for the isogeny ϕ : E → E ′ of degree N , is a data s ϕ of size O(polylog(p + N )) (associated to a unique isogeny ϕ), such that there exists an algorithm E that takes s ϕ and a point P of the curve E of order d in input and computes λ(d)ϕ(P ) in O(polylog(d + N + |P |)) for any point P of E, where |P | is the bitsize of the representation of P .

The notion of isogeny representation is particularly relevant when the degree N is a big prime and the kernel points are defined over an F p -extension of big degree (this is exactly the setting of pSIDH [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF]). Indeed, in that case, the standard ways to represent isogenies (with polynomials, or kernel points) are not compact or efficient enough to match our definition.

The Deuring correspondence gave us the tools to obtain efficient representations with a natural isogeny representation obtained by taking s ϕ as the ideal I ϕ corresponding to ϕ. This ideal representation matches Definition 2.2, however it also reveals the endomorphism ring of E ′ . One of the motivations of Leroux in [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF] to introduce another isogeny representation (called the suborder representation) is to have an isogeny representation that does not directly reveal the endomorphism ring of the codomain. This suborder representation matches our notion of weak isogeny representation as defined in Definition 2.2. The main contribution of this paper implies that the suborder representation does not hide the endomorphism ring of the codomain to a quantum computer, even when the degree is prime.

Since then, Robert [START_REF] Robert | Evaluating isogenies in polylogarithmic time[END_REF] suggested to use the techniques introduced to attack SIDH in order to obtain another isogeny representation (this one not even requiring to reveal the endomorphism ring of the domain). Our analysis holds for any suborder representation, hence it also applies to Robert's one.

The pSIDH key exchange

As an application of the hardness of computing the endomorphism ring from the suborder representation, Leroux introduced a key exchange called pSIDH. The principle can be summarized as follows: use the evaluation algorithm for the suborder representation to perform an SIDH-like key exchange, but for isogenies of big prime degree. The SIDH and pSIDH key exchange both use the following commutative isogeny diagram:

E B ψ A / / E AB E 0 ϕ B O O ϕ A / / E A ψ B O O
In pSIDH, Alice and Bob's secret keys are ideal representations for the isogenies ϕ A and ϕ B (or equivalently the endomorphism ring of the two curves E A and E B ), and their associated public keys are the suborder representations for ϕ A and ϕ B .

Leroux showed that the knowledge of End(E A ) (resp. End(E B )) and the suborder representation of ϕ B (resp. ϕ A ) was enough to compute the end curve E AB from which the common secret can be derived efficiently. The mechanism behind this computation is quite complicated and is not relevant for us since we target the key recovery problem. We refer to [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF] for more details.

The hidden subgroup problem

The hidden subgroup problem (HSP for short) in a group G is defined as the problem of finding a subgroup H ≤ G given a function f on G satisfying that f is constant on the left cosets of H and takes different values on different cosets, i.e., f (x) = f (y) if and only if x -1 y ∈ H. There is also a right version of the hidden subgroup problem where the level sets of the hiding function f are the right cosets of H. As taking inverses in G maps left cosets to right cosets and vice versa, the two versions of HSP are equivalent. (One just needs to replace the hiding function with its composition with taking inverses.) Although the equivalence is straightforward, it is useful as in certain cases it is easier to understand right cosets than left ones (or conversely).

The framework of HSP captures many computational problems including some problems which most cryptographic protocols used today rely on, e.g., factoring and the discrete logarithm problem. Shor's quantum algorithms [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF] can solve factoring and the discrete logarithm problem efficiently. Furthermore, quantum polynomial time algorithms for the finite abelian HSP generalizing Shor's algorithm are available, see [START_REF] Yu | Quantum measurements and the abelian stabilizer problem[END_REF], [START_REF] Boneh | Quantum cryptanalysis of hidden linear functions[END_REF].

It is well known that the graph isomorphism problem can be cast as HSP in symmetric. Also, a method solving the HSP in dihedral groups via the standard approach would also solve a special, though still presumably hard special case of the shortest vector problem. However, in contrast to the abelian case, there are only a few positive results known for HSP in finite non-commutative groups. As shown in [START_REF] Ettinger | On quantum algorithms for noncommutative hidden subgroups[END_REF], HSP in dihedral groups is related to another problem called the hidden shift problem. The hidden shift problem in a group G is the problem of finding an element s ∈ G given two functions f 1 and f 2 on G satisfying that f 1 (g) = f 2 (gs) for every g ∈ G. If f 1 and f 2 are injective then the hidden shift problem in an abelian group G is equivalent to a hidden subgroup problem in the semidirect product G⋊Z/2Z. This is of particular interest in isogeny contexts, as the key recovery problem in CSIDH can be reduced to the injective hidden shift problem in abelian groups in order to produce quantum subexponential-time attacks based on Kuperberg's algorithm [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF].

In this paper, we consider a restricted HSP in the general linear group. We use the term Borel hidden subgroup problem for it.

Problem 2.3. Let N ∈ Z ≥1 and let Z/N Z be the group of integers modulo N . The Borel HSP is the hidden subgroup problem in the general linear group GL n (Z/N Z) for N ∈ Z ≥1 , i.e., the group of invertible n by n matrices with entries from Z/N Z, where the hidden subgroup H is promised to be a conjugate of the subgroup consisting of the upper triangular matrices.

Restricting the possible hidden subgroups in non-abelian groups may lead to efficient algorithms to find them. Denney et al. in [START_REF] Denney | Finding conjugate stabilizer subgroups in PSL and related groups[END_REF] proposed a polynomial-time algorithm for the Borel HSP in GL 2 (F p ) for prime numbers p. A quantum algorithm for the more general case of GL n (F q ) over fields of size q = p k , is provided by Ivanyos in [START_REF] Ivanyos | Finding hidden borel subgroups of the general linear group[END_REF]. That algorithm runs in polynomial time if q is not much smaller than n.

In this paper, we consider the Borel HSP for GL 2 (Z N ) for any integer N greater than one, and we present both classical and quantum algorithms for different parameters N . Note that GL 2 (Z/N Z) acts as a permutation group on the set of the free cyclic Z/N Z-submodules of (Z/N Z) 2 and each Borel subgroup H in GL 2 (Z/N Z) is the stabilizer of a free cyclic Z/N Z-submodule S of (Z/N Z) 2 , thus finding the Borel subgroup is equivalent to finding the corresponding cyclic submodule. The main tool of the classical algorithm is a testing procedure to determine whether elements of (Z/N Z) 2 are in S. The classical algorithm solves the Borel HSP efficiently for any smooth number N , while the quantum algorithm efficiently solves the Borel HSP for arbitrary N . The main idea of the quantum algorithm is based on the observation that the problem can be reduced to another restricted hidden subgroup problem in the group G = (Z/N Z) 2 ⋊(Z/N Z) * where the hidden subgroup is promised to be a complement of the normal subgroup (Z/N Z) 2 . The latter restricted HSP can be cast as an instance of the multiple shift problem considered in [START_REF] Ivanyos | On Learning Linear Functions from Subset and Its Applications in Quantum Computing[END_REF], which can itself be seen as a generalization of the hidden shift problem.

Problem 2.4. The hidden multiple shift problem HMS(N, n, r) is parameterized by three positive integers N, n and r, where N > 1 and 2 ≤ r ≤ N -1. Assume that we have a set H ⊆ Z/N Z of cardinality r and a function

f s : (Z/N Z) n × H → {0, 1} l , defined as f s (x, h) = f (x -hs) where s ∈ (Z/N Z) n and f : (Z/N Z) n → {0, 1} l is an injective function.
Given f s by an oracle, the task is to find s mod N δ(H,N ) , where δ(H, N ) is defined as the largest divisor of N such that h -h ′ is divisible by δ(H, N ) for every h, h ′ ∈ H.

A special case of the HMS problem was first considered by Childs and van Dam [START_REF] Andrew | Quantum algorithm for a generalized hidden shift problem[END_REF]. They presented a quantum polynomial time algorithm for the case when n = 1 and H is a contiguous interval of size N Ω(1) . For general n, an algorithm in [START_REF] Ivanyos | On Learning Linear Functions from Subset and Its Applications in Quantum Computing[END_REF] solves HMS(N, n, r) in O(poly(n)( N r ) n+O( 1) ). For a set H of small size, HMS is close to the hidden shift problem. Specifically, HMS(N, n, 2) is the standard hidden shift problem, though modulo a divisor of N depending on the difference of the two elements of H. On the other extreme, for r = N , HMS is an abelian hidden subgroup problem in the group (Z/N Z) n+1 . Intuitively, the larger r is, the easier HMS(N, n, r) becomes. Below we restate the above mentioned result from [START_REF] Ivanyos | On Learning Linear Functions from Subset and Its Applications in Quantum Computing[END_REF] for the special case n = 1.

Theorem 2.5. There is a quantum algorithm that solves the HMS(N, 1, r) in time N r O(1) with high probability.

The malleability oracle

In [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF] the authors introduce a general framework dubbed the malleability oracle. Let G be a group acting on a set X and let f : X → I be an injective function where I is some set. The input of the malleability oracle is an element g ∈ G and a value f (x) (x is not provided) and the output is f (g * x). It is shown in [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF]Theorem 3.3] that if G is abelian and the action of G on X is free and transitive then inverting f (x) can be reduced to an abelian hidden shift problem. The idea of the proof is as follows. One takes an arbitrary known x 0 and the corresponding f (x 0 ). Then one can define two functions f 0 , f 1 from G to I where f 0 (g) = f (g * x 0 ) and f 1 (g) = f (g * x). These functions are well-defined as f was injective. Now since the action of G is transitive there is an element s that takes x 0 to x. One can easily see that f and f 0 are shifts of each other and the shift is realized by that element s. Since the action is free, f and f 0 will be injective functions themselves hence one can apply Kuperberg's algorithm to find s and finally that is enough to compute x.

Remark 2.6. It follows from the proof that it is not strictly necessary for the action to be transitive. It is enough if we know any element in the orbit of the secret x. For instance it suffices if there are only a few orbits and we have a representative of each of them (as we can run Kuperberg's algorithm multiple times with different x 0 s).

The way to interpret this result is as follows. If one has a way instantiating the malleability oracle, then one can utilize that to invert the function in subexponential time. For isogeny-based cryptography the natural function to be considered here is the one-way function sending a subgroup H to the elliptic curve E/H. In [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF] it is shown that [KMPW21, Theorem 3.3] applies to two scenarios:

-In CSIDH when curves and isogenies are defined over F p . This result was not novel as it is the same as the original hidden shift attack -In SIDH when one knows the image of the secret isogeny on a sufficiently large torsion group

We explain the second application a bit further. Let E be a supersingular elliptic curve with known endomorphism ring O. Here we assume that one can evaluate every element of O efficiently on points of E. Let N be any integer.

Then O/N O is isomorphic to M 2 (Z/N Z) [Voi18, Theorem 42.1.9]. This implies that (O/N O) * is isomorphic to G = GL 2 (Z/N Z)
. Now it is clear that G acts on cyclic subgroups of order N of E by evaluation. When there is a one-to-one correspondence between cyclic subgroups of order N and N -isogenous curves to E, then this implies an action on N -isogenous curves to E. What would a malleability oracle look like in this framework? One is given a curve E ′ that is N -isogenous to E. Let A be the corresponding secret kernel. Now the input of the oracle is an endomorphism σ (whose degree is coprime to N ) and then it returns E/σ(A). [KMPW21, Theorem 3.3.] "almost" states that if one has access to such an oracle, then one can compute A via a hidden shift algorithm. The "almost" part comes from the fact that G here is not abelian and the group action is not free. In [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF] it is shown that one can get around this issue by essentially just utilizing a subgroup of G that is abelian (and evoking some small technical conditions).

One can look at this result as a subexponential quantum reduction from finding a certain N -isogeny to being able to instantiate the malleability oracle, which is formulated as Problem 1.3. The results of Section 4 will be related to a generalization of 1.3.

In [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF] the authors were able to solve Problem 1.3 when deg(ϕ) = 2 k and the action of ϕ is known on a sufficiently large subgroup of E. In order to achieve this result one had to throw away most of the available information (by restricting G to a small abelian subgroup) in order to fit the malleability oracle framework. In this paper we show that utilizing the entire G-action improves on [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF] significantly.

The second claim can be reinterpreted in the context of the IsERP problem. Namely when the isogeny degree is a power of 2 and the isogeny is provided with some isogeny representation, then one can compute the endomorphism ring of the codomain in quantum subexponential time (assuming the endomorphism ring of the domain curve was known).

The Borel hidden subgroup problem

In this section, we present both classical and quantum algorithms for the "twodimensional" Borel hidden subgroup problem. The classical algorithm solves the Borel HSP efficiently in the group GL 2 (Z/N Z) for smooth number N , while the quantum algorithm solves it efficiently for any positive odd number N . For an even number N we can use a classical procedure applied to the 2-part of N with the quantum one for the odd part of N to obtain a quantum method for every N .

Let N be an integer greater than one. By fixing a basis, we have an explicit isomorphism End((Z/N Z) 2 ) ∼ = M 2 (Z/N Z) and Aut((Z/N Z) 2 ) ∼ = GL 2 (Z/N Z). Note that GL 2 (Z/N Z) acts as a permutation group on the set of the free cyclic Z/N Z-submodules of (Z/N Z) 2 . Let H be the stabilizer of a secret free cyclic submodule S. In the matrix notation, H is a conjugate of the subgroup consisting of the upper triangular matrices in GL 2 (Z/N Z). That is, in an appropriate basis for (Z/N Z) 2 , the elements of H are of the form * * 0 * , where the diagonal entries are units in Z/N Z. (Here the first basis element is a generator for S.) The Borel HSP in GL 2 (Z/N Z) is the following: we are given a function on GL 2 (Z/N Z) (given by an oracle) that is constant on the left cosets of H and takes different values on distinct cosets, the task is to find H, or equivalently the submodule S.

Using Chinese remaindering, one can reduce the case when N is any number of known factorization to instances of the prime power case.

Lemma 3.1. Let N = N 1 N 2 be a known decomposition of N where gcd(N 1 , N 2 ) = 1. Then we have

GL 2 (Z/N Z) ∼ = GL 2 (Z/N 1 Z) × GL 2 (Z/N 2 Z).
Moreover, one can reduce the Borel HSP in GL 2 (Z/N Z) to the Borel HSP in GL 2 (Z/N i Z) for i = 1, 2.

Proof. By the Chinese Remainder Theorem

, Z/N Z ∼ = Z/N 1 Z⊕Z/N 2 Z, (Z/N Z) 2 ∼ = (Z/N 1 Z) 2 ⊕ (Z/N 2 Z) 2 , End((Z/N Z) 2 ) ∼ = End((Z/N 1 Z) 2 ) ⊕ End((Z/N 2 Z) 2 ).
Furthermore, these isomorphisms can be efficiently computed using the extended Euclidean algorithm. The restriction of the third isomorphism also gives Aut(

(Z/N Z) 2 ) ∼ = Aut((Z/N 1 Z) 2 ) × Aut((Z/N 2 Z) 2 ). The stabilizer H of the free cyclic submodule S generated by (A 1 , A 2 ) ∈ (Z/N 1 Z) 2 ⊕ (Z/N 2 Z) 2
is the direct product of the stabilizers H i of S i , where S i are the free cyclic submodules over Z/N i Z generated by A i . Hiding functions for H i can be obtained by restricting the hiding function for H to the component Aut((Z/N i Z) 2 ).

⊓ ⊔

A classical Borel HSP algorithm

Based on iterated applications of Lemma 3.1, we can focus on the prime power case. (Note that the factorization of N can be computed in deterministic time polynomial in B log N where B is an upper bound on the prime divisors of N .) Therefore, we assume N = q k for a prime number q.

An important subroutine in our algorithm is a procedure for testing whether an element u ∈ (Z/N Z) 2 is in S based on the following observations. If u ∈ S then for any φ ∈ End((Z/N Z) 2 ) such that φ + Id ∈ GL 2 (Z/N Z) and φ((Z/N Z) 2 ) ≤ Z/N Zu we have φ + Id ∈ H. This is because for u ∈ S we have φ(u) ∈ Z/N Zu ≤ S and Id(u) = u ∈ S. On the other hand, if u ̸ ∈ S then there exists an element φ ∈ End((Z/N Z) 2 ) with φ(V ) ≤ Z/N Zu and φ(S) ̸ ≤ S. Indeed, if {v, w} is an Z/N Z-basis of (Z/N Z) 2 such that v is a generator of S, then the map sending v to u and w to zero satisfies these properties.

Another ingredient of the testing procedure is the following.

Lemma 3.2. If φ + Id ∈ GL 2 (Z/N Z) then φ(S) ≤ S if and only if φ + Id ∈ H.
Proof. If φ(S) ≤ S then (φ+Id)S ≤ φ(S)+S = S. To see the reverse implication, assume that φ(v) ̸ ∈ S for some v ∈ S.

Then φ(v) + v is in the coset φ(v) + S disjoint from S. ⊓ ⊔
Thus for φ with φ + Id ∈ GL 2 (Z/N Z) we can test whether φ(S) ≤ S by comparing the value of the hiding function taken on φ + Id with that on Id.

Testing procedure: Let w 1 , w 2 be a fixed basis of (Z/N Z) 2 . Given u ∈ (Z/N Z) 2 we define two maps φ 1 , φ 2 by φ i (w i ) = u and φ i (w 3-i ) = 0. Note that φ 1 and φ 2 generate E u := {φ ∈ End((Z/N Z) 2 ) : φ((Z/N Z) 2 ) ≤ Z/N Zu} as an Z/N Z-submodule of End((Z/N Z) 2 ). Therefore if φ i (S) ≤ S (i = 1, 2) then for every element φ ∈ E u we have φ(S) ≤ S. If u ∈ q(Z/N Z) then φ i -Id ∈ q End((Z/N Z) 2 ) -Id ⊆ GL 2 (Z/N Z) (i = 1, 2), so we can test whether u ∈ S by testing φ i (S) ≤ S (i = 1, 2) by comparing the value of the hiding function taken on φ i + Id with that on Id. If q ̸ = 2 then either φ i -Id or -φ i -Id (or both) fall in GL 2 (Z/N Z) (depending on the nonzero eigenvalue of φ i modulo q), so the test above works with a minor modification for u ̸ ∈ q(Z/N Z) as well.

Finally, to cover the case q = 2 and u ̸ ∈ q(Z/N Z) observe that u ∈ S if and only if S = Z/N Zu. To test whether this is the case we compute generators for the subgroup H Z/N Zu = {φ ∈ GL 2 (Z/N Z) : φ(u) ∈ Z/N Zu} and test membership of these generators for membership in H again by comparing values of the hiding function.

Equipped with the testing procedure, we compute S from "bottom up" as follows. First we compute S ∩ q k-1 (Z/N Z) 2 . Note that q k-1 (Z/N Z) 2 ∼ = (Z/qZ) 2 and there are q + 1 possibilities for S k-1 = S ∩ q k-1 (Z/N Z) 2 . We can find S ∩ q k-1 (Z/N Z) 2 by brute force based on the testing procedure on all q + 1 submodules corresponding to each possibility in time qpoly log |N |. Assume that we have computed S l = S ∩ q l (Z/N Z) 2 for some l > 0. Then we compute V l = {v ∈ q l-1 (Z/N Z) 2 : qv ∈ S l } and by an exhaustive search in the factor V l /S l we find S l-1 = S ∩ q l-1 (Z/N Z) 2 using again the test in time qpoly log |N |. Note that V l /S l is an elementary abelian group of rank at most two. (A factor of a subgroup of an abelian q-group generated by 2 elements is also 2-generated.) The total cost is kqpoly log |N |.

We deduce the following result.

Theorem 3.3. There is a classical algorithm that solves the Borel hidden subgroup problem in GL 2 (Z/N Z) in time poly(B log N ) where B is an upper bound for the largest prime factor of N .

A quantum algorithm

Denney, Moore and Russell [START_REF] Denney | Finding conjugate stabilizer subgroups in PSL and related groups[END_REF] proposed a quantum polynomial time algorithm that solves the problem in the case when N is a prime. In this subsection we extend their method to arbitrary N as follows. Based on Lemma 3.1 and Theorem 3.3, it is sufficient to give a procedure that works modulo the odd part of N . Thus, in the rest of the discussion we can and do assume that N is odd. We use the notation introduced at the beginning of the section. In particular, H is the stabilizer of a secret free cyclic Z/N Z-submodule S of (Z/N Z) 2 . Note that (Z/N Z) 2 /S is again a free cyclic Z/N Z-module whence for w = (1, 0) T or w = (0, 1) T we have that S and w generate (Z/N Z) 2 . We describe an algorithm that works under the assumption that S and w = (1, 0) T generate V . If that fails, we repeat it after an appropriate basis change.

From the assumption, it follows that there is a unique element s ∈ Z/N Z such that S is generated by v = (s, 1) T . We restrict the hidden subgroup problem to the stabilizer K of the vector w. Note that K is the group consisting of invertible matrices of the form 1 * 0 * .

Observe that K is isomorphic to the semidirect Z/N Z ⋊ (Z/N Z) * where the action of (Z/N Z) * on Z/N Z is the multiplication by its elements and the hidden subgroup H ∩ K is the stabilizer of the free cyclic submodule S in K. Note that the stabilizer of the submodule (Z/N Z)v in K is the conjugate of the stabilizer of the submodule of (Z/N Z) 2 generated by (0, 1) T in K by the unitriangular matrix 1 s 0 1 transporting (0, 1) T to v = (s, 1) T . Hence, by a straightforward calculation, the stabilizer H ∩ K of the submodule Z/N Zv in K is the subgroup

K s = 1 hs -s 0 h : h ∈ (Z/N Z) * . ( 1
)
As N is odd, the images of the matrices of the form M -Id where M ∈ H ∩ K:

0 (h -1)s 0 h -1 : h ∈ (Z/N Z) *
generate the submodule Z/N Zv. Indeed, 2 ∈ (Z/N Z) * and hence we have M = 1 s 0 2 ∈ H ∩ K and so the image of M -Id is Z/N Zv.

As shown in the preprint version of [IPS18], the HSP in K ∼ = Z/N Z ⋊ (Z/N Z) * where the hidden subgroup H is a conjugate of the complement (Z/N Z) * can be cast as an instance of the hidden multiple shift problem HM S(N, 1, r) with r = ϕ(N ), the Euler's totient function of N . To see this, note that from (1) it follows that the right cosets of K s are of the form

K s • 1 a 0 1 : h ∈ (Z/N Z) * = 1 hs -s + a a h : h ∈ (Z/N Z) * .
Therefore, when we encode the elements g of K by the second column of g -Id, the right version of the HSP gives an instance of the hidden multiple shift problem on H×{h-1 : h ∈ (Z/N Z) * }. As already noted in Section 2.6, the left version of the HSP is equivalent to the right one. Therefore, since HM S(N, 1, ϕ(N )) can be solved efficiently by Theorem 2.5, we obtain the following result.

Theorem 3.4. There is a quantum algorithm that efficiently finds the associated free cyclic submodule S for the hidden Borel subgroup H in GL 2 (Z/N Z) in time (log N ) O(1) .

On the isogeny to endomorphism ring problem

In this section, we study the IsERP and its connection to other algorithmic problems. Our final result provides a reduction from the IsERP to a pure quaternion problem, the PQLP (Problem 4.10), but we obtain this reduction through a quantum equivalence between the IsERP and the Group Action Evaluation Problem, that can be seen as a generalization of Problem 1.3. Most of the work in this section is dedicated to this equivalence. In Section 4.1, we formally introduce the group action we consider. Then, in Section 4.2, we prove the result. Finally, in Section 4.3 we give the link with the PQLP and study the hardness of this problem.

4.1

The group action of GL 2 (Z/N Z) on N -isogenies.

In this section, we cover all necessary results on the group action we will consider. For that, it is important to understand how 2 × 2 matrices mod N appear naturally when you consider the action of endomorphisms on the N -torsion. This comes from the isomorphism End(E)/N End(E) ∼ = M 2 (Z/N Z) which is a natural extension of the isomorphism E[N ] ∼ = Z/N Z 2 . We elaborate on that in the next paragraph. If one wants to compute an explicit isomorphism between End(E)/N End(E) and M 2 (Z/N Z) one can use the above method of evaluating a basis of End(E) on a basis of E[N ]. However, when E[N ] is defined over a large extension field (e.g., N is large random prime), then this method is not efficient.

The issue can be circumvented by looking at the problem from a slightly different angle. Namely we have basis of End(E)/N End(E) and we also have a multiplication table of the basis elements. Such a representation is called a structure constant representation. Rónyai [START_REF] Rónyai | Computing the structure of finite algebras[END_REF] proposed a polynomial-time algorithm for this problem when N is prime. The next lemma generalizes the algorithm to arbitrary N whose factorization is known.

Proposition 4.1. Let A be a ring isomorphic to M 2 (Z/N Z) given by a structure constant representation. Suppose that factorization of N is known. Then there exists a polynomial-time algorithm that computes an explicit isomorphism between A and M 2 (Z/N Z).

Proof. First we reduce the problem to the case where N is prime power. Let N = ab where a and b are coprime. Then A/aA is isomorphic M 2 (Z/aZ) and A/bA is isomorphic to M 2 (Z/bZ). Since M 2 (Z/aZ) × M 2 (Z/bZ) is isomorphic to M 2 (Z/N Z), knowing an explicit isomorphism between A/aA and M 2 (Z/aZ) and an explicit isomorphism between A/bA and M 2 (Z/bZ) is enough to recover the isomorphism between A and M 2 (Z/N Z). Using this procedure iteratively (using the fact that the factorization of N is known) one can reduce to the case where N = q k where q is some prime number. Now suppose that A is isomorphic to M 2 (Z/q k Z). Observe that A/qA is isomorphic to M 2 (Z/qZ). One can compute a non-trivial idempotent in A/qA using Rónyai's algorithm [START_REF] Rónyai | Computing the structure of finite algebras[END_REF], let that be e 0 . Now observe that qA is the Jacobson radical of A. Indeed, since qA is clearly contained in the radical and A/qA is semisimple. Then [DK12, Corollary 3.1.2] says that e 0 can be lifted modulo qA to an idempotent of A. Now we know the existence, we show how one can do that algorithmically.

One has that e 2 0 -e 0 ∈ qA and e 0 and e 0 -1 are not in qA. Our goal is to find an element e which is an idempotent of A. We will perform an iteration which starts with e 0 and in the ith step we return an element e i for which e 2 i -e i ∈ q i+1 A. Suppose we have an element e i-1 for which e 2 i-1 -e i-1 ∈ q i A. Now we are looking for an f ∈ A such that (e i-1 +f q i ) 2 -(e i-1 +f q i ) ∈ q i+1 A. Let (e 2 i-1 -e i-1 )/q = E i-1 . Then this is equivalent to e i-1 f + f e i-1 ≡ 1 -E i-1 (mod ()q). This is a system of linear equations that has a solution by [DK12, Corollary 3.1.2] thus can be found efficiently. Now we have thus found an idempotent e of A.

Since A is a 2 × 2 matrix ring, I = Ae is an irreducible A-module. Then the left action of A on I provides an explicit isomorphism between A and M 2 (Z/qZ). We could not find a reference for this fact, so we present a quick simple proof. be an idempotent matrix. We can assume that it has the above form as e is not congruent to 0 or the identity matrix modulo qA. We also have that a(1 -a) = bc. Now the following is a generating set (as an abelian group) of Ae:

a b 0 0 , 0 0 a b , c (1 -a) 0 0 , 0 0 c (1 -a)
.

One has that either a or 1 -a is invertible in Z/q k Z, one may suppose that a is invertible (the calculation is the same in the other case). Then it is clear that every element of the form

α α(b/a) β β(b/a)
is in the left ideal for any α, β ∈ Z/q k Z. We show that every element of Ae is of this form. This follows from the fact that every element of the form

is an isomorphism of A-modules. ⊓ ⊔ Remark 4.2.
Once an idempotent e is found, one can finish the proof in an alternate way as well. Namely one can show that Im(e) = ker(e) is a cyclic subgroup of (Z/q k Z) 2 of cardinality q k . Then a generator of ker(e) and ker(1e) will be a basis in which e is 1 0 0 0 which shows indeed that the left ideal generated by e is minimal.

The group action of invertible matrices on isogenies. Now, let us take a cyclic subgroup G ⊂ E[N ] of order N (this is a submodule of rank 1 inside (Z/N Z) 2 with our isomorphism). If σ ∈ GL 2 (Z/N Z), then it is clear that σ(G) is also a cyclic subgroup of order N . Thus, we have a natural action of GL 2 (Z/N Z) on the cyclic subgroups of order N . This group action on subgroups of order N can naturally be extended to a group action of GL 2 (Z/N Z) on the set of N -isogenies from E through the bijection between cyclic subgroups of order N and N -isogenies given by G → (ϕ G : E → E/G) (and whose inverse is simply ϕ → ker ϕ).

Composing this bijection with the group action we already have, we get the following group action

M σ ⋆ ϕ G → ϕ σ(G) . ( 2
)
This action is always well-defined. However, for computational purposes, we want ways to efficiently represent its elements and compute the action ⋆. These considerations motivate the remaining of this paper.

The problem we consider is the following:

Problem 4.3 (Group Action Evaluation Problem). Let E be a supersingular elliptic curve over F p 2 and let ϕ : E → E 1 be an isogeny of degree N for some integer N . Given End(E), an isogeny representation for ϕ, M in GL 2 (Z/N Z), find an isogeny representation of M ⋆ ϕ.

The stabilizer subgroups. One last thing that will be important to apply our results to this group action is to identify the stabilizer subgroup associated to a given isogeny ϕ. In fact, those are pretty easy to identify and are well-known objects. The answer is given by the following proposition.

Proposition 4.4. Let ϕ : E → E ′ be an isogeny of degree N . The stabilizer subgroup associated to ϕ through the group action defined in Equation ( 2) is made of the matrices M σ such that σ is in the Eichler order Z + I ϕ where I ϕ is the ideal associated to ϕ under the Deuring correspondence.

Proof. By definition of the group action, the stabilizer subgroup is obtained with the matrices M σ such that σ(ker ϕ) = ker ϕ. This means that σ acts as a scalar λ σ on ker ϕ. Thus, ker ϕ ⊂ ker(σ -λ σ ) and by definition of I ϕ , we have that In this section, we prove a quantum polynomial-time equivalence between the the Group Action Evaluation Problem and the IsERP.

σ -λ σ ∈ I ϕ , hence σ ∈ Z + I ϕ .
Theorem 4.7. The Group Action Evaluation Problem reduces to the IsERP in classical polynomial-time.

Proof. Assume we have an efficient algorithm to solve the IsERP. Let us take an instance of the Group Action Evaluation Problem. So we have N, E, End(E), a representation for ϕ and a matrix M , and we want to compute a representation for M * ϕ. The first step of the reduction is to compute the ideal I ϕ associated to ϕ. There are several ways to do that, but to keep this proof short, we will use some of the results proven in [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF]. Thus, our first step is to build a suborder representation for the isogeny ϕ as in [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF]. The suborder representation is made of endomorphisms of Z + N End(E) → End(E ′ ) of powersmooth norm. Since we know End(E) and End(E ′ ), the algorithms of the Deuring correspondence can be used to compute their kernels in polynomial time (their norm being powersmooth implies that their kernels are defined over a small extension). Then, we can compute the suborder representation using Vélu's formulas. Once we have the suborder representation, we can apply the equivalence between the SOIP and the SOERP [Ler22a, Proposition 13] to find the ideal I ϕ . Once I ϕ has been computed, we need to compute the ideal I M ⋆ϕ . For that we are going to use a σ such that M σ = M . We can build such a σ in polynomial time from End(E) using Proposition 4.1.

Once a good σ is known, we get the ideal I M ⋆ϕ as σ(I ϕ ∩Oσ)σ -1 +N O (where we take O ∼ = End(E)). Since the ideal I Mσ⋆ϕ is a valid isogeny representation, this proves the result.

⊓ ⊔ Theorem 4.8. The IsERP reduces to the Group Action Evaluation Problem in quantum polynomial time.

Proof. Assume we can solve the Group Action Evaluation Problem. Let us take an input of the IsERP, we have a curve E, its endomorphism ring End(E), an integer N and the isogeny representation associated to an isogeny ϕ of degree N .

The algorithm to solve the Group Action Evaluation Problem allows us to compute efficiently the group action introduced in Section 4.1. Using Proposition 4.6 and Theorem 3.4 one can compute the stabilizer subgroup associated to ϕ. As the stabilizer subgroups of ϕ give us matrices corresponding to some σ in the Eichler order Z+I ϕ , we can compute the embedding of this order in O ∼ = End(E) in polynomial time using the algorithm of Proposition 4.1. Then, we can extract the ideal I ϕ and compute O R (I ϕ ) which is isomorphic to End(E ′ ) and this gives the result.

⊓ ⊔

When the degree N is smooth, we can modify the proof of Theorem 4.8 to get a classical reduction by using Theorem 3.3 instead of Theorem 3.4. Theorem 4.9. Suppose that degree of the secret isogeny is smooth. Then IsERP reduces to the Group Action Evaluation Problem in classical polynomial time.

Reduction of the Group Action Evaluation Problem to the PQLP.

In this section, we reduce the Group Action Evaluation Problem to another problem that we call the Powersmooth Quaternion Lift Problem (PQLP). The PQLP can be stated as follows:

Problem 4.10. Let O be a maximal order in B p,∞ . Given an integer N and an element σ 0 ∈ O such that (n(σ 0 ), N ) = 1, find σ = λσ 0 mod N O of powersmooth norm with some λ coprime to N .

We use PQLP O (σ 0 ) to denote the set of σ ∈ O that satisfy the conditions in Problem 4.10 with respect to σ 0 ∈ O. The high level idea of the reduction from the PQLP to the Group Action Evaluation Problem is close to the approach introduced in [START_REF] Kutas | One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols[END_REF]. Given a matrix M , the goal is to find a good representative of the class of M , i.e. a σ ∈ End(E) of powersmooth norm, such that M = M σ . Then, we can use Vélu's formulae to solve the Group Action Evaluation Problem.

Proposition 4.11. The Group Action Evaluation Problem reduces to PQLP in classical polynomial time.

Proof. Let us take an instance of our problem. We have N, E, End(E), an isogeny representation for ϕ : E → E ′ of degree N and a matrix M .

We need to show that if we know a σ ∈ End(E) (represented as a quaternion element in a maximal order O ∼ = End(E)) of powersmooth norm such that M σ = M , then we can compute a representation for M ⋆ ϕ in polynomial time.

For that, we will use the following commutative isogeny diagram

E ′ σ ′ / / E ′ /σ(ker ϕ) E ϕ O O σ / / E M ⋆ϕ O O
where σ ′ has the same degree as σ and is defined by ker σ ′ = ϕ(ker σ). Since the isogeny σ ′ has powersmooth degree, it can be computed in polynomial time once ker σ ′ has been computed. Since, we can evaluate ϕ, it suffices to compute ker σ and this can be done in polynomial-time since we known End(E).

Since the diagram is commutative, we have that σ ′ • ϕ = M ⋆ ϕ • σ and this gives us the way to evaluate efficiently M ⋆ ϕ on almost all torsion (as soon as the order is coprime to deg σ) as M ⋆ ϕ = σ′ • ϕ • σ/ deg σ. This is sufficient to build a suborder representation of M ⋆ ϕ (see the algorithm outlined in the proof of Theorem 4.8).

This proves that the main computational task is to find this σ of powersmooth norm. Thus, it suffices to apply an algorithm to solve the PQLP on input N , End(E) and a σ 0 such that M σ0 = M (that we can find using Proposition 4.1).

⊓ ⊔

Resolution of the PQLP

In this section, we solve the PQLP (Problem 4.10) with conditions imposed on the factors of N , as detailed in the following theorem.

Theorem 5.1. Let N = ℓ ei i ̸ = p be an odd integer that is of size polynomial in p and has O(log(log p)) factors, then there exists a randomized classical polynomial time algorithm that solves the PQLP. This theorem follows from the correctness of Algorithm 3 which is introduced and discussed in Section 5.2. The successive reductions from the IsERP to the Group Action Evaluation Problem, and subsequently to the PQLP, demonstrate the existence of a polynomial time algorithm that solves the IsERP, given N satisfies the conditions in Theorem 5.1. As a direct consequence, this breaks pSIDH quantumly since N is a large prime in pSIDH. As mentioned previously, the IsERP is easy when N is powersmooth. We briefly discuss some approaches to solve the general case in [CII + 23, Appendix D].

In Section 5.1, we give a summary of useful known algorithms and provide variants for RepresentInteger, StrongApproximation and KLPT to better accommodate our specific application. Following this, we introduce our primary strategy for resolving the PQLP in Section 5.2. In Section 5.3, we deal with a critical technical point which we introduce as the Quaternion Decomposition problem. The crux of this problem, and indeed our main conceptual contribution, is the decomposition of σ 0 into elements that are easy to lift, and elements already possessing a powersmooth norm. Finally in Section 5.4, we provide a quantum algorithm that solves the PQLP.

Algorithmic building blocks

Our algorithm for the PQLP is founded on algorithmic building blocks initially introduced in [KLPT14] and later extended in other work, such as [DFKL + 20]. We provide a brief recap of these algorithms here, along with several new variants tailored to suit our requirements. We fix log c p to be our powersmooth bound for some constant c, and this bound is inherently implied whenever we reference the term 'powersmooth'.

As in [START_REF] Kohel | On the quaternion ℓ-isogeny path problem[END_REF], for each p, we fix a special p-extremal maximal order O 0 .

O 0 = Z⟨i, 1+j 2 ⟩ where i 2 = -1, j 2 = -p, for p ≡ 3 mod 4, Z⟨ 1+i 2 , j, ci+k q ⟩ where i 2 = -q, j 2 = -p, for p ≡ 1 mod 4,

where c is any root of x 2 + p mod q. In the second case, q is required to satisfy that q ≡ 3 mod 4 is a prime and -p q = 1. We add one extra condition that (q, N ) = 1. Under the generalized Riemann hypothesis (GRH), the smallest q is of size O(log 2 p). For the ease of exposition, we define q to be 1 when we are in the first case (i.e., when p ≡ 3 mod 4).

For each O 0 , we identify a suborder of the form R+Rj for R = Z[i] (note that we are making a slightly different choice here than the R in [START_REF] Kohel | On the quaternion ℓ-isogeny path problem[END_REF] where they always take R to the maximal order in Q(i)). For an element α = a + bi ∈ R, we use Re -Cornacchia(M ): on an input M that is a prime integer not equal to q, outputs either ⊥ if M cannot be represented by x 2 + qy 2 , or a solution x, y to the equation M = x 2 + qy 2 . -RepresentInteger O0 (M ): on an input M > p, outputs γ ∈ O 0 such that n(γ) = M . -StrongApproximation F (N, µ 0 ): on inputs an integer F > pN 4 , a prime N and µ 0 ∈ Rj, outputs λ / ∈ N Z and µ ∈ O 0 of norm dividing F such that µ = λµ 0 mod N O 0 .

-KLTP M (I): on inputs an integer M > p 3 and an ideal I, outputs an equivalent ideal J such that n(J) = M .

Let us denote the output γ of RepresentInteger O0 (M ) as C + Dj with C, D ∈ R. To fit our algorithm's specific use case, we require not only that n(γ) is powersmooth, but also that C, D satisfy additional conditions relative to some inputs A, B ∈ R, which are determined by σ 0 from the PQLP. As a result, we introduce the following variant named RepresentInteger ′ R+Rj (N, A, B). This variant necessitates more randomized steps to find the desired outputs C, D ∈ R. 1 Let k be the smallest integer such that the number of prime factors of N is less than k log log p, randomly generate M of size ⌊p log 3k+4 p log log p⌋ that is powersmooth and coprime to N .

2 Set m = ⌊ M p(q+1) ⌋ and sample random integers z, t ∈ [-m, m] 2 . 3 Set M ′ = M -p(z 2 + qt 2 ). 4 If (z 2 + qt 2 , N ) ̸ = 1 or (M ′ , N ) ̸ = 1 or M ′ is not a prime then 5 Go back to Step 2. 6 If Cornacchia(M ′ ) = ⊥ then 7 Go back to Step 2. 8 x, y = Cornacchia(M ′ ). 9 C ← x + yi, D ← z + ti. 10 If (N, ImR(A BC D)) ̸ = 1 then 11 Go back to Step 2.
12 If q(4p 2 n(ABCD) -(n(AC) -pn(AD)) 2 ) is not a square modulo N then 13 Go back to Step 2.

14 Return C, D.

Heuristic 5.2. We assume that M ′ , z 2 +qt 2 , Im R (A BC D) and q(4p 2 n(ABCD)-(n(AC) -pn(AD)) 2 ) appearing in Algorithm 1 behave like random integers of the same size.

Lemma 5.3. Let N be as in Theorem 5.1, assuming Heuristic 5.2, Algorithm 1 returns a solution in polynomial time.

Proof. For Step 4, by assumption, M ′ is a prime with probability 1/O(log p), and once we ensure that M ′ is a prime, (M ′ , N ) = 1 holds with a negligible failure rate. On the other hand, since the number of prime factors of N is less than k log log p, the probability that (z 2 + qt 2 , N ) = 1 holds is at least 1/O(log k p). Therefore, Step 4 succeeds with probability greater than 1/O(log k+1 p). For Step 10, similarly it succeeds with probability at least 1/O(log k p). For Step 6, x 2 + qy 2 = M ′ has a solution if and only if (M ′ ) is a product of two principal ideals in Z[i]. M ′ is split or ramifies in Z[i] with probability 1/2, and a random invertible ideal in

Z[i] is principal with probability 1/#Cℓ(Z[i]) > 1/O( √ q log q) [Coh95,
Section 5.10.1]. Since q is at most O(log 2 p), this step succeeds with probability greater than 1/O(log p log log p). Finally, for an integer to be a square modulo N , it's equivalent to this integer being a square modulo each prime factor of N . Therefore, Step 12 succeeds with probability at least 1/O(log k p). In total, the success probability is greater than 1/O(log 2+3k p log log p). In Step 2, there will be O(log 3k+2 p log log p) pairs of (z, t), therefore Algorithm 1 will return a solution in polynomial time.

⊓ ⊔

We also provide a generalization of the StrongApproximation algorithm to allow for composite N (note that in this algorithm we don't have restriction on the number of factors of N ). The subscript ps refers to powersmooth. Heuristic 5.4. We assume that M appearing in Algorithm 2 behaves like a random integer of the same size. Proof. This can be seen by checking how many solutions there are for equation N 1 x + N 2 y = N 3 mod ℓ ei i with ℓ ei i being a prime power divisor of N and then using Chinese Reminder Theorem.

⊓ ⊔ Lemma 5.6. Let N be an odd integer, assuming Heuristic 5.4, Algorithm 2 returns a solution in polynomial time.

Proof. The #S × #S linear equations behave like a random system of linear equations of the same dimension, therefore, repeating Step 3 constant number of times will give rise to a linear system over F 2 that is solvable. We have ensured that F generated in Step 8 is such that F n(µ0) is a square modulo N , hence Step 9 makes sense. Similar to what is discussed in the proof of Lemma 5.3, Step 12 succeeds with probability at least 1/O(log 2 p log log p). To make sure this Algorithm 2: StrongApproximation ps (N, µ 0 )

Input: An odd integer N and µ0 ∈ Rj such that (n(µ0), N ) = 1. Output: λ ∈ Z such that (λ, N ) = 1 and µ ∈ R with powersmooth norm such that µ = λµ0 mod N O0.

1 Write µ0 as (t + si)j with t, s ∈ Z.

2 Let S = {ℓ such that ℓ | N and n(µ 0 ) ℓ = -1}. 3 Randomly generate #S many prime pi's such that pi < log c p and let ϵij ∈ {0, 1} be the exponent such that p i ℓ j = (-1)

ϵ ij . 4 Solve the system of #S × #S equations Σ #S i=1 ϵijxi = 1 for j = 1, • • • , #S in F2. 5 If There is no solution found in Step 4 then 6 Go back to Step 3 7 F = #S i=1 p x i i .
8 Multiply a log c p-powersmooth square factor that is coprime to n(µ0) to F to ensure F > pN 4 . 9 Denote one of the square root of F n(µ 0 ) modulo N by λ. 10 Randomly generate c, d such that λp(2tc + 2qsd) ≡ (F -λ 2 p(t 2 + qs 2 ))/N mod N . 11 Set M = (F -p((λt + cN ) 2 + q(λs + dN ) 2 ))/N 2 . 12 If M is not a prime or Cornacchia(M ) = ⊥ then algorithm gets passed to Step 14, we need O(log 2 p log log p) many solutions from Step 10. According to Lemma 5.5, this happens if O(log 2 p log log p) < N , and this holds since N is assumed to be of size polynomial in p.

⊓ ⊔

Finally, another variant we introduce here is KLTP ′ M (O 0 , O). Here M is an integer such that M > p 3 . This algorithm first computes a connecting ideal I ′ from O 0 to O, then computes an equivalent left O 0 -ideal I of norm M whose right order is α -1 Oα for some nonzero α ∈ B p,∞ using KLPT M (I ′ ). This KLPT ′ algorithm outputs I and α.

The main algorithm

In this section, we first present a strategy that solves Problem 4.10 for special orders O 0 . Then, we expand this strategy to address more general orders O. Let σ 0 ∈ O 0 be as in Problem 4.10, the method proceeds as follows.

Find σ

′ 0 ∈ R + Rj such that σ ′ 0 = σ 0 mod N O 0 . Since [O 0 : R + Rj] = D, Dσ 0 ∈ R + Rj. Let D ′ ∈ Z be such that D ′ D ≡ 1 mod N , such D ′ exists since (D, N ) = 1, then σ ′ 0 = D ′ Dσ 0 ∈ R + Rj and σ ′ 0 = σ 0 mod N O 0
. By an abuse of notation, we will use σ 0 to denote σ ′ 0 in what follows. 2. Write σ 0 = A+Bj with A, B ∈ R, let γ be the output of RepresentInteger ′ R+Rj (N, A, B). Intuitively, γ is an element in R+Rj that has powermooth norm and satisfies extra properties to ensure the next step has a solution. 3. Find α 1 , α 2 , α 3 ∈ Rj such that σ 0 = α 1 γα 2 γα 3 mod N O 0 . This is the main technical point in this method, we introduce it as Problem 5.7 and discuss it in detail in Section 5.3. 4. Find γ i ∈ O 0 such that γ i = λ i α i mod N O 0 , n(γ i ) is powersmooth and (λ i , N ) = 1 for i = 1, 2, 3. These are exactly the outputs of StrongApproximation ps (N, α i ). 5. The element γ 1 γγ 2 γγ 3 ∈ O 0 satisfies that σ 0 = λγ 1 γγ 2 γγ 3 mod N O 0 with n(γ 1 γγ 2 γγ 3 ) powersmooth and λ coprime to N .

In general, let O be a maximal order in B p,∞ , and let n I > p 3 be a random integer that is coprime to N . Let n ′ I ∈ Z such that n ′ I n I ≡ 1 mod N . Let I, α be the outputs of KLPT n I (O 0 , O) such that I is a connecting ideal from O 0 to O ′ := α -1 Oα and n(I) = n I . We then have inclusions n

I O ′ ⊆ O 0 and n I O 0 ⊆ O ′ , therefore n I α -1 σ 0 α ∈ O 0 . Let σ ∈ PQLP O0 (n I α -1 σ 0 α), then σ = n I α -1 σ 0 α mod N O 0 . Multiplying n I with both sides of the equation yields that n I σ = n 2 I α -1 σ 0 α mod N O ′ . Multiplying n ′2 I on both sides gives that n ′ I σ = α -1 σ 0 α mod N O ′ . Since n ′ I is coprime to N , σ ∈ PQLP O ′ (α -1 σ 0 α), therefore ασα -1 ∈ PQLP O (σ 0 ).
We summarize the discussions above and present Algorithm 3.

Quaternion decomposition

In this section, we discuss how to perform Step 3 from the strategy outline. We start with introducing a new problem.

Note that the modulo condition in Equation (6) holds not just in N O 0 but in N R since [O K : R] = 1 or 2 is coprime to N . By assumption, n(C) and n(D) are both coprime to N , let n ′ C , n ′ D ∈ Z be integers such that n ′ C n(C) ≡ 1 mod N and n ′ D n(D) ≡ 1 mod N respectively, and let p ′ ∈ Z be such that p ′ p ≡ 1 mod N , then Equation ( 6) is equivalent to

(n ′ C p ′ )(pA Dx 3 -pB C x3 ) = x 1 x2 mod N R, (n ′ D p ′ )(ACx 3 + pBDx 3 ) = x 1 x 2 mod N R. (7)
Lemma 5.8. Equation (7) has a solution (x 1 , x 2 , x 3 ) ∈ R 3 if and only if there exists

x 3 ∈ R such that x := (n ′ C p ′ )(pA Dx 3 -pB C x3 ) and y := (n ′ D p ′ )(ACx 3 + pBDx 3 ) have same norm modulo N .
Proof. One solution to Equation (7) clearly implies n(x) = n(y) = n(x 1 )n(x 2 ). For the other direction, we provide a simple proof here for the case when N is a prime that is inert in R, and refer to [CII + 23, Appendix C] for the general case when N is an arbitrary odd integer. Since N is a prime that is inert in R, R/(N ) ∼ = F N 2 . Hilbert's Theorem 90 implies that if a ∈ R/(N ) has norm 1, then a = b/ b for b ∈ R/(N ). Since n(x) = n(y) and both x, y / ∈ N R, we have that n(x/y) = 1, therefore x/y = z/z for some nonzero z ∈ R/(N ). Consequently, x 1 , x 2 can be chosen to be lifts of yz and 1/z to R respectively.

⊓ ⊔ Remark 5.9. The method we present for odd integers N is constructive, therefore leads to an algorithm that finds x 1 , x 2 given x 3 such that n(x) = n(y). We call this algoithm EquivNormConjugationProduct(x 3 ). of the quadratic equation is a square modulo N . By our assumption this is the case. Then (s, t) viewed in (Z/N Z) 2 is defined up to a scalar, and we could simply choose s = 1 and let t 0 be one of the root of f (1, t) ≡ 0 mod N .

Finally, suppose (n(x 3 ), N ) = 1 does not hold, this implies (N, Im R (A BC D)) which contradicts our assumption. Therefore, we have shown that we could find a solution x 3 = s + ti where s, t satisfies Equation ( 8) and (n(x 3 ), 1) = 1.

We now summarize our algorithm for solving Problem 5.7 in Algorithm 4.

Quantum algorithm for the PQLP

As discussed earlier, Theorem 5.1 implies that we can solve the IsERP in quantum polynomial time. However, Theorem 5.1 only guarantees a randomized polynomial-time algorithm, and it might be advantageous to avoid that inside a quantum algorithm. So instead of lifting elements inside the quantum algorithm we lift O(log N ) elements first and then utilize them to make the lifting procedure inside the quantum algorithm deterministic (and free of any heuristic after the precomputation has succeeded).

Theorem 5.10. There is an algorithm that solves the PQLP in quantum polynomial time.

Proof. We provide a proof for the case where N is a prime number. The proof for general N is in [CII + 23, Appendix A]. For any matrix M in GL 2 (Z/N Z), M can be written as P L • D • U where P is a permutation matrix, L is a lower unitriangular (it is lower triangular with 1-s in the diagonal), D is diagonal, and U is upper unitriangular (it is upper triangular with 1-s in the diagonal). This decomposition can be found in polynomial time using Gaussian elimination. Now one has to decompose L, D and U separately. Any lower unitriangular matrix can be written as a power of A = 1 0 g 1 where g is a generator of (Z/N Z) * . Similarly, every upper unitriangular matrix can be written as a power of B = 1 g 0 1 . Any diagonal matrix can be written as C k D l where C = g 0 0 1 , D = 1 0 0 g . This shows that every element in GL 2 (Z/N Z) can be written as P A a B b C c D d . Thus instead of lifting elements inside the main quantum algorithm using Theorem 5.1 one can precompute lifts of P, A, B, C, D and then decompose a matrix M ∈ GL 2 (Z/N Z) as A a B b C c D d to obtain a lift of M . This decomposition requires several instances of the discrete logarithm problem in Z/N Z which can be computed in quantum polynomial time. The only issue is that if one computes a powersmooth lift of A (or B, C or D) then A a is not going to be powersmooth if a is large. To circumvent this issue one also computes lifts of A 2 k , B 2 k , C 2 k and D 2 k for every k between 1 and log 2 (N ). Furthermore, one computes lifts which are coprime (this can be ensured easily as StrongApproximation can lift an element in Z[i]j to any number that is bigger than p O(1) ).

This way P A a B b C c D d will also be powersmooth as it is the product of 4 log N + 1 powersmooth numbers. Lifting 4 log N + 1 numbers can be done in classical polynomial time using Theorem 5.1.

⊓ ⊔

Impact on isogeny-based cryptography

The most important application of Theorem 1.4 is that it breaks pSIDH in quantum polynomial time as N is a prime number in pSIDH. Another application is on SCALLOP [DFFK + 23]. Even though Theorem 1.4 does not break SCAL-LOP, it shows that its security reduces to the problem of evaluating the secret prime degree isogeny (up to a scalar). In [DFFK + 23] it is already discussed that one can deduce some information on the secret isogeny ϕ by utilizing the fact that one can evaluate ϕ • θ • φ efficiently on any point where θ is some fixed endomorphism on a curve which has an endomorphism of low degree (typically that curve is j-1728 and θ is the non-trivial automorphism).

Our results mildly generalize to the following setting. Let E be a supersingular elliptic curve that does not possess a non-scalar endomorphism of degree N 2 . In other words there is a one-to-one correspondence between cyclic subgroups of order N and N -isogenous curves. Our results imply that if given some curve E/A and an endomorphism σ one can compute E/σ(A), then one can also compute the endomorphism ring of E/A in quantum polynomial time (and actually the corresponding isogeny itself its degree is smooth). The difference between our previous results here is that we do not need an isogeny representation for the isogeny corresponding to the subgroup generated by A as long as we can evaluate the above group action. At the moment we do not see any particular application for this observation but it might prove to be a useful cryptanalysis tool in the future.

  The isomorphism. Let P, Q be a basis of E[N ]. We identify any point R = [x]P + [y]Q as the vector v R = (x, y) T . Then, an endomorphism σ ∈ End(E) can be seen as a matrix in M σ ∈ M 2 (Z/N Z) through its action on the basis P, Q. If we have σ(P ) = [a]P + [b]Q and σ(Q) = [c]P + [d]Q, then we can define M σ as a c b d and the representation of σ(R) is given by M σ v R . In that case, it can be easily shown that det M σ = deg σ mod N .

  γc γ(1 -a) δc δ(1 -a) can be written in this form (a linear combination of the second two basis elements) because if γc = α and δc = β, then α(b/a) = γ(1 -a) and β(b/a) = δ(1a) (because cb/a = (1-a)). Finally, it is clear that the map α α(b/a) β β(b/a) → (α, β)

  R (α) to denote a and Im R (α) to denote b. Let D denote the index [O 0 : R + Rj], then D = 4, for p ≡ 3 mod 4, 4q, for p ≡ 1 mod 4. (4) We will now detail the algorithmic building blocks, sourced from [KLPT14] or [DFKL + 20].

Algorithm 1 :

 1 RepresentInteger ′ R+Rj (N, A, B) Input: An integer N and A, B ∈ R Output: C, D ∈ R such that: i) (n(C + Dj), N ) = 1 and n(C + Dj) is powersmooth; ii) (n(C), N ) = 1; iii) (n(D), N ) = 1; iv) (N, ImR(A BC D)) = 1 and v) q(4p 2 n(ABCD) -(n(AC) -pn(AD)) 2) is a square modulo N .

Lemma 5. 5 .

 5 Consider a linear equation N 1 x+N 2 y = N 3 mod N where gcd(N, N 1 ) = d 1 , gcd(N, N 2 ) = d 2 and (d 1 , d 2 ) = 1. Then this equation has N solutions in (Z/N Z) 2 .

13

  Go back toStep 10 14 a, b = Cornacchia(M ). 15 Return λµ0 + N (a + bi + (c + di)j), λ.

  The condition n(x) = n(y) is equivalent to n(CDpx) = n(CDpy). And one could calculate explicitly thatn(CDpx) = p 2 n(A)n 2 (D)n(x 3 ) + p 2 n(B)n(C)n(D)n(x 3 ) -2p 2 n(D)Re R (A BC Dx 2 3 ), n(CDpy) = n(A)n 2 (C)n(x 3 ) + p 2 n(B)n(C)n(D)n(x 3 ) + 2pn(C)Re R (A BC Dx 2 3 ).We now aim to findx 3 = s + ti ∈ R with (n(x 3 ), N ) = 1 such that n(CDpx) -n(CDpy) = n(γ) n(A)(n(C) -pn(D)) + 2pRe R (A BC Dx 2 3 ) = 0 mod N . Plugging in x 3 = s + ti, finding x 3 is equivalent to finding (s, t) ∈ Z 2 such that f (s, t) := C 1 s 2 + C 2 st + C 3 t 2 = 0 mod N,(8)whereC 1 = n(A) n(C) -pn(D) + 2pRe R (A BC D) , C 2 = -4qp(Im R A BC D)andC 3 = qn(A) n(C) -pn(D) -2qpRe R (A BC D) .Clearly, a solution (s, t) exists if and only if the discriminant 4q(4p 2 n(ABCD) -(n(AC) -pn(AD)) 2 ) (9)

Algorithm 4 :

 4 QuaternionDecomposition(N,A,B,C,D)Input: N, A, B, C, D as in Problem 5.7. Output: x1, x2, x3 ∈ R such that A + Bj = λx1j(C + Dj)x2j(C + Dj)x3j mod N O0where λ is some integer that is coprime to N .1 t0 ← root of n(A) n(C) -pn(D) + 2pReR(A BC D) -4qpImR(A BC D)t + qn(A) n(C) -pn(D) -2qpReR(A BC D) t 2 = 0 mod N. 2 x3 ← 1 + t0i 3 x1, x2 ← EquivNormConjugationProduct(x3) 4 Return x1, x2, x3.

Table 1

 1

	, borrowed

Table 1 .

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

  Conversely, it is clear that any element in Z + I ϕ acts as a scalar on ker ϕ and so is part of the stabilizer. For the proof that Z + I ϕ is an Eichler order, see [DFKL + 20].

	Proposition 4.6. The stabilizer subgroups are conjugates of the subgroup of
	upper triangular matrices (i.e., a Borel subgroup).
	Proof. Follows from [Voi18, 23.1.3]. For an elementary proof see [CII + 23, Ap-
	pendix B].	⊓ ⊔
	4.2 The main reductions.

⊓ ⊔ Remark 4.5. Writing the stabilizer subgroups as Eichler orders of the form Z+I ϕ will help us prove that computing the stabilizer subgroup is essentially equivalent to finding the endomorphism ring of the codomain of ϕ (which is isomorphic to the right order of I ϕ ).

Acknowledgements Gábor Ivanyos is supported in part by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Artificial Intelligence National Laboratory Program. Péter Kutas is supported by the Hungarian Ministry of Innovation and Technology NRDI Office within

Algorithm 3: PQLP O (N, σ 0 )

Input: An odd integer N that is of size polynomial in p and has O(log log p) distinct prime factors, a maximal order O, and an element σ0 ∈ O such that (n(σ0), N ) = 1.

Problem 5.7 (Quaternion Decomposition). Let N be an odd integer, and O 0 , R be as defined in Section 5.1. Let

and (n(α 3 ), N ) = 1, then

Here n ′ α3 and n ′ γ are integers such that n ′ α3 n(α 3 ) ≡ 1 mod N and n ′ γ n(γ) ≡ 1 mod N respectively. We then search for solutions α 1 , α 2 , α 3 ∈ Rj for Equation (5) with (n(α 3 ), 1) = 1 instead.

Let us write α i 's as x i j with x i 's being unknowns that we wish to find in R, writing Equation (5) in terms of A, B, C, D, x 1 , x 2 and x 3 gives rise to the following:

Therefore, in order to solve the original equation, it suffices to find x 1 , x 2 , x 3 ∈ R with (n(x 3 ), N ) = 1 such that pA Dx 3 -pB C x3 = p Cx 1 x2 mod N R, ACx 3 + pBDx 3 = p Dx 1 x 2 mod N R.

(6)