This paper addresses the discrete logarithm problem (DLP) in elliptic curve (EC) cryptography. ECs have been intensively studied in algebraic geometry and number theory. In recent years, they have been used in devising efficient algorithms for factoring integers and primality proving, and in the construction of public key cryptosystems.
In particular, EC cryptography whose security is based on the intractability of the DLP in ECs (ECDLP) has drawn considerable public attention in recent years.
Let E/Fq be an EC given by the Weierstrass equation: y2 + a1xy + a3y = x3 + a2x2 + a4x + a6, a1, a2, a3, a4, a6 ∈ Fq , (1) where Fq is a finite field with q = pm elements (p: prime, and m ≥ 1). The ECDLP in E/Fq is defined to find 0 ≤ l ≤ n − 1 such that R = lP := P + P + ··· + P | {z } l given P ∈ E(Fq ) and R ∈
, where n is the order of the finite cyclic group. Through the paper, we denote for E(K ) := {(x, y) ∈ K × K |(x, y) satisfies Eq.(1)}∪{O}, the addition is defined in such a way that E := E(K¯ ) makes an abelian group, where K¯ is the algebraic closure of K , and O is the identity element of the group . The main reason why EC cryptosystems are getting more accepted compared to the conventional schemes is that it is believed that the ECDLP in E/Fq generally requires an exponential time in log q to solve it (V. Miller [15], and J. Silverman and J. Suzuki [23]) while the DLP in F∗ q can be solved at most within a subexponential time. In other words, if EC cryptosystems provide equivalent security as the existing schemes, then the key lengths will be shorter. Having short key lengths means smaller bandwidth and memory requirements and can be a crucial factor in some applications, for example the design of smart card systems. However, it has been reported that for specific cases the ECDLP is no more difficult than the DLP by considering injective homomorphisms that map in a polynomial time from
to Fq or F∗ qk , where F∗ qk is a suitable extension field of Fq . (For attacks against hyper-EC cryptography, L. Adleman, J. DeMarrais, and M. Huang gave a heuristic argument that under certain assumptions, the DLP in the group of rational points on the Jacobian of a genus g hyper-EC over Fp is solved in a subexponential time for sufficiently large g and odd p with log p ≤ (2g + 1)0.98. For the detail, see [1].) For the reduction to Fq , recently only the case of anomalous ECs, i.e. the case of q = p and #E(Fp ) = p, and its simple generalization have been solved [21,24,18]. On the other hand, for the reduction to F∗ qk , A. Menezes, T. Okamoto, and S. Vanstone [13] proposed the so-called MOV reduction that makes it possible to solve the case of supersingular ECs, i.e. the case of p|t with t := q + 1− #E(Fq ). In other words, for supersingular ECs the ECDLP in E/Fq is reduced to the DLP in F∗ qk for some k that is solved in a subexponential time. The DLP obtained in that way is defined in F∗ qk , so that the input size is multiplied by k. In actual, the value of k is the minimum positive integer such that E[n] ⊆ E(Fqk ), where E[n] := {T ∈ E|nT = O}. Menezes, Okamoto, and Vanstone found in [13] that if E/Fq is supersingular, such a k is at most six, and constructed a probabilistic polynomial time algorithm to find Q ∈ E[n] such that the Weil pairing en(P, Q) [22] has order n in F∗ qk . Concerning the reduction to F∗ qk , after the MOV reduction appeared, G. Frey and H. R¨uck [7] proposed another injective homomorphism based on the Tate pairing (FR reduction). The FR reduction is applied when n|q − 1. Also, by extending the definition field from Fq to Fqk , the reduction is possible even for the case of n|qk − 1. In this case, k is the minimum positive integer such that n|qk −1. Then, as in the MOV reduction, the input size of the DLP is multiplied by k. But the Ref. [7] dealt with only the conceptual aspect. At this point, we should be aware that there is a gap between the conditions to which the MOV and FR reductions are applied. In fact, according to R. Schoof [19], if p 6 |n, E[n] ⊆ E(Fqk ) is equivalent to n|qk − 1 and other two conditions. In this paper, we generalize the MOV reduction so that it can be applied to some non-supersingular ECs satisfying E[n] ⊆ E(Fqk ) for some k (Section 2). This extension is never straightforward since no algorithm has been proposed to efficiently find for non-supersingular ECs some Q ∈ E[n] such that en(P, Q) is a primitive nth root of unity. We construct a polynomial time algorithm to realize it although those ECs do not cover all the ones satisfying E[n] ⊆ E(Fqk ).
Moreover, we prove that it is possible to immediately find such a Q ∈ E[n] for the MOV reduction unless c2n|c1 when we express the group structure as1 E(Fq ) ∼= Zn1 ⊕ Zn2, E[n] ⊆ E(Fqk ), and E(Fqk ) ∼= Zc1n1 ⊕ Zc2n1 with n2|n1 and c2|c1 (See [13,14]). On the other hand, quite recently, R. Balasubramanian and N. Koblitz [5] showed that if n is a prime, n 6 |q, and n 6 |q −1, then E[n] ⊆ E(Fqk ) is equivalent to n|qk − 1. In this sense, if n is a prime, the following are the cases that the (extended) MOV reduction cannot deal with but the FR can: 1. n|q − 1; and 2. E[n] ⊆ E(Fqk ), c2n|c1. Next, we describe the detail algorithm for the FR reduction, and analyze the computational property (in Section 3). We actually implement the FR reduction for many cases. In addition, we compare it with the extended MOV reduction except for those two cases (in Section 4). Consequently, we should suggest that the FR is better than the MOV in any situation. Through the paper, for brevity, we assume 1. the order n of
is a prime. If the given n = Q i pei i is not a prime. the problem is reduced to finding for each i, l mod pi such that R = lP. Then, we can obtain the values of l mod pei i for all i using the Pohlig-Hellman’s algorithm [17] to determine l mod n using the Chinese Remainder Theorem. Further, without loss of generality, we can further assume the following two conditions: 2. p 6 |t (non-supersingularity), and 3. p 6 |n (non-anomalousness) i.e. p 6= n because for those cases, the ECDLP has been already solved in subexponential and polynomial times, respectively. This paper has primarily an expository role. 2 Extending the MOV Reduction The framework of the MOV reduction can be described as follows ([13], page 71 in [14]). The idea is to extend the definition field from Fq to Fqk for some k so that E[n] ⊆ E(Fqk ). Algorithm 1 Input: an element P ∈ E(Fq ) of order n, and R ∈
. Output: an integer l such that R = lP
Step 1: determine the smallest integer k such that E[n] ⊆ E(Fqk ). Step 2: find Q ∈ E[n] such that α = en(P, Q) has order n. Step 3: compute β = en(R, Q). Step 4: compute l, the discrete logarithm of β to the base α in F∗ qk . Let µn be the group of nth roots of unity, en: E[n]×E[n] → µn the Weil pairing [22], and Q ∈ E[n] such that en(P, Q) is a primitive nth root of unity. Then, from the property of the Weil pairing, µn ⊆ F∗ qk holds. Thus, the group isomorphism
→ µn defined by S 7→ en(S, Q) gives an injective homomorphism
→ F∗ qk [13]. It is known that for any E/Fq there is a pair (n1, n2) such that E(Fq ) ∼= Zn1 ⊕ Zn2 with n2|n1 [14]. Ref. [13] proved that if E/Fq is supersingular, 1. k is at most 6, and 2. if put E(Fqk ) ∼= Zc1n1 ⊕ Zc2n1 for appropriate c1 and c2 with c2|c1, then c1 = c2. In general, the values of c1 and c2 can be obtained by the following: 1. Count #E(Fq ), using Schoof’s method [20] or its variant [6,2]. 2. For each k, (a) compute #E(Fqk ) from #E(Fq ), using the Weil Theorem [14]; (b) factor #E(Fqk ); and (c) find n0 1 and n0 2 such that E(Fqk ) ∼= Zn0 1 ⊕ Zn0 2 , using Miller’s algorithm [16] (c1 = n0 1/n1 and c2 = n0 2/n1). However, it would be time-consuming to follow these steps: the first two steps take polynomial times, the third takes a subexponential time, and the last takes a probabilistic polynomial time, provided k is small enough compared to q. However, in Ref. [13], Algorithm 1’, which will be mentioned later, is constructed concretely based on the following facts concerning supersingular ECs: 1. there are six classes of supersingular ECs; 2. the values of k and c (= c1 = c2) are uniquely determined by the class; and 3. the class is uniquely determined by the value of t = q + 1 − #E(Fq ), where t is the trace of qth-power Frobenius endomorphism. That is, for supersingular ECs, the following algorithm was proposed in [13] [14]. Algorithm 10 Input: an element P ∈ E(Fq ) of order n, and R ∈
. Output: an integer l such that R = lP Step 1’: determine the smallest integer k such that E[n] ⊆ E(Fqk ). Step 2’: pick Q0 ∈ E(Fqk ) randomly, and compute Q = [cn1/n]Q0 . Step 3’: compute α = en(P, Q) and β = en(R, Q). Step 4’: compute l 0 by solving the discrete logarithm of β to the base α in F∗ qk . Step 5’: check if l 0 P = R holds. If it does, set l = l 0 . Otherwise, go to Step 2’.
It can be easily seen that Algorithms 1 and 10 are essentially the same although they take different step. At this point, we pay attention to how to determine an element Q ∈ E[n]. The correct l is obtained with probability 1 − 1/n (φ(n)/n if n is not a prime) after Steps 1’-5’ of Algorithm 10 . Since n is large, the expected number of trials is close to one. Since we consider non-supersingular ECs, we cannot use the above three facts. Let (e, r) be such that c1/c2 = ner with e ≥ 0 and (n, r) = 1. We propose the details of Step 2 in Algorithm 1 for non-supersingular ECs as follows: Step 2-1: pick Q0 ∈ E(Fqk ) randomly. Step 2-2: set Q = [c1n1/ne+1]Q0 ∈ E[ne+1] ∩ E(Fqk ). Step 2-3: if Q 6∈ E[n], i.e. if nQ 6= O, go to Step 2-1. Step 2-4: compute α = en(P, Q). If α = 1, go to Step 2-1. We should note here that the above modification provides a generalization of the MOV reduction: previously, the MOV can be applied if the EC is supersingular, i.e. e = 0 and r = 1. If e = 0, Step 2-3 can be omitted. The following theorem suggests from a computational point of view that the extension of the MOV reduction in this paper is useful if and only if e = 0. Theorem 1 The probability that Q ∈ E[ne+1] ∩ E(Fqk ) obtained in Step 2-2 satisfies both Q ∈ E[n] and en(P, Q) 6= 1 is 1 ne (1 − 1 n). Proof: Consider the map: f : E(Fqk ) → E(Fqk ) , f(Q)=[c1n1/ne+1]Q . Then, since E(Fqk ) ∼= Zc1n1 ⊕ Zc2n1 , the image of f is isomorphic to Zne+1 ⊕ Zn. Let Ω be the set of Q such that Q ∈ E[n] and en(P, Q) 6= 1. From the property of the Weil pairing [22], en(P, Q) = 1 with P 6= O if and only if Q ∈
. Thus, #Ω = n2 − n. If Q0 ∈ E(Fqk ) is randomly selected in Step 2-1, the probability of success in Step 2-4 is obtained as: #Kerf × #Ω #E(Fqk ) = c1n1 × c2n1 ne+1 × n × (n2 − n) c1n1 × c2n1 = 1 ne (1 − 1 n) ut Corollary 1 In Steps 2-1 through 2-4 of Algorithm 1, the expected number of iterations is ne+1/(n − 1) ≈ ne. Proof: From Kac’s lemma [8], the expected time is the reciprocal number of the probability (1 − 1/n)/ne that has been obtained in Theorem 1, i.e. 1/[ 1 ne (1 − 1 n)] = ne+1 n − 1 .
Recall n = O(q), which means Step 2-3 requires an exponential time on average if e ≥ 1. If we have c2n|c1 during the field extension when we apply the MOV reduction, we must give up the reduction process. Such a probability may be small, and we might in the future come up with an alternative method that can deal with even such a case. However, we should keep in mind that there is much additional computation to realize the MOV reduction for nonsupersingular ECs: counting #E(Fq ), factoring #E(Fqk ), finding the pair (c1, c2) for the group structure E(Fqk ) (more precisely, the value of c1n1/ne+1 in Step 2-2), etc., even when E[n] ⊆ E(Fqk ) and c2n 6 |c1. 3 Implementing the FR Reduction In this section, assuming K := Fqk for some k. We consider the realization of the FR reduction. In the original paper by Frey and R¨uck [7], only the conceptual aspect was stated, and it seems that no realization on the FR reduction has been published because the FR reduction appears to be less familiar to the cryptography community than the MOV reduction. We first describe an algorithm for realizing Frey and R¨uck’s idea, where we assume that k is the minimum integer such that n|qk − 1. Algorithm 2 Input: an element P ∈ E(Fq ) of order n, and R ∈
. Output: an integer l such that R = lP. Step 1: determine the smallest integer k such that n|qk − 1, and set K := Fqk . Step 2: pick S, T ∈ E(K ) randomly. Step 3: compute the element f ∈ K (E)∗ such that div(f) = n((P) − (O)), and compute α = f(S)/f(T ) Step 4: compute γ = α qk−1 n . If γ = 1, then go to Step 2. Step 5: compute the element g ∈ K (E)∗ such that div(g) = n((R) − (O)), and compute β = g(S)/g(T ), and δ = β qk−1 n . Step 6: solve the DLP δ = γl in K ∗ , i.e. the logarithm of δ to the base γ in K ∗ . 3.1 Frey and R¨uck’s Idea Let Div(E) be the divisor group of E and supp(D) := {P ∈ E(K¯ ) : nP 6= 0} for D = X P∈E nP (P) ∈ Div(E). Then, since E is defined over K , the Galois group GK¯/K acts on Div(E) as Dσ = X P∈E nP (P σ) for D = X P∈E nP (P) ∈ Div(E) and σ ∈ GK¯/K . We say that D ∈ Div(E) is defined over K if Dσ = D for all σ ∈ GK¯/K , and denote by DivK (E) the subset of Div(E) whose elements are defined over K
For f ∈ K¯ (E)∗, the divisor div(f) is defined by div(f) := P P∈E ordP (f)(P), where ordP (f) is the multiplicity of zeros (if positive) or poles (if negative) at P ∈ E with respect to f ∈ K¯ (E)∗, and we refer to such a divisor as the principal divisor. Let Div0(E) := {D ∈ Div(E)|deg(D)=0}, where deg(D) := PnP , and P rin(E) the subset of Div0(E) whose elements are principal divisors. Then, we can define the following surjective map: Div0(E) → P ic0(E) := Div0(E)/P rin(E) , D 7→ D¯ and denote D1 ∼ D2 if two divisors D1 and D2 have the same image, i.e. D¯1 = D¯2 in P ic0(E). We further define P ic0 K (E) to be the set of all divisor classes in P ic0(E) that have a representative element defined over K , which is a subgroup of P ic0(E). Moreover, P ic0 K (E)n := {D¯ ∈ P ic0 K (E)|nD¯ = 0}. It is known that by the isomorphism E(K ) → P ic0 K (E) , Q 7→ (Q) − (O) , we can identify E(K ) with P ic0 K (E) [22], and denote (Q) − (O) by Q¯. Let A be a divisor such that A¯ ∈ P ic0 K (E)n and B another divisor P i ai(Qi) ∈ Div0 K (E) such that supp(A) ∩ supp(B) = φ. Since nA ∼ 0, there exists an element fA in the function field K¯ (E) such that div(fA) = nA [22], so that we can put fA(B) := Q i fA(Qi)ai . Then, Frey and R¨uck [7] proved the following: Proposition 1 ([7]) If n|q − 1, {A, ¯ B¯}0,n:= fA(B) defines a nondegenerate bilinear pairing: {, }0,n : E(K )[n] × E(K )/nE(K ) → K ∗ /(K ∗ ) n where E(K )[n] := E[n] ∩ E(K ). Then the mapping K ∗ → K ∗ defined by α 7→ α qk−1 n gives K ∗ /(K ∗ )n ∼= µn ⊆ K ∗ , where µn is the group of nth roots of unity. From the nondegeneracy of the pairing {, }0,n, there exists Q ∈ E(K )/nE(K ) such that {P, ¯ Q¯} qk−1 n 0,n is a primitive nth root of unity. Thus, the group isomorphism
→ µn defined by S 7→ {S, ¯ Q¯} qk−1 n 0,n gives an injective homomorphism
→ F∗ qk . The pairing {, }0,n can be said to be a variant of the Tate pairing [25]. 3.2 Theoretical Analysis In [7], the computation of Steps 2-5 is supposed to be within a probabilistic polynomial time, now we actually evaluate the computation for each step in Algorithm 2. We assume that the usual multiplication algorithms are used, so that multiplying two elements of length N takes time O(N2). For Step 2, we first pick an element x = a in K to substitute it to Eq. (1). Then, we check if the quadratic equation with respect to y has a solution
in K , i.e. if the discriminant is a quadratic residue in K . The probability of the
success is approximately a half. If it is successful, it suffices to solve the quadratic
equation in a usual manner. The computation to solve the quadratic equation
dominants one to compute quadratic roots in K . This takes expected running
time O((log qk)3) = O(k3(log q)3) (for the detail, see [4], [10]). We do this process
twice to obtain S, T ∈ E(K ).
For Step 3, there is a standard procedure to compute the function f ∈ K¯ (E)
from a principal divisor div(f) ∈ P rin(E) (see for example pages 63-64 in [14]).
Basically, this can be done by the following:
- Write div(f) = P
i ai((Pi) − (O)). - For each i, compute P0
i ∈ E and fi ∈ K¯ (E) such that
ai((Pi) − (O)) = (P0
i ) − (O) + div(fi) . - Add the divisors (P0
i ) − (O) + div(fi), for all i.
Then, we can add two divisors as follows: if two divisor D, D0 are expressed by
D = (P) − (O) + div(f) , D0 = (P0
) − (O) + div(f0
)
with P, P0 ∈ E and f,f0 ∈ K¯ (E)∗, then
D + D0 = (P + P0
) − (O) + div(ff0
g)
where g = l/v with l and v are the lines through P and P0 and through P + P0
and O (in particular, P0 = −P implies v ≡ 1). We can obtain the value of α =
f(S)/f(T ) by substituting S, T to the aforementioned f,f0
, g and multiplying
them. Hence, Step 3 takes O((log qk)2) × O(log n) = O(k2(log q)3).
For Step 4, the computation of γ = α qk−1
n takes O(log( qk−1
n ))×O((log qk)2) =
O(k3(log q)3). Moreover, we should evaluate the probability of going back to Step
2 so that we can measure how long it takes to compute the whole steps. The
crucial point here is that we should efficiently find Q¯ ∈ P ic0
K (E)/nP ic0
K (E) such
that {P, ¯ Q¯}0,n can be a generator of K ∗ /(K ∗ )n. We prove the following theorem.
Theorem 2 Let k be the smallest positive integer such that n|qk−1(in this case,
K = Fqk ). Then the probability of going back from Step 4 to Step 2 is 1/n.
Proof: Note that E(K ) ∼= Zn1 ⊕ Zn2, n2|n1, and E[n] ∼= Zn ⊕ Zn. Thus,
E(K )[n] ∼=
Zn (n 6 |n2)
Zn ⊕ Zn (n|n2).
Also, from the nondegeneracy of the FR reduction,
E(K )/nE(K ) ∼=
Zn (n 6 |n2)
Zn ⊕ Zn (n|n2).
We consider the two cases separately.
- E[n] 6⊆ E(K ), i.e. n 6 |n2: if we pick Q ∈ E(K ) randomly, the probability of
{P , ¯ Q¯}0,n 6∈ (K ∗ )n is
E(K ) − #nE(K )
E(K ) = n1n2 − n1n2/n
n1n2
= 1 − 1/n.
- E[n] ⊆ E(K ), i.e. n|n2: let T := {Q ∈ E(K )/nE(K ) | {P , ¯ Q¯}0,n 6∈ (K ∗ )n}.
Then, #T = n2 − n. Since the map ϕ : E(K ) → E(K )/nE(K ) is a module
homomorphism, the probability of {P, ¯ Q¯}0,n 6∈ (K ∗ )n is
ϕ−1(T )
E(K ) = #Ker(ϕ) × #T
E(K ) = (n1n2/n2)(n2 − n)
n1n2
= 1 − 1/n.
2
The probability of going back from Step 4 to Step 2 is almost close to zero
since we assume that n is considerably large.
For Step 5, we can estimate the computation as O(k3(log q)3).
From the above insight, if k can be assumed to be small enough compared
to q, the expected running time of the FR reduction (from Step 2 to Step 5 in
Algorithm 2) is O((log q)3).
3.3 Implementation
We made several experiments including the following four cases. The CPU is Pentium 75MHz (SONY Quarter L, QL-50NX, the second cache capacity: 256kB)
In Examples 1 and 2, the FR reduction was applied to ECs with trace 2.
Example 1 (EC with trace 2, i.e. #E(Fp ) = p − 1 ) Suppose that the curve
E/Fp : y2 = x3 + ax + b, the base point P = (x0, y0) ∈ E(Fp ), the order n of P,
and a point R = [l]P = (x1, y1) are given as follows:
p = 23305425500899 (binary 45-bits, p − 1=2 × 32 × 11378692),
a = 13079575536215, b = 951241857177,
n = 1137869,
x0 = 17662927853004, y0 = 1766549410280,
x1 = 2072411881257, y1 = 5560421985272.
Then, we find that l = 709658.
Example 2 (EC with trace 2, i.e. #E(Fp ) = p − 1 ) Suppose that the curve
E/Fp : y2 = x3 + ax + b, the base point P = (x0, y0) ∈ E(Fp ), the order n of P,
and a point R = [l]P = (x1, y1) are given as follows:
p = 93340306032025588917032364977153
(binary 107-bits, p − 1=210 × 72 × 163 × 8473212 × 39869872),
a = 71235469403697021051902688366816, b = 47490312935798014034601792244544,
n = 3986987,
x0 = 10362409929965041614317835692463, y0 = 79529049191468905652172306035573,
x1 = 15411349585423321468944221089888, y1 = 9416052907883278088782335830033.
For Example 2, the reduction process was implemented as follows:
1) Choose random points S, T ∈ E(Fp ):
R = (x2, y2),
x2 = 78183126653622965564444255681546, y2 = 78588945135854560800493672181265,
S = (x3, y3),
x3 = 58714658884321859706339658012314, y3 = 29352359294307548304481400079114.
The time of computation : 177 sec.
2) Compute the FR pairing:
Set div(f) := n((P) − (O)), div(g) := n((R) − (O)) and D := (S) − (T ),
then
{P , ¯ D¯}0,n = f(S)
f(T) = 28089673702084922579189210362050,
( f(S)
f(T) )
p−1
n = 86048548119736537511939909279595,
{Q, ¯ D¯}0,n = g(S)
g(T) = 54538105615281807032380914744128,
( g(S)
g(T) )
p−1
n = 44179423723975173427344893182175.
The time of computation:
computation of f(S): 982 sec, computation of f(T ): 996 sec,
computation of g(S): 971 sec, computation of g(T ): 968 sec,
computation of ( f(S)
f(T) )
p−1
n : 5 sec, computation of ( g(S)
g(T) )
p−1
n : 6 sec.
3) Solve the DLP: (86048548119736537511939909279595)l
= 44179423723975173427344893182175 mod p,
find that l = 764009.
Next, in Examples 3 and 4, the FR and MOV reductions were applied to
supersingular-ECs, and experimental data in the both reductions were analyzed
and compared.
Example 3 (Supersingular-EC) Suppose that the curve E/Fp : y2 = x3 +
ax + b, the base point P = (x0, y0) ∈ E(Fp ), the order n of P, and a point
R = [l]P = (x1, y1) are given as follows:
p = 23305425500899 (binary 45-bits, p +1= 22 × 52 × 29 × 1217 × 6603413),
a = 1, b = 0,
n = 6603413,
x0 = 18414716422748, y0 = 9607997424906,
x1 = 22829488331658, y1 = 15463570264423.
Since E(Fp ) ∼= Zp+1, E(Fp2 ) ∼= Zp+1 ⊕ Zp+1 [13], the definition field Fp
is extended to Fp2 to apply the FR and MOV reductions. Then, we find that
l = 4500974.
Example 4 (Supersingular-EC) Suppose that the curve E/Fp : y2 = x3 +
ax + b, the base point P = (x0, y0) ∈ E(Fp ), the order n of P, and a point
R = [l]P = (x1, y1) are given as follows:
p = 1020213065766829380286510327794694206093068319698
(binary 163-bits, p +1=23 × 33 × 59 × 113
×7084458733777404048453899025845195282548847),
a = 1, b = 0,
n = 7084458733777404048453899025845195282548847,
x0 = 6361408431660145018472734964469918949727993631117,
y0 = 222428572612516351526464210931959631877226149291,
x1 = 1791400202383882094094972648523798358242766050148,
y1 = 6662282879825452479945554028296857282243572635001.
Since E(Fp ) ∼= Zp+1
2
⊕ Z2, E(Fp2 ) ∼= Zp+1 ⊕ Zp+1 [13], the definition field
Fp is extended to Fp2 to apply the FR and MOV reductions. Set g(α) := α2 + 1.
Then Fp2 ∼= Fp [α]/g(α).
For Example 4, the FR and MOV reductions process were implemented as
follows:
(FR reduction):
1) Choose random points S, T ∈ E(Fp ):
S = (x2, y2),
x2 = 5,
y2 = 2785279641020018517947594885587158401374598752249α
T = (x3, y3),
x3 = 3385306113851451711868938545058221186172597937436,
y3 = 4986770654406953531745186184758026961048619598992.
The time of computation : 2245 sec;
2) Compute the FR pairing:
Set div(f) := n((P) − (O)), div(g) := n((R) − (O)) and D := (S) − (T ),
then
{P , ¯ D¯ }0,n = f(S)
f(T)
= 3533166625479465632799073949081211397797456268974α
+4001496656282493042880656119736166996221452751615,
( f(S)
f(T) )
p2−1
n = 5010350267319872795048848896836646242920060597592α
+6845979045282387430745118341017487648956259367889,
{R, ¯ D¯}0,n = g(S)
g(T)
= 7618053821224285687383466174720252396501663499416α
+5910267516953452268669659762088222325143176074230,
( g(S)
g(T) )
p2−1
n = 1354335315181821211682485365859218098755278877378α
+8654410318384179317451981196322210287393432354847.
The time of computation :
computation of f(S): 39667 sec, computation of f(T ): 40023 sec,
computation of g(S): 39634 sec, computation of g(T ): 39646 sec,
computation of ( f(S)
f(T) )
p2−1
n : 116 sec, computation of ( g(S)
g(T) )
p2−1
n : 136 sec.
3) Solve the DLP
(5010350267319872795048848896836646242920060597592α
+6845979045282387430745118341017487648956259367889)l
= 1354335315181821211682485365859218098755278877378α
+8654410318384179317451981196322210287393432354847 in F∗
p2 ,
find l = 3882677356899000378261873813993378.
(MOV reduction): Let R, S be as in FR reduction.
1) Compute Q = (x4, y4)=[ p+1
n ]S with order n.
x4 = 2686073998998561952934233204632904496418536385138,
y4 = 7693683030135341554015734905157658084500223439095α.
The time of computation Q : 1203 sec.
2) Compute the Weil pairing:
Set div(f) = n((P + S) − (S)), div(g) = n((R + S) − (S)) and
div(h)=(Q + T ) − (T ),
then
en(P, Q) = f(Q+T)
f(T) × h(S)
h(P +S)
= 5191780390348421007816254381110295818010622599391α
+6845979045282387430745118341017487648956259367889,
en(R, Q) = g(Q+T)
g(T) × h(S)
h(R+S)
= 8847795342486472591182617912087723962175404319605α
+8654410318384179317451981196322210287393432354847.
The time of computation:
computation of f(Q + T ): 39972 sec, computation of f(T ): 39720 sec,
computation of h(S): 39626 sec, computation of h(P + S): 39850 sec,
computation of g(Q + T ): 39992 sec, computation of g(T ): 39956 sec,
computation of h(R + S): 39862 sec.
3) Solve the DLP:
(5191780390348421007816254381110295818010622599391α
+6845979045282387430745118341017487648956259367889)l
= 8847795342486472591182617912087723962175404319605α
+8654410318384179317451981196322210287393432354847 in F∗
p2 ,
find l = 3882677356899000378261873813993378.
When we implement the FR and MOV reductions, two random points are
needed. The numbers of function values needed to compute the pairings for
the FR and MOV reductions are four and seven, respectively. In the both reductions, the computation of function values dominates the whole computation
time (Table 1).
From the implementation data and the above consideration, the computation
of function values needed to implement the FR and MOV reductions may be a
heavy load. For each reduction, the computation of pairings actually dominates
the whole computation time while other steps theoretically take O((log q)3) as
well. We find that the running time of the FR reduction is almost 4/7 times as
much as that of the MOV reduction.
Table 1. The time of computation in Examples 1-4
Type log q k Running time(sec)
Example 1 46 1 FR reduction 419
Example 2 108 1 FR reduction 4105
Example 3 46 2 FR reduction 999
MOV reduction 1872
Example 4 164 2 FR reduction 161467
MOV reduction 282426
log q and k are the binary size of the definition field and
the necessary minimum extension degree, respectively.
4 Comparing the (Extended) MOV and FR Reductions
We extended the MOV reduction so that it can be applied to some non-supersingular ECs, and implemented the FR reduction to understand the whole process.
Now time to compare the two reductions.
4.1 On the Extension Degrees
Bad news for the MOV reduction is the following fact on group structures, which
is due to R. Schoof [19]
Proposition 2 ([20]) The following two conditions are equivalent:
- E[n] ⊆ E(Fqk );
- n|qk − 1, n2|#E(Fqk ), and either φ ∈ Z or O(
t
2
k − 4qk
n2 ) ⊆ EndF
qk (E),
where φ and tk denote the qk-Frobenius endomorphism of E/Fqk and its trace,
respectively, and O( t2
k−4qk
n2 ) and EndF
qk (E) are the order of discriminant t2
k−4qk
n2
and the endomorphism ring of E/Fqk in which the isogenies are defined over Fqk ,
respectively.
In this sense, the condition under which the F R can be applied generally includes
the one under which the MOV can be applied.
On the contrary, here’s good news for the MOV reduction: the difference is
not so large between the two conditions for extension degree k under which the
MOV and FR reductions can be applied. In fact, R. Balasubramanian and N.
Koblitz [5] proved the following:
Proposition 3 ([5]) Suppose n|#E(Fq ), and that n is a prime with p 6= n,
n 6 |q − 1. Then,
E[n] ⊆ E(Fqk ) ⇐⇒ n|qk − 1
Based on the proof of Proposition 3 [5], we show the following result that provides
us with important information for comparing the extension degrees for the MOV
and FR reductions although it may be clear from Ref. [5].
Remark 1 Suppose E[n] 6⊆ E(Fq ), and that n is a prime. If n|q − 1
E[n] ⊆ E(Fqk ) ⇐⇒ k = nj with j ≥ 1
Proof: We pick the basis {P, T } of E[n] so that the matrix expression on E[n]
of the q-Frobenius endomorphism φ is given by
Mφ =
1 a
0 q
1 a
0 1
∈ GL2(Zn) .
(Recall q ≡ 1 mod n.) Then, the matrix that φk expresses is Mφk =
1 ka
0 1
.
Thus,
φk(T ) = T ⇔ ka ≡ 0 mod n ⇔ k ≡ 0 mod n ,
where we have used a 6≡ 0 mod n since E[n] 6⊆ E(Fqk ). Thus, k = nj with j ≥ 1.
2
If E[n] 6⊆ E(Fq ) and n|q − 1, Remark 2 implies that the extension degree k
is no less than n, which further means that an exponential number of extensions
are needed in the MOV reduction. Hence, then, we will have to give up applying
the MOV reduction.
4.2 On the Efficiency of the Reductions
In the following, assuming n 6 |q − 1, we compare the efficiency of the MOV and
FR reductions.
We exclude the following computation in the pre-processing:
- counting #E(Fq ), say by Schoof’s algorithm [20,6,2], and
- factoring #E(Fq ).
Moreover, suppose that the DLP that is obtained by the both reductions from
the ECDLP essentially has the same difficulty. Then, all we should compare is
the main part of the reductions, i.e. Steps 2-3 in Algorithms 1 and Step 2-5 in
Algorithm 2.
However, as considered in Section 2, compared to the FR reduction, additional computation is needed to find the group structure for E(Fqk ) for the
proposed MOV reduction, although it is computed in a subexponential time.
Moreover, as for application of the MOV reduction, we must give up the
application if e ≥ 1 in Theorem 1. Besides, we should notice that computing
the Weil pairing requires almost twice time that the pairing in the FR reduction
takes.
4.3 The Actual Difference of the Conditions Between the Two
Reductions
At present, we find that there are still two conditions under which the FR can
be applied but the MOV cannot:
- n|q − 1; and
- E[n] ⊆ E(Fqk ), c2n|c1.
Besides, the factorization of #E(Fqk ) is needed to apply Miller’s algorithm.
(This might be solved immediately because Miller’s algorithm sometimes does
not require complete factorization.)
Even if the second condition is cleared in the future, the FR reduction is
superior to the MOV reduction for the computation of the main part, i.e. for
computing the pairings, the MOV requires almost twice time that the FR takes.
In this regard, we must conclude that practically, in any situation the FR
reduction is better than the MOV reduction from an algorithmic point of view.
