# Research on Attacking a Special Elliptic Curve Discrete Logarithm Problem.

1. IntroductionLet E be an elliptic curve over a finite field [F.sub.q], where q = [p.sup.n] and p is prime. Given points P, Q [member of] E([F.sub.q]) to find an integer [alpha], if it exists, such that Q = [alpha]P. The computational problem is called elliptic curve discrete logarithm problem (ECDLP). This problem is the fundamental building block for elliptic curve cryptography (ECC) and pairing-based cryptography and has been a major area of research in computational number theory and cryptography for several decades.

The security of elliptic curve cryptography is based on the difficulty of the ECDLP. Like any other discrete logarithm problem, ECDLP can be solved by generic algorithms such as the Baby-Step Giant-Step method [1] and Pollard rho method [2]. At present, parallelized Pollard rho algorithm [3] is the fastest general-purpose method for solving the ECDLP. So far, Pollard rho method has been implemented on a variety of accelerator platforms including FPGAs, Playstation 3 Cell Processors, and GPUs.

Many bilinear maps were applied to establish efficient cryptographic schemes, whose security relies on the infeasibility of newly proposed mathematical problems such as Bilinear Diffie-Hellman Problem (BDHP) [4], Strong Diffie-Hellman Problem (SDHP) [5], Bilinear Diffie-Hellman Inversion Problem (BDHIP) [6], and Bilinear Diffie-Hellman Exponent Problem (BDHEP) [7].

A variant of the Diffie-Hellman problem introduced by Boneh and Boyen [5] is to compute that when given P, [alpha]P, [[alpha].sup.2]P, ..., [[alpha].sup.d]P. Problems of this type (including the simpler case of being given P, [alpha]P, [[alpha].sup.d]P) are sometimes called discrete logarithm problems with auxiliary inputs.

In Eurocrypt 2006, Cheon [8, 9] first proposed an algorithm for solving discrete logarithm problem with auxiliary inputs (DLP-wAI). Auxiliary inputs are some additional information which is provided for solving DLP, such that some elements (P, [alpha]P, [[alpha].sup.2]P, ... [member of] G) instead of only two elements (P, [alpha]P [member of] G).

Let G = <P> be an additive cyclic group generated by an element P of prime order p. The time complexity of Cheon's algorithm is O([square root of ((p - 1)/d)] + [square root of (d)]) with O(max{[square root of ((p - 1)/d)], [square root of (d)]}) storage in the case of d | (p - 1). In particular, when d [approximately equal to] [square root of (p)], it only needs O([??]) in time and space. Cheon also presents a variant for the case when d | (p + 1). The idea of Cheon's algorithm is to embed a discrete logarithm [alpha] from [F.sup.*.sub.p] to an auxiliary group [F.sup.*.sub.p] (or [mathematical expression not reproducible]) for p - 1 (or p + 1 case, resp.).

In 2009, Satoh [10] proposed a possible generation of Cheon's algorithm when d is a divisor of [[phi].sub.n](p) when n [greater than or equal to] 2, where [[phi].sub.n](p) is the nth cyclotomic polynomial. Although Satoh described the algorithm in the context of general linear groups, essentially Satoh's algorithm used embedding from [F*.sub.p] to an auxiliary group [mathematical expression not reproducible]. In the case of n = 2, Satoh's algorithm reduced the number of input data pieces by the half of Cheon's original algorithm. However, the efficiency of the algorithm was not well-studied. Kim [11, 12] studied Satoh's generalization of the p + 1 algorithm for solving the DLP-wAI. The result showed that the complexity of Satoh's algorithm was not faster than Cheon's algorithm when d | [[phi].sub.n](p) and n [greater than or equal to] 3. One of the main problems when using this mapping is the occurrence of high degree polynomials.

In 2012, Kim and Hee [13] proposed a new approach to solve the DLP-wAI focusing on the behavior of the function mapping rather than embedding the secret key to an auxiliary group. Kim's algorithm reduced solving DLP-wAI into finding a polynomial whose substitution polynomial has many absolutely irreducible factors. In p + 1 case, the complexity of Kim's algorithm is O([square root of ([p.sup.2]/R)] [log.sup.2]d log p) with d auxiliary elements, where R is the number of pairs (x, y) [member of] [F.sub.p] x [F.sub.p] such that f(x) = f(y), while Cheon's algorithm required 2d auxiliary elements for the same problem. However, it would be more difficult to design such a polynomial with small value sets.

Sakemi et al. [14] investigated useful techniques for speeding up Cheon's algorithm and demonstrated that it is possible to solve 160-bit DLP-wAI over a pairing-friendly elliptic curve within a practical time.

In this paper, we introduce a new algorithm for solving ECDLP-wAI. If P, [alpha]P, [[alpha].sup.k]P, [mathematical expression not reproducible], [mathematical expression not reproducible], ..., [mathematical expression not reproducible] P [member of] G are given, specify that d is a prime number and that [phi] is the Euler totient function and that k is a generator of multiplicative cyclic group with order [phi](d); we can solve [alpha] [member of] [Z.sup.*.sub.p] by using O([square root of ((p - 1)/d)]+d) group operations and O([square root of ((p - 1)/d)]) storage.

The rest of this paper is organized as follows. In Section 2, we describe Cheon's algorithm. We define a group partition and show how group elements can be represented with only a few elements in Sections 3 and 4. In Section 5, we propose an algorithm for the ECDLP-wAI and analyze the complexity. Then our experimental results are reported in Section 6. Finally, we conclude this paper in Section 7.

2. Preliminary

In this section we introduce some notations and concepts used throughout this paper.

2.1. Discrete Logarithm Problem with Auxiliary Inputs. The DLP-wAI was first proposed by Cheon in [8,9] as a variant of DLP. Let G = <P> be an additive cyclic group generated by the base point P of prime order p. The DLP-wAI in G is to solve [alpha] [member of] [F*.sub.p] from some additional information such as [[alpha].sup.i]P [member of] G for some integer i.

Cheon proposed two types (p - 1 and p + 1 case) of DLP-wAI. Both of the two algorithms transform the discrete logarithm in [F*.sub.p] into an auxiliary group, and solving the DLP in the auxiliary group is more efficient than original group.

We now sketch the technique due to Brown and Gallant [15] for solving ECDLP instances P, [alpha]P, [[alpha].sup.d] P, where P has order p and d | (p - 1). Fix [zeta] [member of] [Z.sup.*.sub.p] of order equal to (p - 1), so that [[zeta].sup.d] has order (p - 1)/d. Since [[alpha].sup.d] has order modulo p dividing (p - 1)/d, we have [[alpha].sup.d] [equivalent to] [([[zeta].sup.d]).sup.x] (mod p) for some integer 0 [less than or equal to] [k.sub.1] < (p - 1)/d. Writing m [left arrow] [??][square root of ((p - 1)/d)][??] and [k.sub.1] = u + mv with 0 [less than or equal to] u, v < m we have [[alpha].sup.d]P = [([[zeta].sup.d]).sup.u][([[zeta].sup.md]).sup.v]P. Hence one can compute a list of values ([[zeta].sup.-du])[P.sub.d] and a list of values ([[zeta].sup.dm])vP and find in O([square root of ((p - 1)/d)]) steps the matching pair (u, v). Writing [k.sub.1] = u + mv we have [[alpha].sup.d] [equivalent to] [([[zeta].sup.d]).sup.k] (mod p). To find a we write [alpha] = [[zeta].sup.k] and note that k = [k.sub.1] + [k.sub.2] [square root of ((p - 1)/d)] for some 0 [less than or equal to] [k.sub.2] < d. By a similar method based on [alpha]P one computes [k.sub.2] in O([square root of (d)]) steps and hence computes [alpha]. Overall we compute [alpha] in O(max{[square root of ((p - 1)/d)], [square root of (d)]}) group operations.

The p - 1 case is that P, [alpha]P, [[alpha].sup.d]P are given for a positive divisor d of p - 1. This case maps [alpha] to [[alpha].sup.d] and the subgroup of [F.sup.*.sub.p] with order (p - 1)/d as the auxiliary group. We give Cheon's algorithm with p - 1 case as follows:

Algorithm 1. Input: [P, [P.sub.1] = [alpha]P, [P.sub.d] = [[alpha].sup.d]P [member of] G}, d | p - 1; Output: [alpha] [member of] [Z.sup.*.sub.p]: (1) Find a generator [zeta] [member of] [Z.sup.*.sub.p], (2) Set [[zeta].sub.d] [left arrow] [[zeta].sup.d], (3) m [left arrow] [??][square root of ((p - 1)/d)][??], [??] [left arrow] [??](p - 1)/md[??], (4) Find 0 [less than or equal to] u < m, 0 [less than or equal to] v [less than or equal to] m such that [[zeta].sup.-u.sub.d][P.sub.d] = [[zeta].sup.mv.sub.d]P, (5) [k.sub.1] [left arrow] u + mv, (6) Set [[zeta].sub.e] = [[zeta].sup.(p-)/d], (7) m' [left arrow] [??][square root of (d)][??], [??]' [left arrow] [??]d/m'[??], (8) Find 0 [less than or equal to] u' [less than or equal to] m, 0 [less than or equal to] v' [less than or equal to] [??]' such that [mathematical expression not reproducible], (9) [k.sub.2] [left arrow] u' + m'v', (10) Output [mathematical expression not reproducible].

The secret key [alpha] [member of] [F.sup.*.sub.p] can be recovered in time complexity O([square root of ((p- 1)/d)] + [square root of (d)]) by using O(max{[square root of ((p - 1)/d)], [square root of (d)]}) storage. In the extreme case where there is a factor d | (p - 1) with d [approximately equal to] [square root of (p)], then one can solve the ECDLP in O([??]) steps, which is much efficient than that for solving DLP in general groups (which requires O([square root of (p)])).

The p + 1 case is that P, [alpha]P, [[alpha].sup.2]P, ..., [[alpha].sup.2d]P are given for a positive divisor d of p + 1. This case maps a to [([alpha] + [theta]).sup.(p-1)xd], where [theta] [member of] [F.sup.2.sub.p\[F.sub.p], and the subgroup of [mathematical expression not reproducible] with order (p + 1)/d as the auxiliary group. We give Cheon's algorithm with p + 1 case as follows:

Algorithm 2. Input: let {P, [P.sub.1] = [alpha]P, [P.sub.2] = [[alpha].sup.2]P, ..., [P.sub.2d] = [[alpha].sup.2d]P [member of] G}, d | p + 1, a a quadratic nonresidue of [Z.sub.p], and [theta] a root of [X.sup.2] - a in [F.sub.p], H [less than or equal to] [F.sub.p][[theta]]*, [beta] = [[beta].sub.0] + [[beta].sub.1][theta], and [absolute value of (H)] = p + 1; Output: [alpha] [member of] [Z.sup.*.sub.p]: (1) Find a generator [zeta] [member of] H, (2) Set [[zeta].sub.d] [left arrow] [[zeta].sup.d] [[bar.[zeta]].sub.d] [left arrow] [[zeta].sup.-1.sub.d], (3) m [left arrow] [??][square root of ((p + 1)/d)][??], [??] [left arrow] [??](p + 1)/md[??], (4) [mathematical expression not reproducible], (5) Find 0 [less than or equal to] u m, 0 [less than or equal to] v [less than or equal to] [??] in such that [[zeta].sup.-u.sub.d] [[beta].sup.d] = [[zeta].sup.mv.sub.d], (6) [k.sub.1] [left arrow] u + mv, (7) Set [[zeta].sub.e] = [[zeta].sup.(p+1)/d], (8) m' [left arrow] [??][square root of (d)][??], [??] [left arrow] [??]d/m'[??], (9) Find 0 [less than or equal to] u' < m', 0 [less than or equal to] v' [less than or equal to] [??] such that [mathematical expression not reproducible], (10) [k.sub.2] [left arrow] u' + m'v', (11) [mathematical expression not reproducible], (12) Output [alpha] = [[beta].sub.1]/([[beta].sub.0] + 1).

The secret key [alpha] [member of] [F.sup.*.sub.p] can be recovered in time complexity O([square root of ((p + 1)/d)] + d) by using O(max{[square root of ((p + 1)/d)], [square root of (d)]}) storage.

3. Partitions of Group Elements

In this section, we introduce a representation of a multiplicative subgroup and then give a group action on [F.sup.*.sub.p]. For more information about group theory, one refers to [16, 17].

3.1. Multiplicative Cyclic Subgroup of [Z.sup.*.sub.p-1] Construction. A representation of the subgroup can help to analyze the structure of the subgroup. In this paper, we introduce a new representation for multiplicative subgroup of [Z.sup.*.sub.p-1], where p is an odd prime.

Let S be a subset of [Z.sub.p]. The greatest common divisor of all integers s is denoted by gcd(S), where s mod (p - 1) belongs to S. We define a subset K of [Z.sup.*.sub.p-1] by K = (1 + [lambda][Z.sub.p-1]) [intersection] [Z.sup.*.sub.p-1], where p - 1 = d[lambda], [lambda] is an even integer, and d is an odd prime number.

Lemma 3. Let K = {n[lambda] +1; n [member of] [0, (p - 1)/[lambda])} [intersection] [Z.sup.*.sub.p-1]. Thus K is a multiplicative subgroup of [Z.sup.*.sub.p-1].

Proof. Let 1 + i[lambda], 1 + j[lambda] [member of] K; then (1 + i[lambda])(1 + j[lambda]) mod (p-1) [equivalent to] 1 + (i + j + ij[lambda])[lambda] mod (p - 1). Since gcd(1 +i[lambda], p - 1) = 1 and gcd(1 + j[lambda], p - 1) = 1, this means gcd((1 + i[lambda])(1 + j[lambda]), p - 1) = 1. So (1 + i[lambda])(1 + j[lambda]) [member of] K.

Let 1 + i[lambda] [member of] K; we assume (1 + i[lambda])(1 + j[lambda]) [equivalent to] 1 mod (p - 1). Since 1 + (i + j + ij[lambda]) [lambda] [equivalent to] 1 mod (p - 1) [??] i + j(1 + [lambda]) [equivalent to] 0 mod d and gcd(d, 1 + i[lambda]) = 1, then there exists j such that 1 + j[lambda] is the inverse of 1 + i[lambda].

It is closed under multiplication and inversion. Therefore K is a multiplicative subgroup of [Z.sup.*.sub.p-1].

Since [lambda] is an even integer, every element of K is as form 1 + n[lambda] so that [lambda] = gcd(K - 1), where K - 1 = {k - 1: k [member of] K}.

3.2. Group Action

Definition 4 (see [16]). An action of group G on a set S is a function G x S [right arrow] S (usually denoted by (g, x) [right arrow] g [omicron] x) such that for all [g.sub.1], [g.sub.2] [member of] G, x [member of] S satisfies:

([g.sub.1][g.sub.2]) [omicron] x = [g.sub.1] [omicron] ([g.sub.2] [omicron] x), e [omicron] x = x, (1)

where e is a unit element of G. When such an action is given, we say that G acts on set S.

Since there may be many different actions of group G on given set S, the notation gx is ambiguous. A group action on a set induces a partition of this set, which is called the orbit of the set under this group action.

Let G be a group that acts on a set S. The relation on S defined by x ~ x' [??] gx = x' for some g [member of] G is an equivalence relation. The equivalence classes of the equivalence relation are called the orbits of the set under this group action; usually the orbit of x [member of] S is denoted as <x>.

A group action of G on a set S induces a partition of S via the equivalence relation defined by x ~ x' [??] g [omicron] x = x' for some g [member of] G. The equivalence classes are called orbits of S under the action of G; usually the orbit of x [member of] S is denoted as <x>. We define the set of fixed points of S under the action of G by Fix(G) = {x [member of] S: g [omicron] x = x for all g [member of] G} and the set of nonfixed points nFix(G) by S \ Fix(G). Hence all elements of group G can be represented by only two types of elements, fixed points and nonfixed points.

We define the action of subgroup K on [F.sup.*.sub.p] such that K x [F.sup.*.sub.p] [right arrow] [F.sup.*.sub.p] satisfies (k, x) [right arrow] [x.sup.k] for all k [member of] K and x [member of] [F.sup.*.sub.p]. This map induces a set [x.sup.K] = {[x.sup.k] : k [member of] K} that is called a K-orbit of x. In particular, Fix(K) = {x [member of] [F*.sub.p] | [x.sup.k] [equivalent to] x mod (p - 1), for every k [member of] K} is a subgroup of [F*.sub.p], which is the set of fixed points.

Let [xi] be a primitive element in [Z.sub.p]; then [zeta] = [[xi].sup.(p-1)/[lambda]] is a generator of a cyclic group. Obviously, the fixed point set is generated by [zeta] where <[zeta]> = {x [member of] [F.sup.*.sub.p]: [x.sup.[lambda]] = 1 mod (p - 1)} and [lambda] = gcd{k - 1: k [member of] K}.

By using this group action on [F.sup.*.sub.p], we can efficiently partition [F.sup.*.sub.p]. Thus the elements of [F.sup.*.sub.p] can be represented with only a few subsets.

4. A Group Represented by Disjoint Orbits

In this section, we introduce how to partition group elements by disjoint orbits.

4.1. A Group Partition. Let [mathematical expression not reproducible], where I = {2, 3, ..., t} is an index set, [p.sub.2], ..., [p.sub.t] are distinct odd prime numbers, and each [e.sub.i] [greater than or equal to] 1. We choose a prime divisor [p.sub.j] of p - 1 with [e.sub.j] = 1, denoted as [p.sub.j] = d. Let [mathematical expression not reproducible]. It is equivalent to gcd([lambda], d) = 1. We generate a set K that is defined by K := {1 + n[lambda]: n [member of] [0, d)}.

Proposition 5. Let K = {1 + n[lambda]: n [member of] e [0, d)} [intersection] [Z.sup.*.sub.p-1] be a multiplicative subgroup of [Z.sup.*.sub.p-1]. Thus the order of K is [phi](d), where [phi] denotes Eulers totient function.

Let (p - 1)/[lambda] = d be prime; then [absolute value of (K)] = d - 1. We note that gcd([lambda], d) = 1 and 1 + n[lambda], where 0 [less than or equal to] n < d. Obviously, 1 + n[lambda] is a complete residue modulo d for 0 [less than or equal to] n < d. Thus, there exists unique 0 [less than or equal to] n' < d such that d | 1 + n'[lambda]. So all the elements of K can be expressed by K = {1 + n[lambda]: n [member of] [0, d) \ n'}. Thus we know that [absolute value of (K)] = [phi](d) = d-1.

Proposition 6. Let K = {1 + n[lambda]: n [member of] [0, d) n'} be a multiplicative subgroup of [Z.sup.*.sub.p-1]. If gcd([lambda], d) = 1, then K is a cyclic group.

Proof. We define a map f: K [right arrow] [Z.sup.*.sub.d], where [Z.sup.*.sub.d] is a multiplicative cyclic group of order d - 1. The map f is defined by f: 1 + n[lambda] [right arrow] (1 + n[lambda]) mod d for every 1 + n[lambda] [member of] K.

Let 1 + n[lambda] = [k.sub.1]d + [t.sub.1] and 1 + m[lambda] = [k.sub.2]d + [t.sub.2], where 0 [less than or equal to] [t.sub.1], [t.sub.2] < d:

(1 + n[lambda]) (1 + m[lambda]) mod d

= ([k.sup.1]d + [t.sub.1]) ([k.sub.2]d + [t.sub.2]) mod d

= [k.sub.1][k.sub.2][d.sup.2] + ([k.sub.1][t.sub.2] + [t.sub.1][k.sub.2])d + [t.sub.1][t.sub.2] mod d

= [t.sub.1][t.sub.2] mod d,

(1 + n[lambda]) mod d x (1 + m[lambda]) mod d

= ([k.sub.1]d + [t.sub.1]) mod d x ([k.sub.2]d + [t.sub.2]) mod d

= [t.sub.1] mod d x [t.sub.2] mod d = [t.sub.1][t.sub.2] mod d. (2)

Hence (1 + n[lambda])(1 + m[lambda]) mod d [equivalent to] (1 + n[lambda]) mod d x (1 + m[lambda]) mod d; it implies that the map f is a group-homomorphism for the multiplicative structures on K and [Z.sup.*.sub.d]. In order to prove the map is bijective, we only need to prove the map f is injective.

If 1 + n[lambda] [not equal to] 1 + m[lambda], then (1 + n[lambda]) mod d [not equal to] (1 + m[lambda]) mod d for all 0 [less than or equal to] n, m < d and n [not equal to] m. Suppose (1 + n[lambda]) mod d = (1 + m[lambda]) mod d; then d | (n - m)[lambda]. Since gcd([[lambda], d) = 1, we have d | n - m. This is a contradiction. Therefore, the map f is injective. It is natural that f is bijective. Hence the groups K and [Z.sup.*.sub.d] are isomorphism (written as K [congruent to] [Z.sup.*.sub.d]).

Therefore the group K is a cyclic group.

Then we need to find a generator of K. Since K is a cyclic group and K [congruent to] [Z.sup.*.sub.d], the homomorphism f maps the generator of K to the generator of [Z.sup.*.sub.d]. Let [gamma] be a generator of [Z.sup.*.sub.d]; then K = <[f.sup.-1]([gamma])>. The following proposition implies that [mathematical expression not reproducible] are all the distinct elements for x [member of] [F.sup.*.sub.p] \ <[zeta]>, where k is a generator of K.

Proposition 7. Let K be defined as above and [zeta] a generator of Fix(K); then all elements [mathematical expression not reproducible] in the same orbit are distinct for every x [member of] [F.sup.*.sub.p] <[zeta]>.

Proof. Suppose that [mathematical expression not reproducible] for 0 [less than or equal to] i, j < d, i [not equal to] j. Writing this as [mathematical expression not reproducible], we know p - 1 | [k.sup.i] - [k.sup.j]. Since [k.sup.i] - [k.sup.j] = l[lambda], where 0 [less than or equal to] l < (p - 1)/[lambda], notice that ord(x) = p - 1; we have (p - 1) | l[lambda]. However, p - 1 > l[lambda]; this is a contradiction. Thus [mathematical expression not reproducible] are distinct for 0 [less than or equal to] i, j < d, i [not equal to] j.

Let [zeta] be a generator of a cyclic group of fixed point. In the following we mainly discuss the relation between [[zeta].sup.i][x.sup.K] and [[zeta].sup.j][x.sup.K] under the condition gcd([lambda], d) = 1 for all 0 [less than or equal to] i, j [less than or equal to] [lambda] - 1 and i [not equal to] j, where [zeta] is a fixed point and x is a nonfixed point.

Proposition 8. Let K be a multiplicative subgroup of [Z.sup.*.sub.p-1] and [zeta] a generator of fixed point for [lambda] = gcd(K - 1). If gcd([lambda], d) = 1, then any two orbits [[zeta].sup.i][x.sup.K] and [[zeta].sup.j][x.sup.K] are disjoint for 0 [less than or equal to] i, j [less than or equal to] [lambda] - 1, i [not equal to] j.

Proof. Any two orbits [[zeta].sup.i][x.sup.K] and [[zeta].sup.j][x.sup.K] are disjoint for 0 [less than or equal to] i, j [less than or equal to] [lambda] - 1, i [not equal to] j. It is equivalent to ([[zeta].sup.i][x.sup.K])[intersection] ([[zeta].sup.j][x.sup.K]) [not equal to] 0. Suppose that ([[zeta].sup.i][x.sup.K])[intersection] ([[zeta].sup.j][x.sup.K]) [not equal to] 0 for some i, j. This means that [[zeta].sup.i][x.sup.K] = [[zeta].sup.j][x.sup.K] and [mathematical expression not reproducible], where [k.sup.m], [k.sup.n] [member of] K. Since [([[zeta].sup.i-j]).sup.[lambda]] = 1 and [mathematical expression not reproducible] for x [member of] [F*.sub.p], the order of y divides both [lambda] and d. Then it divides gcd([lambda], d) = 1, from which it follows that y must be equal to 1. This is a contradiction, so [[zeta].sup.i][x.sup.K] and [[zeta].sup.j][x.sup.K] are disjoint. On the other hand, if i = j, there is natural [[zeta].sup.i][x.sup.K] = [[zeta].sup.j][x.sup.K].

From the above discussion, we conclude that two orbits [[zeta].sup.i][x.sup.K] and [[zeta].sup.j][x.sup.K] are identical or disjoint. Therefore, group elements can be expressed by disjoint orbits. We may divide the group G into two classes, the nonfixed points (denoted as [G.sub.njp]) and the fixed points (denoted as [G.sub.jp]). The group G can be expressed by G = [G.sub.njp] [union] [G.sub.fp], where [union] denotes the disjoint union.

The nonfixed points part [G.sub.njp] behaves just like an extended orbit. [G.sub.njp] can be partitioned by the disjoint union of distinct [G.sub.x,nfp], such as [G.sub.x,nfp] = [x.sup.K] [union] [zeta][x.sup.K] [union] ... [union] [[zeta].sup.[lambda]-1][x.sup.K] where we choose x [member of] G as a nonfixed point representative element, and [zeta] [member of] G is a fixed point.

The above discussion gives a decomposition of group elements as union of distinct orbits, which we call the orbit decomposition formula. Furthermore, we can take these elements x, [zeta]x, ..., [[zeta].sup.[lambda]-1]x as the different representatives for distinct orbits. Obviously, any two orbits [[zeta].sup.i][x.sup.K] and [[zeta].sub.j][x.sup.K] are one-to-one correspondence, where 0 [less than or equal to] i, j < [lambda]. Thus any two orbits have the same cardinality.

Hence, the cardinality of [G.sub.x,nfp] can be expressed by [absolute value of (K)][lambda] for x [member of] G. The order of G can be expressed by [absolute value of (G)] = [absolute value of ([G.sub.x,nfp] [union] [G.sub.fp])] = ([absolute value of (K)] + 1) [lambda] for a non-fixed point x [member of] G and a fixed point [zeta] [member of] G.

Example 9. Let K = {1, 5, 9, 13, 17, 25} [less than or equal to] [Z*.sub.28;] define a map [mathematical expression not reproducible] for k = 5 and 0 [less than or equal to] i [less than or equal to] 5. We consider a group partition method on [Z.sup.*.sub.71]. Then we have [lambda] = 4 disjoint orbits of length [phi](d) = 6. Since there is one-to-one correspondence between any two orbits, the group [Z.sup.*.sub.29] can be divided as follows:

[2.sup.K] = {2, 3, 19, 14, 21, 11},

[4.sup.K] = 25 x [2.sup.K] = {4, 9, 13, 22, 6, 5},

[7.sup.K] = 70 x [2.sup.K] = {7, 16, 20, 25, 24, 23},

[8.sup.K] = 57 x [2.sup.K] = {8, 27, 15, 18, 10, 26}. (3)

So the cardinality of every orbit is [absolute value of (K)] = [absolute value of ([2.sup.K])] = [absolute value of ([4.sup.K])] = [absolute value of ([7.sup.K])] = [absolute value of ([8.sup.K])] = 6. We have 4 fixed points [G.sub.fp] = <12> = {1, 12, 17, 28} and note that [1.sub.4] [equivalent to] [12.sup.4] [equivalent to] [17.sup.4] [equivalent to] [28.sup.4] [equivalent to] 1 mod 29. Obviously, [G.sub.nfp] can be represented as [G.sub.nfp] = [2.sup.K] [union] [4.sup.K] [union] [7.sup.K] [union] [8.sup.K]. Thus [Z.sup.*.sub.29] can be partitioned by [F.sup.*.sub.71] = Fix(K) [intersection] nFix(K).

5. A Special Polynomial Construction

In [13], Kim and Hee proposed a fast multipoint evaluation method to solve DLP-wAI focusing on the behavior of function mapping between the finite fields rather than using embedding for auxiliary groups. This method reduced solving DLP-wAI into finding a polynomial whose substitution polynomial has many absolutely irreducible factors.

In this section, we construct a polynomial f(x) [member of] [F.sub.p][x] having the same value for the elements in the same orbit. We define a function f(x) by

[mathematical expression not reproducible], (4)

where [k.sup.[phi](d)] = 1 mod (p - 1). It implies that [mathematical expression not reproducible] are all distinct elements and that this sequence is repeated for further powers. Furthermore, we define the equivalence relation ~ on [F.sup.*.sub.p] as follows:

[mathematical expression not reproducible], (5)

where [zeta] is a fixed point and [[zeta].sup.i]x are the representatives of distinct orbits.

This relation partitions the group [F.sup.*.sub.p] into different equivalence classes, and each class contains [phi](d) elements. Obviously, any two equivalence classes, that is, <[[zeta].sup.i]x> and <[[zeta].sup.j]x>, have one-to-one correspondence for all i, j and i [not equal to] j.

Proposition 10. Let K be multiplicative subgroup of [Z.sup.*.sub.p-1] and [zeta] a generator of fixed point. Then we have [mathematical expression not reproducible] mod p and f([[zeta].sup.i]x) [equivalent to] [[zeta].sup.i] f(x) mod p, where x [member of] [F.sup.*.sub.p] \ <[zeta]>, k [member of] K, and 0 [less than or equal to] i [less than or equal to] [lambda] - 1.

Proof. One has (k = C mod p for all k e K; the orbit generated by [[zeta].sup.i]x satisfies [([[zeta].sup.i]x).sup.K] = [[zeta].sup.i][x.sup.K] for all 0 [less than or equal to] i [less than or equal to] [lambda] - 1.

5.1. The Proposed Algorithm

Theorem 11. Let G = <P> be an additive cyclic group of prime order p with a generator P. Let K be a multiplicative subgroup of [F.sup.*.sub.p-1] with [lambda] = gcd(K - 1). Suppose that a generator [zeta] of [F.sup.*.sub.p-1] and [mathematical expression not reproducible] are given. Then [alpha] [member of] [F*.sub.p] can be computed in time 2[??][square root of ((p - 1)/d)][??] + (d-1) group operations by using storage for [??][square root of ((p - 1)/d)][??] elements of G.

Proof. Let G = <P> be an additive cyclic group generated by an element P of prime order p. Polynomial [mathematical expression not reproducible] mod p has the same value for all elements in an orbit, and it is to say that [mathematical expression not reproducible] mod p, where k, [k.sub.2], ..., [k.sup.[phi](d)-1] [member of] K and [alpha] [member of] [F.sup.*.sub.p].

Given [mathematical expression not reproducible], we first compute [mathematical expression not reproducible]. Then we randomly choose a nonfixed element [beta] from [F*.sub.p] and evaluate f(x) at [beta]. There exist nonnegative integers 0 [less than or equal to] i, j [less than or equal to] [lambda] - 1 such that [[zeta].sup.t] f([alpha]) = f([beta]).

If we take m = [??][square root of ((p - 1)/d)][??], t can be expressed in a unique manner as t = mv + u, where 0 [less than or equal to] u, v < m. This implies that

[[zeta].sup.mv] f([alpha]) = [[zeta].sup.-u] f([beta]). (6)

Since f([alpha]) is unknown value, in practice, we search for integers u and v that satisfy

[[zeta].sup.mv] f([alpha])P = [[zeta].sup.-u] f([beta])P. (7)

In order to find such t, we use Baby-Step Giant-Step [1] method. We construct a lookup table, which contains all the pairs ([[zeta].sup.-u] f([beta])P, u) for 0 [less than or equal to] u < m, and we sort the table by the first component. Then we compute [[zeta].sup.mv] f([alpha])P for each 0 [less than or equal to] v < m and compare with the lookup table in order to identify coincidence. Note that the terms in both sides of (7) can be computed by repeated elliptic curve scalar multiplication. Thus, we can determine a pair of (u, v) that satisfies (7) in 2m group operations by using storage for m elements of G. Then t can be found.

There is [[zeta].sup.t]f([alpha])P = f([beta])P or equivalently f([[zeta].sup.t][alpha])P = f([beta])P. Since the kth power of any point is still in the same orbit, there exists an integer [k.sup.l] [member of] K such that [mathematical expression not reproducible]. We compute [mathematical expression not reproducible] and compare with [[zeta].sup.t][alpha]P in G, where 0 [less than or equal to] i [less than or equal to] [lambda] - 1. This gives [mathematical expression not reproducible].

We briefly describe this method in Algorithm 12. The algorithm is probabilistic, in which [beta] [member of] [F.sup.*.sub.p] satisfies [[zeta].sup.t]f([alpha])P = f([beta])P for our attack. Since all elements of group [F.sup.*.sub.p] can be represented by fixed point and nonfixed point, the probability that a random element [beta] [member of] [F.sup.*.sub.p] is a nonfixed point is [phi](d)[lambda]/p = 1 - [lambda]/p, which is sufficiently large.

Algorithm 12 (a new algorithm to ECDLP with auxiliary inputs). Consider the following:

Input: let {[mathematical expression not reproducible]}, {k, [k.sub.2], ..., [k.sup.[phi](d)-1] [member of] K}, and [xi] a primitive element in [F.sub.p], [mathematical expression not reproducible]; Output: [alpha] [member of] [F.sup.*.sub.p]: (1) Set [zeta] [left arrow] [[xi].sup.d], (2) [Step 1] Compute [mathematical expression not reproducible], (3) Randomly choose [beta] [member of] [F.sup.*.sub.p] and compute [mathematical expression not reproducible], (4) [Step 2] m [left arrow] [??][square root of ([lambda])][??], (5) Find 0 [less than or equal to] u, v < m, such that [[zeta].sup.mv] f([alpha])P = [[zeta].sup.-u] f([beta])P, (6)In case of failure, return to line 3 until t [left arrow] mv + u, (7) [Step 3] Find [k.sup.l] [member of] K, 0 < I < [phi](d) such that [mathematical expression not reproducible], (8) Output [mathematical expression not reproducible].

In summary, if [mathematical expression not reproducible] and multiplicative group K are given, the proposed algorithm computes [alpha] approximately in O([square root of ((p - 1)/d)] + d) group operations with storage O([square root of ((p - 1)/d)]) in G.

6. Experimental Results

This section describes our experimental results of our new algorithm for an elliptic curve. We successfully solved ECDLP-wAI by our implementation in a group G with 61-bit order.

6.1. Parameters. We use an addition cyclic group G = <P> with order p on an elliptic curve [y.sup.2] + xy = [x.sup.3] + [x.sup.2] + 415485412408256448 defined over a binary finite field [mathematical expression not reproducible]. Concrete values of these parameters are summarized in the following:

(i) q = 0x2000000000000000 (61 - bit)

= [2.sup.61],

(ii) #E = 0x1FFFFFFFF35AB90A (61 - bit)

= 2305843009001535754

= 2 x 1152921504500767877,

(iii) p = 0xFFFFFFFF9AD5C85 (61- bit)

= 1152921504500767877,

(iv) p-1 = 0xFFFFFFFF9AD5C84 (61 - bit)

= [2.sup.2] x 7 x 1213 x 33945398201059,

where #E denotes the number of points in [mathematical expression not reproducible]. In the implementation of our new algorithm, we use the following parameters:

(i) [lambda] = 950471149629652 (50 - bit),

(ii) [??][square root of ([lambda])][??] = 30829713 (25 - bit),

(iii) k = 1900942299259305,

(iv) d = 1213, [absolute value of (K)] = 1212, K = {[k.sup.i] | i [member of] [0, 1211]},

(v) [G.sub.fp] = <[zeta]> = <917376305973559977> and [absolute value of ([G.sub.fp])] = [lambda].

Here, d is chosen to minimize the time complexity of our algorithm. The element [zeta] is chosen as the generator of the multiplicative group [G.sub.fp]. A base point P is randomly chosen from points in E([F.sub.q]) with order p. Given the coordinate of [mathematical expression not reproducible], the corresponding values for x and y are as follows:

x (P) = 0x15934FDA439710FD,

y(P) = 0x23394044E191AD5

x([P.sub.1]) = 0x1EBFBF5362EA038C,

y([P.sub.1]) = 0x1499B155A750CE2C

x([P.sub.2]) = 0x1A8DE21E255B38F8,

y([P.sub.2]) = 0x1A16E1F6A5367A3B

...

x([P.sub.1212]) = 0x2C878114BD6109E,

y([P.sub.1212]) = 0x11C28EA554F98437. (8)

6.2. Results. In this experiment, we randomly choose an element [beta] = 916588465071928542.

Step 1. We compute [mathematical expression not reproducible] and [mathematical expression not reproducible] as follows:

x (f ([alpha]) P) = 0xF18BC6972DD660F,

y (f ([alpha]) P) = 0x103F35553C14D081,

x (f ([beta]) P) = 0x16983D29CE603AF0,

y (f ([beta]) P) = 0x13E3CF104F63D01D. (9)

Step 2. We search for the integer 0 [less than or equal to] t < [lambda] such that

[[zeta].sup.t] x f([alpha])P = f([beta])P. (10)

It is equivalent to searching for integer 0 [less than or equal to] u, v < [??][square root of ([lambda])][??], such that

[[zeta].sup.[??][square root of ([lambda])][??]v] x f([alpha])P = [[zeta].sup.-1] x f([beta])P. (11)

We establish two databases [DB.sub.L] = {[[zeta].sup.i[??][C'? f(o)P} and [DB.sub.R] = {[[zeta].sup.-j] x f([beta])P}. To establish database [DB.sub.R], we have to compute and store the following points:

[[zeta].sup.-0] x f([beta])P, [[zeta].sup.-1] x f([beta])P, [[zeta].sup.-2] x f([beta])P, ..., [[zeta].sup.-([??][square root of ([lambda])][??]-1)] x f([beta])P. (12)

In order to reduce the storage space, we use the point compression technique as [18]. Each point [[zeta].sup.-j] x f([beta])P is digested as [LSB.sub.64](MD5(x(P) [parallel] y(P))), so each point needs 8 bytes.

Thus, [??][square root of ([lambda])][??] x 8 = 246637704 bytes ([approximately equal to]235.2 Mbytes) is required for [DB.sub.R], and about 6.5 hours is required in total (on Pentium[R] Dual-Core CPU E5700 3.00 GHz). To establish database [DB.sub.L],

[mathematical expression not reproducible] (13)

were computed and stored. With the same space saving technique, [??][square root of ([lambda])][??] x 8 = 246637704 bytes ([approximately equal to]235.2 Mbytes) was required for [DB.sub.L], and 6.5 hours was required in total.

Then, a collision [[zeta].sup.[??][square root of ([lambda])][??]v] x f([alpha])P = [[zeta].sup.-u] x f([beta])P between two databases [DB.sub.L] and [DB.sub.R] was searched by a naive method. Since databases are small, the time for comparison is negligible. Collisions v =7 and u = 235 were found. Thus, a solution

t = [??][square root of ([lambda])][??] v + u = 215808226 (14)

can be found.

Step 3. To find a, we have known an integer t that satisfies [[zeta].sup.t] x f([alpha])P = f([beta])P; it is equivalent to [mathematical expression not reproducible] for 0 [less than or equal to] l [less than or equal to] 1211. Locate [[zeta].sup.t] x [alpha]P from the set [mathematical expression not reproducible] to find 0 [less than or equal to] l [less than or equal to] 1211 such that [mathematical expression not reproducible]. Finally, we succeed in finding a solution [mathematical expression not reproducible].

7. Conclusion

In this paper, we propose a new ECDLP-wAI and give an algorithm to solve the ECDLP efficiently. When given some points [alpha]P, [[alpha].sub.k]P, [mathematical expression not reproducible], [mathematical expression not reproducible], ..., [mathematical expression not reproducible] P [member of] G and multiplicative cyclic group K, our new algorithm can recover the secret key [alpha] [member of] [F*.sub.p] in P([square root of ((p - 1)/d)] + d) group operations by using O([square root of ((p - 1)/d)]) storage, where k is a generator of K and [phi](d) is the order of K. This algorithm can be used to attack these cryptographic schemes that admit an oracle returning kth power of its secret key upon an arbitrary input.

http://dx.doi.org/10.1155/2016/5361695

Competing Interests

The authors declare that they have no competing interests.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (nos. 61309016, 61379150, and 61103230), Fundamental Research Funds for the Central Universities (no. JB140302), and the National Cryptology Development Project of China (no. MMJJ201201004).

References

[1] D. Shanks, "Class number, a theory of factorization and genera," in Proceedings of the Symposia in Pure Mathematics, vol. 20, pp. 415-440, 1971.

[2] J. M. Pollard, "Monte carlo methods for index computations (mod p)," Mathematics of Computation, vol. 32, no. 143, pp. 918-924, 1978.

[3] P. C. Van Oorschot and M. J. Wiener, "Parallel collision search with cryptanalytic applications," Journal of Cryptology, vol. 12, no. 1, pp. 1-28, 1999.

[4] D. Boneh and M. Franklin, "Identity-based encryption from the Weil pairing," SIAM Journal on Computing, vol. 32, no. 3, pp. 586-615, 2003.

[5] D. Boneh and X. Boyen, "Short signatures without random oracles," in Advances in Cryptology--EUROCRYPT 2004, pp. 56-73, Springer, Berlin, Germany, 2004.

[6] D. Boneh and X. Boyen, "Efficient selective-id secure identity-based encryption without random oracles," in Advances in Cryptology--EUROCRYPT2004, pp. 223-238, Springer, Berlin, Germany, 2004.

[7] D. Boneh, C. Gentry, and B. Waters, "Collusion resistant broadcast encryption with short ciphertexts and private keys," in Advances in Cryptology--CRYPTO 2005, V. Shoup, Ed., vol. 3621 of Lecture Notes in Computer Science, pp. 258-275, Springer, Berlin, Germany, 2005.

[8] J. H. Cheon, "Security analysis of strong diffie-hellman problem," in Advances in Cryptology--EUROCRYPT2006, vol. 4004, pp. 1-11, Springer, Berlin, Germany, 2006.

[9] J. H. Cheon, "Discrete logarithm problems with auxiliary inputs," Journal of Cryptology, vol. 23, no. 3, pp. 457-476, 2010.

[10] T. Satoh, "On generalization of Cheon's algorithm," IACR Cryptology ePrint Archive 2009:58, 2009.

[11] T. Kim, Integer factorization and discrete logarithm with additional in-formation [Ph.D. thesis], Seoul National University, 2011.

[12] M. Kim, J. H. Cheon, and I.-S. Lee, "Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs," Mathematics of Computation, vol. 83, no. 288, pp. 1993-2004, 2014.

[13] T. Kim and C. J. Hee, "A new approach to discrete logarithm problem with auxiliary inputs," IACR Cryptology ePrint Archive 2012:609, 2012.

[14] Y. Sakemi, G. Hanaoka, T. Izu, M. Takenaka, and M. Yasuda, "Solving a discrete logarithm problem with auxiliary input on a 160-bit elliptic curve," in Public Key Cryptography--PKC 2012, M. Fischlin, J. Buchmann, and M. Manulis, Eds., vol. 7293 of Lecture Notes in Computer Science, pp. 595-608, Springer, New York, NY, USA, 2012.

[15] D. R. L. Brown and R. P. Gallant, "The static Diffie-Hellman problem," Cryptology ePrint Archive Report 2004/306, 2004, https://eprint.iacr.org/2004/306.

[16] T. W. Hungerford, Algebra, Graduate Texts in Mathematics, 1980.

[17] S. Lang, Algebra, Graduate Texts in Mathematics, Springer, New York, NY, USA, 3rd edition, 2002.

[18] T. Izu, M. Takenaka, and M. Yasuda, "Experimental results on Cheon's algorithm," in Proceedings of the 5th International Conference on Availability, Reliability, and Security (ARES '10), pp. 625-628, IEEE, February 2010.

Jiang Weng, (1,2) Yunqi Dou, (1) and Chuangui Ma (3)

(1) State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China

(2) Air Force Engineering University, Xian 710038, China

(3) Basic Department, Army Aviation Institution, Beijing 101123, China

Correspondence should be addressed to Jiang Weng; wengjiang858@163.com

Received 17 December 2015; Revised 15 May 2016; Accepted 31 May 2016

Academic Editor: Nazrul Islam

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Weng, Jiang; Dou, Yunqi; Ma, Chuangui |

Publication: | Mathematical Problems in Engineering |

Date: | Jan 1, 2016 |

Words: | 7307 |

Previous Article: | Multidimensional and Interactive Assessment Model of Large-Scale Infrastructure Project and Its Demonstration Based on Double Utility. |

Next Article: | Customized Dictionary Learning for Subdatasets with Fine Granularity. |

Topics: |