Alexandre Gélin
email: alexandre.gelin@lip6.fr

Benjamin Wesolowski
email: benjamin.wesolowski@epfl.ch

Loop-abort faults on supersingular isogeny cryptosystems

Keywords: Supersingular isogeny cryptosystem, fault injection, real-world attacks, post-quantum cryptography

Cryptographic schemes based on supersingular isogenies have become an active area of research in the field of post-quantum cryptography. We investigate the resistance of these cryptosystems to fault injection attacks. It appears that the iterative structure of the secret isogeny computation renders these schemes vulnerable to loop-abort attacks. Loop-abort faults allow to perform a full key recovery, bypassing all the previously introduced validation methods. Therefore implementing additional countermeasures seems unavoidable for applications where physical attacks are relevant.

Introduction

Public-key cryptography, the foundation of modern communication security, is confronted to the prospect of a technology capable of breaking today's most widely deployed primitives: quantum computers of sufficient scale to run Shor's algorithm [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]. This risk has given rise to the field of post-quantum cryptography (PQC), which aims at developing new primitives that would resist cryptanalysis by both classical and quantum computers.

Cryptographic schemes based on supersingular elliptic curve isogenies were introduced in [START_REF] Charles | Cryptographic hash functions from expander graphs[END_REF] which proposed the hardness of path-finding in supersingular isogeny graphs and gave an application to cryptographic hash functions. It has since been used as an assumption for other cryptographic systems such as key-exchange, encryption, and signatures [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF]. Several other primitives have subsequently been built based on supersingular isogeny problems, such as zeroknowledge proofs of identity and signatures [START_REF] De Feo | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF][START_REF] Galbraith | Signature schemes based on supersingular isogeny problems[END_REF][START_REF] Jao | Isogeny-based quantum-resistant undeniable signatures[END_REF][START_REF] Sun | Toward quantum-resistant strong designated verifier signature from isogenies[END_REF]. Efficient implementations of these primitives have rapidly followed: in software [START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF][START_REF]Microsoft Security and Cryptography[END_REF], in hardware [START_REF] Koziel | Post-quantum cryptography on FPGA based on isogenies on elliptic curves[END_REF] and on embedded systems [START_REF] Azarderakhsh | NEON-SIDH: Efficient implementation of supersingular isogeny Diffe-Hellman key-exchange protocol on ARM[END_REF].

Even though the basic version of the key exchange protocol uses ephemeral secret values (as with classical Diffie-Hellman), some of these other schemes require static secret keys for at least one party. Such static secrets constitute primary material for active attacks, and such an attack was indeed described in [START_REF] Galbraith | On the security of supersingular isogeny cryptosystems[END_REF] that allows to find all n bits of the secret key with about n interactions with the victim. This attack can be prevented by the Kirkwood et al. [START_REF] Kirkwood | Failure is not an option: Standardization issues for post-quantum key agreement on the security of supersingular isogeny cryptosystems[END_REF] validation method -which is essentially a Fujisaki-Okamoto transform [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF] applied in the context of supersingular isogenies.

The results of [START_REF] Azarderakhsh | NEON-SIDH: Efficient implementation of supersingular isogeny Diffe-Hellman key-exchange protocol on ARM[END_REF], together with the fact that primitives based on supersingular isogenies enjoy significantly smaller keys than the other main candidates for post-quantum cryptography, suggest that they might be well-suited for use on embedded devices. This opens new avenues of potential side-channel attacks.

In this paper, we present the first side-channel attack against supersingular isogeny-based primitives, exploiting a fault-injection technique known as loop-abort fault injection, previously introduced for pairing based cryptography [START_REF] Page | A fault attack on pairing-based cryptography[END_REF]. The iterative structure of isogeny computations render them susceptible to loop-abort fault attacks, allowing an attacker to recover all n bits of the key, within O(n) interactions with the token and a negligible amount of computation. This attack is not prevented by any of the validation methods previously discussed for isogeny-based cryptosystems. Loop-abort fault injections were proven to be feasible in practice [START_REF] Blömer | A practical second-order fault attack against a real-world pairing implementation[END_REF], and should therefore be taken into serious consideration when implementing schemes based on supersingular isogenies in a context susceptible to physical attacks.

After a brief overview of supersingular isogeny-based cryptography in Section 2, we quickly discuss fault injection attacks in Section 3, with a particular focus on loop-abort faults. The attack is then described and analyzed in Section 4, while potential countermeasures are discussed in Section 5.

Cryptosystems from supersingular isogenies

This section recalls the necessary background and the cryptosystems based on supersingular elliptic curve isogenies introduced in [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF] and [START_REF] De Feo | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF].

Elliptic curves and isogenies

For any prime power q = p r , let F q denote the finite field with q elements. Let E be an elliptic curve defined over F q . The set E(F q ) of rational points over the algebraic closure forms a group, in which the subset E(F q ) of F q -rational points forms a finite subgroup. Let E be another elliptic curve defined over F q . An isogeny E → E is a non-constant morphism sending the identity of E to the identity of E (we then say that E is isogenous to E). In particular, an isogeny is a surjective group homomorphism from E(F q ) to E (F q ), of finite kernel. All isogenies that we consider in this paper are separable [START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF]Definition p.21], so by isogeny we always mean separable isogeny. Then, the degree of an isogeny is simply defined as the number of points in its kernel. For any finite subgroup G ⊂ E(F q ), there is a quotient elliptic curve E/G and the canonical projection π G : E → E/G is an isogeny of degree |G|. In fact, any isogeny arises in this form, up to an isomorphism of the target.

Elliptic curves for supersingular isogeny schemes

Fix a reference elliptic curve E 0 . In cryptographic schemes based on supersingular isogenies, the public key of Alice is, essentially, an isogenous curve E A , and its secret is the kernel G A of an isogeny ϕ A : E 0 → E A . Two things appear immediately: first, Alice needs an efficient way to represent the secret kernel. Second, given E 0 and E A , it should be difficult to find the kernel G A . The secret isogenies are simply chosen cyclic, so that the secret is a point P ∈ E 0 (F q ) generating the kernel. This means in particular that E 0 (F q ) should contain a lot of cyclic subgroups. It follows that the traditional constraint in elliptic curve cryptography that the order of E 0 (F q ) should have a large prime factor does not apply here: on the contrary, |E 0 (F q )| should be very smooth.

Let m be any positive integer; then E[m] ⊂ E(F q ) is the subgroup of mtorsion points in E(F q ). Whenever m is coprime to p, we have that E[m] is isomorphic to the group (Z/mZ) 2 . Now, fix a prime number = p, and a positive integer k. Then E[ k ] ∼ = (Z/ k Z) 2 contains k-1 ( + 1) distinct cyclic subgroups of order k . If all the points of E[ k ] are defined over F q , then the set of cyclic subgroups of order k generated by a point defined over F q is sufficiently large to constitute a space of secret keys. Typically, to build the cryptographic schemes, one needs two distinct primes A and B (one for the keys of Alice and one for the keys of Bob). Then, the reference elliptic curve E 0 should be chosen so that

E 0 (F q ) = E 0 [ n A ] ⊕ E 0 [ m B ].
This might be difficult to obtain, so one can simply require

E 0 (F q ) = E 0 [ n A ] ⊕ E 0 [ m B ] ⊕ F
, where the subgroup F contains a few other F q -rational points whose orders are coprime to A and B .

The schemes also require the reference curve E 0 to be supersingular -see [START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF]Theorem 3.1] for a few of the numerous equivalent ways to define supersingularity. The first interesting consequence is that all supersingular curves defined over F q are actually defined over F p 2 . The curve E 0 is constructed as follows. The primes A and B are fixed (typically 2 and 3), together with some exponents n and m whose size depend on the security level. Now, one can find a cofactor f coprime to A and B such that p = n A m B f ± 1 is a prime number. Bröker [START_REF] Bröker | Constructing supersingular elliptic curves[END_REF] has shown that it is easy to find an elliptic curve E 0 over 2 , and therefore we have the desired decomposition

F p 2 such that |E 0 (F p 2 )| = (p ∓ 1) 2 = ( n A m B f ) 2 . From [2, Theorem IX.20], the group E 0 (F p 2 ) is isomorphic to (Z/ n A m B f Z)
E 0 (F p 2 ) = E 0 [ n A ] ⊕ E 0 [ m B ] ⊕ F , with F = E 0 [f ]
. This choice of A , B , n, m, p and E 0 is fixed for the rest of the paper. We are working on the class of all elliptic curves E that are F p 2 -isogenous to E 0 . They are all supersingular, and by Tate's isogeny theorem [START_REF] Tate | Endomorphisms of abelian varieties over finite fields[END_REF], they all have the same number of F p 2 -rational points. It follows that any such E enjoys the same decomposition

E(F p 2 ) = E[ n A ] ⊕ E[ m B ] ⊕ F.

Computing smooth degree isogenies

Let ( , k) ∈ {( A , n), ( B , m)}. For any elliptic curve E isogenous to E 0 , the subgroup E[ k ] ⊂ E(F p 2
) is a free Z/ k Z-module of rank two, with a basis {P, Q}. Any point R = c 1 P + c 2 Q has order k if and only if either c 1 or c 2 is not divisible by . Any such point R of order k induces an isogeny ϕ R : E → E/ R of degree k . As described in [7, Section 4.2.2], the only efficient way to compute the isogeny ϕ R is as a sequence of k isogenies of degree , which can themselves be computed using Vélu's formulas [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF]. We now recall that method. Set E 0 = E, R 0 = R, and for 0 ≤ i < k, recursively define

E i+1 = E i / k-i-1 R i , ϕ i+1 : E i → E i+1 the canonical isogeny, R i+1 = ϕ i+1 (R i ).
Then,

E/ R = E k , each isogeny ϕ i is of degree , and ϕ R = ϕ k • • • • • ϕ 1 .
From this observation, [7, Section 4.2.2] describes a family of strategies to compute ϕ R . These strategies allow to optimize the number of point multiplications and isogeny computations, but all boil down to computing the sequence of isogenies (ϕ i ) k i=1 in order.

Jao-De Feo protocols

We present here two examples of cryptographic protocols based on supersingular isogenies: a key exchange protocol, and a public key encryption protocol. Our attack could easily be adapted to other variants of isogeny-based schemes as we target a component they all have in common: the computation by Alice of a secret isogeny.

Key exchange. The following key exchange protocol is the first supersingular isogeny-based protocol, introduced in [12, Section 3.1].

Setup Choose a prime p = n A m B f ± 1 and an elliptic curve E 0 as in Section 2.2.

As E 0 [ n A ] is a free Z/ n A Z-module of rank two, let {P A , Q A } be a basis 3 . Similarly, let {P B , Q B } be a basis of E 0 [ m B ]. Key exchange Alice chooses two random elements a 1 , a 2 ∈ Z/ n A Z, not both nilpotent 4 , and Bob does the same, with b 1 , b 2 ∈ Z/ m B Z. Let R A = a 1 P A + a 2 Q A , R B = b 1 P B + b 2 Q B . Write E A = E 0 / R A and E B = E 0 / R B ,
(P A ), ϕ B (Q A )).
Alice can compute the j-invariant of

E AB = E B / a 1 ϕ B (P A ) + a 2 ϕ B (Q A ) ,
while Bob can compute the j-invariant of

E BA = E A / b 1 ϕ A (P B ) + b 2 ϕ A (Q B )
.

Fortunately E AB ∼ = E 0 / R A , R B ∼ = E BA , so j(E AB ) = j(E BA )
is the secret shared by Alice and Bob, from which they can derive a secret key.

Public-key encryption. The public-key encryption scheme described in [12, Section 3.2] is very similar to the key exchange. Here, Bob sends an encrypted message to Alice.

Setup As for the key exchange, choose a prime p = n A m B f ± 1 and an elliptic curve E 0 , together with bases

{P A , Q A } for E 0 [ n A ] and {P B , Q B } for E 0 [ m B ]. Let H = {H k | k ∈ K}
be a family of hash functions indexed by a finite set K, where each H k is a function from F p 2 to the message space {0, 1} w . Key generation Choose two random elements a 1 , a 2 ∈ Z/ n A Z, not both nilpotent. Let

E A = E 0 / a 1 P A + a 2 Q A ,
and ϕ A : E 0 → E A the canonical isogeny. Choose a random element k ∈ K.

The public key is (E A , ϕ A (P B ), ϕ A (Q B ), k), and the private key is (a 1 , a 2 , k). Encryption Given a public key (E A , ϕ

A (P B ), ϕ A (Q B ), k) and a message m ∈ {0, 1} w , choose two random elements b 1 , b 2 ∈ Z/ m B Z, not both nilpotent. Fix E B = E 0 / b 1 P B + b 2 Q B ,
and ϕ B : E 0 → E B the canonical isogeny, and let

E BA = E A / b 1 ϕ A (P B ) + b 2 ϕ A (Q B ) . Compute the hash value h = H k (j(E BA )) and c = h ⊕ m. The ciphertext is (E B , ϕ B (P A ), ϕ B (Q A ), c). Decryption Given the ciphertext (E B , ϕ B (P A ), ϕ B (Q A ), c), compute E AB = E B / a 1 ϕ B (P A ) + a 2 ϕ B (Q A ) . Let m = H k (j(E AB )) ⊕ c. Since j(E AB ) = j(E BA ), m is the plaintext. Remark 1.
Observe that Alice's private key (a 1 , a 2 ) is equivalent to (ra 1 , ra 2 ) for any r coprime to A , since

a 1 P A + a 2 Q A and ra 1 P A + ra 2 Q A generate the same subgroup of E 0 [ n A ].
Recall that a 1 and a 2 are not both nilpotent. Seen as integers, this means that one of them is not divisible by A , so is invertible in Z/ n A Z. Therefore (a 1 , a 2 ) is equivalent to either (1, a) (if a 1 is coprime to A ) or to (a, 1) (if a 2 is coprime to A ).

Validation methods against active attacks

Various validation methods have been introduced in order to prevent active attacks against isogeny-based protocols. Classical methods allowing to check if an elliptic curve is supersingular, or if two given points P and Q lie on the curve, have the correct order and are independent are discussed in [START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF]. In [10, Section 2.4], some validation steps are simplified, and a new one is introduced that allows Alice to gain some assurance that the two points of Bob's public-key are the images of the two base points P A , Q A through an isogeny of degree m B . The active attack of [START_REF] Galbraith | On the security of supersingular isogeny cryptosystems[END_REF] allows a dishonest party to send malicious points to Alice that nevertheless pass all these validations.

The only effective countermeasure that has been proposed to prevent this attack against the key exchange protocol is to apply the Fujisaki-Okamoto transform [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF], as explained in [START_REF] Peikert | Lattice cryptography for the internet[END_REF], which in the context of the isogeny key exchange has been discussed by Kirkwood et al. [14]. This validation method essentially forces Bob to send to Alice honestly generated parameters, and to prove that he has been able to compute the shared secret. More precisely, the following describes the key exchange protocol resulting from applying the Fujisaki-Okamoto transform. Here, Alice has a static secret key (a 1 , a 2 ), and Bob -the potential adversary -generates an ephemeral key. In the fault injection attack we describe, Bob forces Alice to compute a wrong isogeny. By predicting the output of this wrong isogeny, Bob can make sure the fault is not detected by the validation, and Alice leaks some faulted information.

Fault injection attacks

Fault injection attacks are a standard kind of attacks assuming physical access to a device (Alice) using a static private key (in the present context, a pair (a 1 , a 2 )). They rely on the ability of the attacking party to tamper with Alice's execution of the protocol, causing her to commit errors in her computations. For the rest of the paper, we fix A = 2 and B = 3 for simplicity, but the results can easily be applied to any A and B .

Tampering with bits and bytes

The secret key is a pair of integers a 1 , a 2 ∈ {1, ..., 2 n -1}, such that the kernel of the secret isogeny is R A = a 1 P A + a 2 Q A . If it is possible to force a particular bit of (a 1 , a 2 ) to, say, 0, then the value of that bit can be recovered by checking if the faulty outcome is valid. A folklore way to make this kind of attack ineffective is to regularly randomize the representation of the secret key. In the present context, this could be done by choosing a random odd integer r each time the private key is used, and to replace (a 1 , a 2 ) by the equivalent pair (ra 1 , ra 2 ).

There exist mostly three ways to alter the value of a bit during execution: forcing it to 0 or 1, flipping it, or randomizing it. The simple attack above assumes that a bit can be forced to some value, but the weakest of these three assumptions is obviously the bit randomization. Under this assumption, a particular bit can be made to take a random value among 0 or 1, unknown from the attacker. This cannot be exploited in such a straightforward way as the bit-forcing assumption, but suffices for the more elaborate attack we present.

Targeting a particular bit might turn out to be difficult. Rather than a precise bit error, one could aim for a byte error (or a word error): a fault is injected in a byte, and the new value of the byte cannot be predicted by the attacker.

Implementing loop-aborts

A powerful way to exploit fault injections is to implement loop aborts. The weakest of the above assumptions are sufficient to force a loop to come to an end. Loop-abort faults have been introduced by Page and Vercauteren in the context of pairing based cryptography [START_REF] Page | A fault attack on pairing-based cryptography[END_REF], and recently used by Espitau et al. [START_REF] Espitau | Loop-abort faults on latticebased Fiat-Shamir and hash-and-sign signatures[END_REF] to attack signature schemes based on lattices. It is explained in [8, Section 5] that a loop-abort can simply be implemented by injecting a random fault on the loop counter -or alternatively, by skipping the jump instruction. Loop-abort faults appear to be feasible in practice, and have already been successfully performed in attacks against pairing based cryptography by Blömer et al. [START_REF] Blömer | A practical second-order fault attack against a real-world pairing implementation[END_REF].

As any fault attack, it requires some knowledge on the structure of the implementation being targeted, to know precisely at which place and time the fault should be injected. Such structure can be recovered by combining some knowledge of the algorithms involved (and maybe of standard implementations), reverse-engineering techniques and side-channel analysis. Then, a few circumstances make loop-abort attacks easier. First, most of the possible values of the loop-counter would cause the loop to abort, so it is not necessary to target a specific bit: some imprecise randomizations should do the trick. Second, to exit the loop after k iterations, it is sufficient to tamper with the counter at any time during the execution of the k-th iteration. With that strategy, if an iteration takes time to execute, the timing of the fault injection need not be excessively precise.

The loop-abort fault attack

This attack takes advantage of the iterative structure of the isogeny computation, as described in Section 2.3. The critical point is Alice's computation of an isogeny E → E/ a 1 R + a 2 S based on her secret. One can inject a fault to cause Alice to compute this isogeny only partially, leaking information about the secret key (a 1 , a 2 ).

Attack framework

Alice takes as input the public parameters of a party who wants to initiate a secure communication, and performs her side of the protocol using a static private key (a 1 , a 2 ). We assume that the countermeasures discussed in [START_REF] Galbraith | On the security of supersingular isogeny cryptosystems[END_REF] are implemented, and in particular the Kirkwood et al. validation method [START_REF] Kirkwood | Failure is not an option: Standardization issues for post-quantum key agreement on the security of supersingular isogeny cryptosystems[END_REF], which essentially prevents attacks based on tricking Alice into computing on maliciously cooked data. Then, Alice is modeled in the form of an oracle

O(E, R, S, E , b 1 , b 2 ) which returns 1 if j(E ) = j(E/ a 1 R + a 2 S ), j(E) = j(E 0 / b 1 P B + b 2 Q B ) and (R, S) = (ϕ B (P A ), ϕ B (Q A ))
and 0 otherwise. The first condition corresponds, as in the second oracle of [10, Section 3], to Alice taking Bob's protocol message, performing her side of the protocol, and returning an error if the shared key she finds does not coincide with Bob's. The second and third conditions account for the Kirkwood et al. [START_REF] Kirkwood | Failure is not an option: Standardization issues for post-quantum key agreement on the security of supersingular isogeny cryptosystems[END_REF] validation method: Bob can only use honestly generated parameters.

We further assume, and it is the foundation of our attack, that the attacker can make Alice abort the main loop after the k-th iteration during her computation of the isogeny E → E/ a 1 R+a 2 S , using techniques discussed in Section 3.2. As described in Section 2.3, recall that after k iterations, Alice has computed the intermediate elliptic curve

E k ∼ = E/ 2 n-k (a 1 R + a 2 S)
The fault injection is modeled by the oracle

O k (E, R, S, E , b 1 , b 2 ), that returns 1 if j(E ) = j(E k ), j(E) = j(E 0 / b 1 P B +b 2 Q B ) and (R, S) = (ϕ B (P A ), ϕ B (Q A ))
, and 0 otherwise.

The attack

Alice's key (a 1 , a 2 ) is either equivalent to (1, a) (if a 1 is odd) or (a, 1) (if a 2 is odd), and the attacker recover one by one the bits of a from the least significant to the most significant 5 . The attacker, playing the role of Bob, chooses a (random) secret key (b 1 , b 2 ) ∈ {1, • • • , 3 m } 2 that he is going to use for the attack. He computes E B = E 0 / b 1 P B + b 2 Q B and lets ϕ B : E 0 → E B be the canonical isogeny. Also write P A = ϕ B (P A ) and Q A = ϕ B (Q A ). First, the attacker needs to decide whether the key can be represented as (1, a) or (a, 1). We have

E 1 B ∼ = E B / 2 n-1 (a 1 P A + a 2 Q A ) = E B / (2 n-1 a 1 mod 2 n )P A + (2 n-1 a 2 mod 2 n )Q A ) .
Therefore a 1 is even if and only if the first isogeny

E B → E 1 B has kernel 2 n-1 Q A ⊂ E[2]
. This can be decided by determining the kernel κ ⊂ E B [START_REF] Blake | Advances in Elliptic Curve Cryptography[END_REF] of the first isogeny computed by Alice. The attacker guesses one of the three possible proper subgroups κ ⊂ E B [START_REF] Blake | Advances in Elliptic Curve Cryptography[END_REF], and queries the oracle

O 1 on the input (E B , ϕ B (P A ), ϕ B (Q A ), E B /κ, b 1 , b 2 )
. If the output is 1, then the guess of κ was correct. If the output is 0, either the guess is incorrect or the fault injection failed. This allows simultaneously to determine if the key can be represented as (1, a) or (a, 1), and to determine the least significant bit of a. More precisely,

if κ = 2 n-1 Q A then a 1 is
even and a 2 is odd, so the key can be represented as (a, 1), and the least significant bit of a is 0. if κ = 2 n-1 P A then a 2 is even and a 1 is odd, so the key can be represented as (1, a), and the least significant bit of a is 0. if κ = 2 n-1 (P A + Q A ) then both a 1 and a 2 are odd, so the key can be represented as (1, a), and the least significant bit of a is 1.

In the following, we assume without loss of generality that the key is represented as (1, a). Now, it remains to recover all the other bits of a, from the least significant to the most significant. In order to match the structure of the attack, the bits of a are indexed from the least significant to the most significant. Observe that

E k B ∼ = E B / 2 n-k (P A + aQ A ) = E B / 2 n-k P A + (2 n-k a mod 2 n )Q A )
only depends on the k least significant bits of a. If we know the first k -1 bits of the key, we can guess the k-th one and compute the corresponding degree-k isogeny. Then, it suffices to compare the result with the faulty outcome to determine if the guess is correct. More precisely, at the k-th step, once the k -1 first bits of the key a have already been recovered, we perform the following steps:

1. Choose a guess b ∈ {0, 1}; 2. Compute Ẽk B = E B / 2 n-k P A + ã2 n-k Q A ) where ã = b•2 k-1 +(a mod 2 k-1
) is the concatenation of b with the first k -1 bits of a; Assuming that the fault injection is a success (i.e., the oracle O k is called successfully), it is clear that the oracle returns 1 only if Ẽk B is indeed the k-th elliptic curve in the sequence of isogenies that Alice should have computed, meaning that b is a correct guess of the k-th bit of a.

Analysis of the attack

Let µ denote the probability of successfully aborting the computation 6 . The attack above requires about 2n/µ ≈ log 2 p/µ fault injections, and as many interactions with Alice7 . Considering that Alice is modeled as an oracle that outputs only one bit, O (n) is optimal in the sense that we cannot hope to recover more than one bit of the key per interaction. The additional factor µ accounts for the potential difficulty of injecting faults. In Section 4.4, we describe a way to reduce the number of faults, assuming a stronger oracle which leaks more information.

To abort after k iterations, the fault must be injected during the execution of the k-th iteration. All known implementations of the isogeny computation share the same iterative structure, however the duration of an iteration is not necessarily a constant, and depends on the choice of a strategy -in the sense of [START_REF] De Feo | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF]Section 4.2.2]. For instance, in the SIDH Library [START_REF]Microsoft Security and Cryptography[END_REF], the first iteration is the longest, taking about 4.0 • 10 6 CPU cycles (measured on an Intel(R) Core(TM) i7-4710MQ CPU @ 2.50GHz), while the other iterations take between 7.9 • 10 4 and 1.8 • 10 6 CPU cycles. Finding the right moment to inject the fault can be easy if Alice is using a public implementation [START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF], and otherwise requires to reverse-engineer the strategy by side-channel analysis.

This attack is the first one against isogeny-based schemes that bypasses the costly Kirkwood et al. validation method [START_REF] Kirkwood | Failure is not an option: Standardization issues for post-quantum key agreement on the security of supersingular isogeny cryptosystems[END_REF]. In essence, this validation method checks these two statements: first, Bob's parameters are honestly generated (and in our attack, they indeed are), and Bob knows the shared key computed by Alice (this is precisely the guess Ẽk B , which has a probability 1/2 of being correct).

Alternative with less faults but stronger oracle

Instead of the weak oracle we have considered so far, which outputs a single bit at each call, one could also consider a more powerful oracle, closer to the first oracle of [10, Section 3] (but still weaker). Let H be a function with very rare collisions (it could be the identity, or a hash function), and consider the oracle

O(E, R, S, b 1 , b 2 ) which outputs H(j(E/ a 1 R + a 2 S )) if j(E) = j(E 0 / b 1 P B + b 2 Q B ) and (R, S) = (ϕ B (P A ), ϕ B (Q A ))
, and 0 otherwise. We can then hope to reduce the number of faults necessary for the attack, at the cost of additional computations.

As previously, we also define the oracle O k (E, R, S, b 1 , b 2 ) which outputs

H(j(E/ 2 n-k (a 1 R + a 2 S) )) if j(E) = j(E 0 / b 1 P B + b 2 Q B ) and (R, S) = (ϕ B (P A ), ϕ B (Q A )),
(P A ), ϕ B (Q A ), b 1 , b 2 )
, and call the output h. Find by exhaustive search the value x ∈ {0, 1, . . . , 2 s -1} such that h = H(E B / 2 n-s (P A + xQ A ) ). Unless a collision occurred in H, this x is exactly a mod 2 s , corresponding to the s least significant bits of a. Generalizing this to the other bits is straightforward. The time complexity to find a batch of s bits clearly grows as O(2 s ).

Note that the Kirkwood et al. validation method prevents this trade-off: Alice always terminates in a non-accepting state unless Bob is able to guess in advance the value j( ẼAB ) of the (faulty) shared secret computed by Alice, bringing the probability of successfully recovering the s bits down to µ/2 s . This trade-off can be analyzed by simulating the attack in software, based on the open-source implementation of [START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF][START_REF]Microsoft Security and Cryptography[END_REF]. The loop-abort is simulated by adding a break instruction at the appropriate moment. We use the default parameters that are provided, that is the curve E : y 2 = x 3 + x defined over F p , for p = 2 372 3 239 -1, claimed to offer 186 bits of classical security.

Timings for various batch sizes (i.e., s in the above description) are provided in Table 1. The sizes are even because the implementation of [START_REF]Microsoft Security and Cryptography[END_REF] computes 4-isogenies instead of 2-isogenies, so the bits have to be considered by pairs. Table 1. Time of the computations depending on the size of the batches. The tests were run on an Intel(R) Core(TM) i7-4710MQ CPU @ 2.50GHz.

Countermeasures and conclusion

Previously introduced validation methods are not sufficient to prevent the fault injection attack we have presented. To patch this vulnerability, it is necessary to implement new countermeasures when such a physical attack is relevant. A few generic countermeasures have already been discussed in [START_REF] Espitau | Loop-abort faults on latticebased Fiat-Shamir and hash-and-sign signatures[END_REF]. First, simply checking after the loop if the value of the counter is exactly the expected number of iterations provides a first protection against attackers who cannot inject faults with a sufficiently high precision (for instance, attackers who can only inject random errors in a memory word). This countermeasure can be strengthened further by adding an additional (or multiple) parallel counter, and checking that both counters have the expected final value. This protects against single faults, and to some extent, against random faults.

These countermeasures are very cheap and easy to implement, as they are not related to the underlying mathematical structures but are simply meant to check that the loop completed the correct number of iterations.

for a even has order 2 k . Caution is required when applying to P and Q results that are meant to be applied to a basis of E [2 k ]. It appears for instance in [START_REF] Galbraith | On the security of supersingular isogeny cryptosystems[END_REF]Lemma 3.2], where the factor 2 k-1 should be replaced by 2 k-2 when using this pair (P, Q).

Also, if a is generated following the guidelines of [START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF] (as a = 2m for m ∈ {1, 2, . . . , 2 k-1 }), then its most significant bit is superfluous. Indeed, the kernel of the first isogeny is necessarily the group generated by [2 k-1 ]P = -[2 k-1 ]Q. Then, the image of P + [a]Q under this isogeny is the same as the image of P + [a + 2 k-1 ]Q. It follows that the secret a leads to the same shared secret as its reduction a mod 2 k-1 . Therefore the secret a = 2m could be chosen with m < 2 k-2 .

  Bob's key generation Bob chooses a random seed r, from which he derives his secret key (b 1 , b 2 ) = f (r) via a pseudo-random function f . He proceeds to compute his message (E B , ϕ B (P A ), ϕ B (Q A )) as in the regular key exchange. He computes the shared secret E AB using Alice's public key (E A , ϕ A (P B ), ϕ A (Q B )), and derives a session key sk and a validation key vk via a key derivation function (KDF), as (sk, vk) = KDF(j(E AB )). Key exchange Bob sends the tuple (E B , ϕ B (P A ), ϕ B (Q A )) and the ciphertext c = Enc vk (r ⊕ sk) to Alice. Validation Alice first derives E AB , then sk and vk , to recover the value r = Dec vk (c) ⊕ sk . From this hypothetical seed r , she is able to recompute Bob's operations. If the result she finds coincides with the tuple (E B , ϕ B (P A ), ϕ B (Q A )) she has received, she terminates the protocol by accepting sk = sk as the shared secret. Otherwise, she returns an error.

3 .

 3 Query the oracle O k on E B , P A , Q A , Ẽk B , b 1 , b 2 ; 4. If the oracle returns 1 (i.e. it does not detect an error), then the k-th bit is b; otherwise, either the bit is 1 -b, or the fault injection failed.

  seconds) 7.13 9.6 21.1 65.3 201 681 2389 7946 22809 84763 number of faults 185 93 62 47 37 31 27 24 21 19

  and let ϕ A : E 0 → E A and ϕ B : E 0 → E B denote the canonical isogenies. Alice computes and publishes (E A , ϕ A (P B ), ϕ A (Q B )), and Bob does the same for (E B , ϕ B

  and 0 otherwise. The idea is to consider batches of s > 1 bits instead of recovering one bit at a time, thereby reducing the required number of faults from n to n s . As in the attack of Section 4.2, the attacker generates parameters b 1 , b 2 , E B and ϕ B . Assuming the key is represented as (1, a), the s least significant bits of a can be recovered as follows: call the oracle O s (E B , ϕ B

In[START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF], the pair (PA, QA) does not form a basis. The protocol still works, but some caution is required (see Appendix A).

Note that an element a ∈ Z/ n A Z is nilpotent if and only if it is the class of a multiple of A.

Note the contrast with the simple attack of Section 3.1, in which the way Alice internally represents her secret key is crucial. In this more evolved attack, Alice's representation is irrelevant.

For simplicity, we assume that this probability is independent of the number k of iterations after which we want to abort.

More precisely, if there exists a way to determine that a fault was successful (for instance, if µ = 1), we can get rid of the factor 2, because a failure brings the information that the guess is wrong, so the bit is 1 -b.

Acknowledgements

This work has been supported in part by the European Union's H2020 Programme under grant agreement number ERC-669891. The second author was supported by the Swiss National Science Foundation under grant number 200021-156420.

A When P and Q are not a basis of the torsion

The implementation proposed by [START_REF] Costello | Efficient algorithms for supersingular isogeny Diffie-Hellman[END_REF][START_REF]Microsoft Security and Cryptography[END_REF] uses a pair of points P and Q in E[ k ] that does not generate the full group E[ k ], in order to achieve better compression. The point P is chosen to be a point of order k , and Q is set as the image of P by the distortion map (x, y) → (-x, iy) (where i 2 = -1).

They prove that because of this construction, when = 2, the sum P + Q has order 2 k-1 (instead of the expected 2 k ). Thus every point of the form P + [a]Q


Alexandre G Élin
email: alexandre.gelin@lip6.fr

AND Thorsten Kleinjung

Arjen K Lenstra

PARAMETRIZATIONS FOR FAMILIES OF ECM-FRIENDLY CURVES

We provide a new family of elliptic curves that results in a one to two percent performance improvement of the elliptic curve integer factorization method. The speedup is confirmed by extensive tests for factors ranging from 15 to 63 bits.

Introduction

The elliptic curve method (ECM) for integer factorization was introduced by H.W. Lenstra in 1985 and published two years later in [START_REF] Lenstra | Factoring integers with elliptic curves[END_REF]. It is the asymptotically fastest method that has been published for finding relatively small factors of large composites. Although the number field sieve [START_REF] Arjen | The development of the number field sieve[END_REF] is the most efficient general algorithm for integer factorization, there are two common use cases for ECM: it is widely used in attempts to find factors of large composites for which no information is available about the sizes of the prime factors (R. Propper found the largest ECM factor so far, a 274-bit factor of 7 337 + 1) and it is used for the so-called cofactoring step of the number field sieve (where many relatively small composites have to be factored).

Given an odd composite integer N to be factored, ECM performs arithmetic operations on elliptic curves considered to be defined over the finite field F p of cardinality p, for an unknown prime divisor p of N . It may find p if the cardinality of at least one of these curves over F p is smooth. For this reason, curves are used that are known to have favorable smoothness properties, such as a large torsion group over Q or a cardinality that is divisible by a fixed factor. Constructions of ECM-friendly curves were published by Suyama [11] (with a slight improvement by Montgomery in [START_REF] Peter | Speeding the Pollard and elliptic curve methods of factorization[END_REF]Section 10.3.2]), Atkin-Morain [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF], and generalized by Bernstein et al. in [START_REF] Daniel | Starfish on strike[END_REF].

Originally formulated in [START_REF] Lenstra | Factoring integers with elliptic curves[END_REF] using Weierstrass curves, until around 2008 implementations of ECM mostly used Montgomery's approach from [START_REF] Peter | Speeding the Pollard and elliptic curve methods of factorization[END_REF]. With the introduction of Edwards curves [START_REF] Harold | A normal form for elliptic curves[END_REF], a number of follow-up papers by Bernstein et al. [START_REF] Daniel | Twisted Edwards curves[END_REF][START_REF] Daniel | ECM using Edwards curves[END_REF] ultimately led to "a = -1 twisted Edwards" curves by Hisil et al. [START_REF] Hisil | Twisted Edwards curves revisited[END_REF] with torsion group isomorphic to Z/2Z×Z/4Z as one of the current most efficient ways to implement ECM, as shown by Bernstein et al. in [START_REF] Daniel | Starfish on strike[END_REF]. For these curves, Barbulescu et al. in [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] identify three families that all have the same larger smoothness probability and an even better fourth family. In [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] a parametrization is provided for one of the three equivalent families; the others are only illustrated by -a finite set ofsmall values found by enumeration. In particular a parametrization of the fourth and best family, which could lead to a better choice of curves for ECM, has so far not been published. By parametrization we mean that an elliptic curve along with a non-torsion point is determined as a function of some parameter: in this paper the parameter may be a point on some other elliptic curve or a rational number, thus giving rise to elliptic and rational parametrizations.

After a brief history in Section 2 on the use of Edwards curves in ECM, we present in Section 3 parametrizations for all families from [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] that remained to be parameterized. In Section 4 we compare our new curves to the ones used so far, observing that the curves derived from a same parametrization have similar behavior and that the fourth and best family indeed seems to lead to the best performance known for ECM. The resulting speed up is modest but worthwhile: given how much computing time is invested in ECM, the resulting practical savings could be considerable.

Edwards curves and elliptic curve method

Twisted Edwards curves. Let K be a field of characteristic different from 2. Edwards curves are defined in [START_REF] Harold | A normal form for elliptic curves[END_REF] by equations of the form x 2 + y 2 = 1 + dx 2 y 2 , for d ∈ K with d(d -1) = 0. To enlarge the set of curves, the equation was generalized in [START_REF] Daniel | Twisted Edwards curves[END_REF] to twisted Edwards curves ax 2 + y 2 = 1 + dx 2 y 2 for a, d ∈ K with ad(a -d) = 0. Because of the favorable properties of the arithmetic in the curve group (speed and no exception for doubling) twisted Edwards curves gained interest in applications.

Torsion group. For each curve, stage 1 of ECM attempts to compute a scalar multiple of some initial point on the curve, for a scalar equal to the product of all prime powers up to some bound and where the computation is done modulo N . If the order of the initial point happens to be smooth modulo at least one but not all prime factors of N , an inversion failure modulo N reveals a factor of N . Because the torsion group E tors of the curve over Q injects in the curve modulo each prime that has good reduction, in ECM it helps to choose curves that have a large E tors . The largest gain that can be obtained in this manner is modest, because according to Mazur's theorem E tors is isomorphic to

Z/nZ with 1 ≤ n ≤ 10 or n = 12, or Z/2Z × Z/2nZ with 1 ≤ n ≤ 4.
The two most profitable possibilities, Z/12Z and Z/2Z × Z/8Z, are characterized for families of Edwards curves in [START_REF] Daniel | ECM using Edwards curves[END_REF]Section 6]. On the other hand, the fastest scalar multiplication is obtained in [START_REF] Hisil | Twisted Edwards curves revisited[END_REF] for a = -1 twisted Edward curves; as shown in [START_REF] Daniel | ECM using Edwards curves[END_REF], however, this limits the possibilities for interesting torsion groups (i.e., with cardinality greater than four) to Z/6Z, Z/8Z or Z/2Z × Z/4Z, thereby in particular excluding the two most profitable ones. For ECM the issue was settled in [START_REF] Daniel | Starfish on strike[END_REF] where a = -1 twisted Edwards curves were compared to curves with E tors isomorphic to Z/12Z and Z/2Z × Z/8Z: it was found that the disadvantage of the formers' smaller torsion groups is outweighed by their faster scalar multiplication.

Curves with on average higher torsion modulo p. Barbulescu et al. in [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] further develop a = -1 twisted Edwards curves with torsion group isomorphic to Z/2Z × Z/4Z. In [START_REF] Daniel | Starfish on strike[END_REF] these are shown to be the curves -x 2 + y 2 = 1 -e 4 x 2 y 2 with e / ∈ {0, ±1}. Compared to generic e-values and averaging over the primes p of good reduction, [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] that for the best case (family (iv)) the cardinality of the torsion group of the curve modulo p is divisible by 16, and by 32 if p ≡ 1 mod 4 and g(g -1)(g + 1) is a quadratic residue modulo p.

Usage of these curves in ECM requires an easy way to generate them, along with an appropriate initial point on each curve. Earlier and new ways to do this are discussed in the next section.

Parametrizations for curves with higher torsion modulo p

In this section we are exclusively interested in the generation of a = -1 twisted Edwards curves with torsion group isomorphic to Z/2Z × Z/4Z. The first known parametrization for the general case of such curves is the elliptic parametrization from [4, Theorem 3.3]; it generates a target curve (and a point of infinite order on it) as a function of a point on another elliptic curve of positive rank. Our goal is to find elliptic parametrizations for all four families (i)-(iv) in (2.1) and (2.2).

For family (i) this has already been done in [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF]. First a new rational parametrization for the general case was derived, i.e., a function from Q -with finitely many exceptions -to a = -1 twisted Edwards curves with torsion group isomorphic to Z/2Z × Z/4Z, along with a point of infinite order on each curve. It was then checked if a special choice of the rational parameters leads to curves with e-values as in (2.1) or (2.2). That turned out to work for family (i), but due to limitations imposed by the rational parametrization it failed for families (ii)-(iv).

In this section we review the approach from [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF], and we present the results of a search that we conducted for new rational parametrizations for the general case. The newly found rational parametrizations turn out to suffice for our purpose: following the approach from [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] it is shown that special choices of the rational parameters lead to elliptic parametrizations for all four families (i)-(iv).

General conditions. From the equation -x 2 + y 2 = 1 -e 4 x 2 y 2 with e / ∈ {0, ±1} for the general case, it follows that e and -e lead to the same curve. Considering the variable change (x, y) -→ (xe 2 , 1 y ), the curves for e and 1 e are birationally equivalent. Thus, only one element of {±e, ± 1 e } is of interest and we fix e > 1. Furthermore, as we require points of infinite order, the curves must have positive rank and easily identifiable torsion points in order to be able to avoid them. The latter can be done, because

• (0, 1) is the neutral element,

• (0, -1) and ∞, ± 1 e 2 are the three 2-torsion points, and

• (± 1 e , ± 1
e ) are the four 4-torsion points.

A point (x, y) on the curve is therefore a non-torsion point if and only if x / ∈ {0, ∞} and xe = ±1.

Earlier parametrizations. As mentioned above, the first parametrization for the general case, from [START_REF] Daniel | Starfish on strike[END_REF]Theorem 3.3], works by selecting a particular elliptic curve over Q of positive rank and by showing how a rational point on it provides an a = -1 twisted Edwards curve with torsion group isomorphic to Z/2Z × Z/4Z, along with a non-torsion point. The first rational parametrization generalizes this approach. It is [2, Theorem 3.7]:

Theorem 3.1. For nonzero t ∈ Q \ {±1, ±3 ±1 } let e 1 = 3(t 2 -1) 8t , x 1 = 1 4e 3 1 + 3e 1 = 128t 3 27t 6 + 63t 4 -63t 2 -27
and

y 1 = 9t 4 -2t 2 + 9 9t 4 -9 .
Then (x 1 , y 1 ) is a non-torsion point on the a = -1 twisted Edwards curve -x 2 +y 2 = 1 -e 4 1 x 2 y 2 with torsion group isomorphic to Z/2Z × Z/4Z. Proof. The excluded t-values imply that e / ∈ {0, ±1} and that x 1 and y 1 are welldefined. The point (x 1 , y 1 ) can be seen to be on the curve and it is a non-torsion point because x 1 / ∈ {0, ∞} and x 1 e 1 = ±1.

Compared to the parametrization from [4, Theorem 3.3], the above rational parametrization reduces the computation required for curve generation, and the simple formula for e facilitates the search for t-values that lead to an e-value that satisfies (2.1) or (2.2). It is easy to check if a rational e-value belongs to family (i) or (ii). Families (iii) and (iv) look more cumbersome, but can easily be dealt with using the following alternative characterizations.

• Because e = 2g 2 +2g+1 2g+1 if and only if 2g 2 + 2(1 -e)g + (1 -e) = 0 and because a rational g satisfying the latter polynomial exists if and only if the discriminant 4(e 2 -1) is a rational square, it follows that e = 2g 2 + 2g + 1 2g + 1 ⇐⇒ e 2 -1 is a square.

• Arguing identically (which results in discriminant 4(e 2 + 1)) it follows that x -6 the a = -1 twisted Edwards curve with torsion group isomorphic to Z/2Z × Z/4Z defined as in Theorem 3.1 belongs to family (i) and has positive rank over Q.

e = g -1 g 2 ⇐⇒ e 2 +
Proof. This follows from

e 1 = 3(t 2 -1) 8t = 9x x 2 -36 = 3x y 2
and the fact that (x 1 , y 1 ) is a non-torsion point.

Remark 3.3. Corollary 3.2 provides an elliptic parametrization for family (i). Attempting this approach for the other three families gives rise to curves of rank zero, and thus not the infinite families desired.

New rational parametrizations. To find new infinite families of curves, we rewrite the general case equation -x 2 + y 2 = 1 -e 4 x 2 y 2 as (3.1)

y 2 = 1 + x 2 1 + e 4 x 2 .
The resulting condition that the right hand side is a square is equivalent to requiring that (1 + x 2 )(1 + e 4 x 2 ) = e 4 x 4 + (1 + e 4 )x 2 + 1 is a square. With x = u v we get the equivalent condition that for the chosen values of e, u, and v the polynomial e 4 u 4 + (1 + e 4 )u 2 v 2 + v 4 must evaluate to a square.

Choosing u and v as polynomials in e, we are interested in the square-free part of the resulting polynomial in e and in e-values for which the square-free part evaluates to a rational square. A square-free part of degree higher than four corresponds to a hyperelliptic curve that is known to have a finite number of rational points; because we are interested in infinite families of curves, this case is of no interest to us.

The following search was conducted (using PARI/GP [START_REF]PARI/GP version 2.7.0[END_REF] for the polynomial factorizations):

• x = u ±1 for all integer polynomials u of degree at most two and coefficients absolutely bounded by 100, and of degree at most four and coefficients absolutely bounded by ten;

• x = u
v for all integer polynomials u, v of degree at most three and coefficients absolutely bounded by ten. The only square-free part of degree two thus found leads to the rational parametrization from Theorem 3.1. All other square-free parts have degree equal to four, and thus each corresponds to an elliptic curve. Each one that has positive rank then leads to an elliptic parametrization (i.e., curves as functions of points on some other elliptic curve), but as we set out to find rational parametrizations (i.e., curves as functions of rational numbers) this is not what we are interested in.

To address this we "manually" searched through the polynomials attempting to find commonalities among the relevant square-free parts, which ultimately resulted in parameterized infinite families of curves. Given such an infinite curve parametrization (parameterized by k in the example below), it suffices to parameterize a finite number of points per curve. Our approach essentially consists in identifying these families from the derived small values and check if they lead to good subfamilies. 16k 2 ) 2 so that for each k for which k 2 + 1 is a square, we have a point (x, y) satisfying the curve equation -x 2 + y 2 = 1 -3 4k 4 x 2 y 2 for the general case. This results in infinitely many such curves.

Using several families of degree four polynomials (and, for some, different points on the same curve), this resulted in the six additional new rational parametrizations in Theorem (3.5), the proof of which is identical to the proof of Theorem 3.1. For completeness the earlier result from Theorem 3.1 is included. Theorem 3.5. For 1 ≤ j ≤ 7 and for each nonzero t ∈ Q \ S j the point (x j , y j ) is a non-torsion point on the a = -1 twisted Edwards curve -x 2 + y 2 = 1 -e 4 j x 2 y 2 with torsion group isomorphic to Z/2Z × Z/4Z: 6 {±1, ±2, ±4}

j S j e j x j y j 1 {±1, ±3 ±1 } 3(t 2 -1) 8t 128t 3 27t 6 +63t 4 -63t 2 -27 9t 4 -2t 2 +9 9t 4 -9 2 {-2, -1, ±4} t 2 +2t+4 2t+2 2t 3 +2t 2 -8t-8 t 4 +6t 3 +12t 2 +16t 2t 5 +14t 4 +40t 3 +44t 2 +32t+16 t 6 +4t 5 +10t 4 +20t 3 +40t 2 +64t+64 3 {±2} t 2 +4 3t 12t 2 -24 t 4 -4t 2 -32 3t 6 -12t 4 +120t 2 5t 6 +12t 4 +128 4 {-2, -1, ±4} t 2 +4t t 2 -4 2t 3 +2t 2 -8t-8 t 4 +6t 3 +12t 2 +16t t 6 +6t 5 +10t 4 -16t 3 -48t 2 -32t-32 t 6 +6t 5 +10t 4 +16t 3 +48t 2 +64t 5 {±4, ±8} 4t
t 3 +8t 4t 2 +8 12t 2 +24 t 4 +4t 2 -32 4t 6 +24t 4 +192t 2 +320 5t 6 +48t 4 +96t 2 +256 7 {±2} t 3 -8t 4t 2 -8 12t 2 -24 t 4 -4t 2 -32 4t 6 -24t 4 +192t 2 -320 5t 6 -48t 4 +96t 2 -256
Imposing the aforementioned conditions to obtain all four families (i)-(iv) (as mentioned above, it suffices to test if {e, 2e, e 2 ± 1} contains a square) leads to the corollary below. For completeness it includes the result of Corollary 3.2.

Corollary 3.6. For 1 ≤ j ≤ 4 let (e j , x j , y j ) be functions of t as in Theorem 3.1. For each case below the elliptic curve E has rank one, torsion group consisting of the set T adjoined with the neutral element, and non-torsion point Q, and for each point (x, y) on E the pair (x j , y j ) is a non-torsion point on the a = -1 twisted Edwards curve -x 2 +y 2 = 1-e 4 j x 2 y 2 with torsion group isomorphic to Z/2Z×Z/4Z of positive rank and of the family listed. The last two columns list the e j -value of the first curve constructed along with the non-torsion point. Proof. With the proof of Corollary 3.2 and the characterizations given before it, the verifications in the table below suffice.

family j

(ii) 2: e 2 = t 2 +2t+4 2t+2 = x 2 +3 2x = 1 2 y x 2 (ii) 3: e 3 = t 2 +4 3t = 2x 2 +18 9x = 1 2 2y 3x 2 (iii) 3: e 2 3 -1 = x 4 -4x 3 +132x 2 -256x+4096 36y 2 = x 2 -2x+64 6y 2 (iii) 4: e 2 4 -1 = 16x 3 -192x x 4 -8x 3 -8x 2 +96x+144 = 4y 2 x 2 -4x-12 2 (iv) 4: e 2 4 + 1 = x 4 +4x 3 +14x 2 -108x+153 x 4 -4x 3 -18x 2 -16xy+12x+48y+9
Remark 3.7. Two of the curves in the e j -column of the table in Corollary 3.6 already appeared in [4, Table 3.1], namely those in the first and fourth row (though for the latter [START_REF] Daniel | Starfish on strike[END_REF] used the different non-torsion point 27 11 , 5 13 ). The search that led to Corollary 3.6 did not identify any elliptic curve of positive rank for j > 4, and no other elliptic curve of positive rank for j ≤ 4 either.

Effectiveness of the new curves

In this section we consider the effectiveness of our new curves when used in ECM and compare them to the curves proposed for ECM in [START_REF] Daniel | Starfish on strike[END_REF]. To facilitate the comparison we conduct the same tests as in [START_REF] Daniel | Starfish on strike[END_REF] and borrow some of their notation.

Earlier work. In [START_REF] Daniel | Starfish on strike[END_REF] the effectiveness of Edwards curves for ECM was investigated. For each of the five torsion groups (isomorphic to Z/6Z, Z/8Z, Z/12Z, Z/2Z × Z/4Z, and Z/2Z × Z/8Z) a set of a thousand Edwards curves was generated as described in [START_REF] Daniel | Starfish on strike[END_REF], with a = -1 when possible (i.e., for the three smallest torsion groups). For each of the 5000 resulting curves the EECM software from [START_REF] Daniel | ECM using Edwards curves[END_REF] was applied to all b-bit primes for 15 ≤ b ≤ 26 (with ECM bounds depending on the targeted b-bit prime as in [START_REF] Daniel | ECM using Edwards curves[END_REF]). For each curve and each b the number of b-bit primes found (the "yield") was tallied, with the resulting counts extensively detailed in five very informative tables. Here a prime p is said to be "found" by a curve if the cardinality of the curve over F p is smooth with respect to the ECM bounds used.

On average the curves with torsion group isomorphic to Z/6Z performed best, because of the relatively large number of primes found and because a = -1 allows fast scalar multiplication. Among these, a particularly good curve is - 5.1]. We re-derived its tallies for the C 6 -column of Table 1 (six figures of which thus already appeared in [4, Table 5.1]). Another interesting result was that among the curves with torsion group isomorphic to Z/2Z × Z/4Z four curves appeared to stand out. Indeed, these four curves happened to belong to the families with favorable Galois properties that were identified in [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF]: two of family (i) and one each of families (iii) and (iv) and in [4, Table 3.1] identified by the non-torsion points 12 91 , 27 29 , 3 14 ,1 17 , 27 11 , 5 13 , and 12 343 , 1404 1421 , respectively. The latter one "easily outperforms" the other 999 curves for b ≥ 19, the reason of which is not identified in [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] and which we now know to be due to the fact that it is of family (iv) 1 : in [4, Table 3.1] it is "best" for b = 17 and b ≥ 19 and "second best" for b = 16, 18. This curve has equation -x 2 + y 2 = 1 -77 36 4 x 2 y 2 and does not appear in our parametrization of curves of family (iv). Its re-derived tallies are listed in the C 2×4 -column of Table 1 (all figures of which except for b = 15 thus already appeared in the #1 or #2-column of [4, Table 3.1]).

x 2 + y 2 = 1 -13312 18225 x 2
Comparison to earlier work. For one hundred curves of family (iv) as parameterized in the last row of the table in Corollary 3.6 we ran the same tests as in [START_REF] Daniel | Starfish on strike[END_REF] with the same EECM software and parameters. The curves we used are denoted by C [m] for 1 ≤ m ≤ 100, where C [m] is constructed from the point (x, y) = mQ with Q = (5, 8) on the curve y 2 = x 3 -x 2 -9x + 9. The #1 and #100-column in Table 1 list the largest and smallest, respectively, number of primes found per curve, with the average-column averaging the counts over all one hundred curves. Results of the tests for families (i)-(iii) are less interesting and not reported.

Per b-value the ratio of the best yield over C [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] , C [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] , . . . , C [100] and the yield of the single best performing earlier curve C 6 is given in the #1 / C6 -column of Table 1, but no single new curve has been identified that actually realizes the small gain suggested (but see Table 2 below). Indeed, the outcome of the same performance comparison between the average of the C [m] -curves and C 6 is more variable and with 65 of the one hundred C [m] -curves having a higher average yield than C 6 , the performance is close. The curve with the best average ratio (of 1.0064) compared to C 6 is C [93] , and curves C [22] and C [86] are the only two curves that have higher yield than C 6 (and thus than C 2×4 ) for all but three b-values; there are ten C [m] curves for which the yield is lower than for C 6 for four b-values. As can be seen in Table 1, for b = 23 all C [m] -curves considered have higher yield than C 6 . Unlike [START_REF] Daniel | Starfish on strike[END_REF], we do not specify which of C [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] , C [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] , . . . , C [100] has the best yield because with no curve appearing more than twice among the "top three" this information is useless. This is illustrated, in the #1 / #100 -column, by the ratio of the yields of the best and worst performing C [m] per b-value: with small ratios all C [m] -curves tested can be seen to behave similarly. The figures in the ratio-columns of the tables in [START_REF] Daniel | Starfish on strike[END_REF] are much larger -with one thousand curves per table they not only cast their net much wider, but they also allow a greater variation (of Galois properties) of curves per batch. All our parameterized curves have higher yields than the curve C 2×4 , even though they are all family (iv) curves. This is due to our choice of the non-torsion point (x j , y j ) which implies that the group of the curve modulo about half of the primes contains a point P such that (x j , y j ) = 2P , thereby for those primes effectively adding a doubling in the scalar multiplication in ECM. The effect diminishes with larger b-values (see also the last column of Table 2).

Additional tests. On the EECM website2 the yields of ECM using a fixed Edwards curve are given when applied to batches of 2 20 b-bit primes, for b up to 63. We used the same EECM software and parameters (but our own sets of 2 20 b-bit primes) to conduct the same experiment for the following four Edwards curves:

• the curve C [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] : -x 2 +y 2 = 1-15 8 4 x 2 y 2 , the first curve of our parametrization of family (iv) curves;

• the above curve C 6 , i.e., the best performing curve from [START_REF] Daniel | Starfish on strike[END_REF];

• the curve C 12 : x 2 + y 2 = 1 -24167 25 x 2 y 2 from the EECM website, with torsion group of order twelve and a non-torsion point 5 23 , -1 7 with very small coordinates;

• the above curve C 2×4 from [START_REF] Daniel | Starfish on strike[END_REF] belonging to family (iv), but not appearing in our parametrization of family (iv) curves.

As can be seen in Table 2 the yields are very close. The average yield-ratios of curve C [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] compared to the three other curves (in the last row of Table 2) suggest that the new curve C [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] overall performs best. Note too that the three other curves were chosen as the best among large batches of previously known curves, whereas C [START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] is just the first one of our newly parameterized family (iv) curves. Based on the final column of Table 1, we expect that all these new curves behave similarly.

The non-monotone yield decrease, consistent among the four curves tested, can be attributed to the choice of parameters in the EECM software.

Conclusion

In [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] favorable properties of the Galois group structures of a = -1 twisted Edwards curves with torsion group isomorphic to Z/2Z×Z/4Z were identified. This gave rise to four families of curves that looked promising for application in ECM. A new rational parametrization of a = -1 twisted Edwards curves with torsion group isomorphic to Z/2Z × Z/4Z then led to an elliptic parametrization for the curves in one family, but not the most promising one.

In this paper we extended the constructions from [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF] by developing six further rational parametrizations, and use three of them to formulate five new elliptic parametrizations that enable fast generation of curves for all families of curves from [START_REF] Barbulescu | Finding ECM-friendly curves through a study of Galois properties[END_REF]. We conducted the same tests as described in [START_REF] Daniel | Starfish on strike[END_REF] for the family of curves that are, based on their Galois properties, most promising for ECM. With respect to the criteria from [START_REF] Daniel | Starfish on strike[END_REF] usage of this family of curves leads to slightly better performance of ECM than reported before, with no significant fluctuations across curves from this same family. The newly parameterized curves may prove to be most useful for ECM-based cofactoring in the number field sieve. We do not claim that our results are complete: other parametrizations than the ones presented in this paper may exist.

All potential new savings identified in this paper rely on the properties of the curves used, not on the way arithmetic on the curve is performed. Indeed, we rely on the same improvement from [START_REF] Hisil | Twisted Edwards curves revisited[END_REF] that is exploited in [START_REF] Daniel | Starfish on strike[END_REF] and use the same software that was used in [START_REF] Daniel | Starfish on strike[END_REF].

Example 3 . 4 .

 34 To illustrate this strategy, substituting e+k ke-1 for x in Equation (3.1), it is found that k 2 +1 e 4 +2ke 3 +(k 2 -1)e 2 -2ke+1 must be a square. With the fixed point e = 3 4k the denominator becomes ( 4k 2 +9

y 2 =y 2 = x 3 -x 2 -

 2232 x 3 -x 2 -64x + 64 {(1, 0), (±8, 0)}(-6, 14)

y 2 ,

 2 identified by the non-torsion point 825 2752 , 1521 1504 in the #1-column (for b = 21 and b ≥ 24) and #2-column (for b = 19, 22) of [4, Table

Table 1 .

 1 Yields for C 6 and the family (iv) curves C 2×4 , C [1] , C [2] , . . . , C [100] .

	b	C 6	C 2×4	#1 (among C [1] , C [2] , . . . , C [100] ) average #100	#1 / C6	#1 / #100
	15	1127	1049	1202	1155.36	1103 1.0665 1.0897
	16	1693	1564	1806	1737.32	1664 1.0667 1.0853
	17	3299	2985	3324	3197.86	3077 1.0075 1.0802
	18	6150	5529	6168	6020.01	5921 1.0029 1.0417
	19	10802 10200	10881 10723.75 10500 1.0073 1.0362
	20	16148 15486	16396 16197.71 15955 1.0153 1.0276
	21	24160 22681	24312 24003.34 23655 1.0062 1.0277
	22	48378 46150	48894 48515.60 48114 1.0106 1.0162
	23	83339 82743	85525 84839.98 84254 1.0262 1.0150
	24 193069 187596 193558 192825.73 191961 1.0025 1.0083
	25 318865 311864 320498 319154.79 317304 1.0051 1.0100
	26 493470 480006 495082 493556.42 492364 1.0032 1.0055

Table 2 .

 2 Yield comparisons for C[START_REF] Arthur | Finding suitable curves for the elliptic curve method of factorization[END_REF] versus C 6 , C 12 and C 2×4 .

	b	C [1]	C 6	C [1] / C6	C 12	C [1] / C12	C 2×4	C [1] / C2×4

This was recognized by Peter L. Montgomery.

http://eecm.cr.yp.to/performance.html

Acknowledgements

This work has been supported in part by the European Union's H2020 Programme under grant agreement number ERC-669891.