# Research on Attacking a Special Elliptic Curve Discrete Logarithm Problem

Authors: Jiang Weng; Yunqi Dou; Chuangui Ma
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Cheon first proposed a novel algorithm for solving discrete logarithm problem with auxiliary inputs. Given some pointsP
,
α
P
,
α
2
P
,
…
,
α
d
P
∈
G, an attacker can solve the secret key efficiently. In this paper, we propose a new algorithm to solve another form of elliptic curve discrete logarithm problem with auxiliary inputs. We show that if some points P
,
α
P
,
α
k
P
,
α
k
2
P
,
α
k
3
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G and a multiplicative cyclic group K
=
〈
k
〉 are given, where d is a prime, φ
(
d
) is the order of K. The secret key α
∈
F
p
⁎ can be solved in O
(
(
p
-
1
)
/
d
+
d
) group operations by using O
(
(
p
-
1
)
/
d
) storage.


---

## Body

## 1. Introduction

LetE be an elliptic curve over a finite field F
q, where q
=
p
n and p is prime. Given points P
,
Q
∈
E
(
F
q
) to find an integer α, if it exists, such that Q
=
α
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
,
α
P
,
α
2
P
,
…
,
α
d
P. Problems of this type (including the simpler case of being given P
,
α
P
,
α
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
,
α
P
,
α
2
P
,
…
∈
G) instead of only two elements (P
,
α
P
∈
G).LetG
=
〈
P
〉 be an additive cyclic group generated by an element P of prime order p. The time complexity of Cheon’s algorithm is O
(
(
p
-
1
)
/
d
+
d
) with O
(
max
⁡
(
p
-
1
)
/
d
,
d
) storage in the case of d
∣
(
p
-
1
). In particular, when d
≈
p, it only needs O
(
p
4
) 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 α from F
p
∗ to an auxiliary group F
p
∗ (or F
p
2
∗) 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 φ
n
(
p
) when n
≥
2, where φ
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
p
∗ to an auxiliary group F
p
n
∗. 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
∣
φ
n
(
p
) and n
≥
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
(
p
2
/
R
log
2
⁡
d
log
⁡
p
) with d auxiliary elements, where R is the number of pairs (
x
,
y
)
∈
F
p
×
F
p such that f
(
x
)
=
f
(
y
), while Cheon’s algorithm required 2
d 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. IfP
,
α
P
,
α
k
P
,
α
k
2
P
,
α
k
3
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G are given, specify that d is a prime number and that φ is the Euler totient function and that k is a generator of multiplicative cyclic group with order φ
(
d
); we can solve α
∈
Z
p
∗ by using O
(
(
p
-
1
)
/
d
+
d
) group operations and O
(
(
p
-
1
)
/
d
) storage.The rest of this paper is organized as follows. In Section2, 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 α
∈
F
p
∗ from some additional information such as α
i
P
∈
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
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
,
α
P
,
α
d
P, where P has order p and d
∣
(
p
-
1
). Fix ζ
∈
Z
p
∗ of order equal to (
p
-
1
), so that ζ
d has order (
p
-
1
)
/
d. Since α
d has order modulo p dividing (
p
-
1
)
/
d, we have α
d
≡
(
ζ
d
)
x
(
mod
⁡
p
) for some integer 0
≤
k
1
<
(
p
-
1
)
/
d. Writing m
←
(
p
-
1
)
/
d and k
1
=
u
+
m
v with 0
≤
u
,
v
<
m we have α
d
P
=
(
ζ
d
)
u
(
ζ
m
d
)
v
P. Hence one can compute a list of values (
ζ
-
d
u
)
P
d and a list of values (
ζ
d
m
)
v
P and find in O
(
(
p
-
1
)
/
d
) steps the matching pair (
u
,
v
). Writing k
1
=
u
+
m
v we have α
d
≡
(
ζ
d
)
k
(
mod
⁡
p
). To find a we write α
=
ζ
k and note that k
=
k
1
+
k
2
(
p
-
1
)
/
d for some 0
≤
k
2
<
d. By a similar method based on α
P one computes k
2 in O
(
d
) steps and hence computes α. Overall we compute α in O
(
m
a
x
{
(
p
-
1
)
/
d
,
d
}
) group operations.Thep
-
1 case is that P
,
α
P
,
α
d
P are given for a positive divisor d of p
-
1. This case maps α to α
d and the subgroup of F
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
1
=
α
P
,
P
d
=
α
d
P
∈
G
}, d
∣
p
-
1;
Output:α
∈
Z
p
∗:
(1) Find a generator ζ
∈
Z
p
∗,
(2) Set ζ
d
←
ζ
d,
(3) m
←
(
p
-
1
)
/
d,  m
^
←
(
p
-
1
)
/
m
d,
(4) Find 0
≤
u
<
m, 0
≤
v
≤
m
^ such that ζ
d
-
u
P
d
=
ζ
d
m
v
P,
(5) k
1
←
u
+
m
v,
(6) Set ζ
e
=
ζ
(
p
-
1
)
/
d,
(7) m
′
←
d,  m
^
′
←
d
/
m
′,
(8) Find 0
≤
u
′
<
m
′,  0
≤
v
′
≤
m
^
′ such that ζ
e
-
u
′
ζ
-
k
1
P
1
=
ζ
e
m
′
v
′
P,
(9) k
2
←
u
′
+
m
′
v
′,
(10) Output α
=
ζ
k
1
+
k
2
(
p
-
1
)
/
d.The secret keyα
∈
F
p
∗ can be recovered in time complexity O
(
(
p
-
1
)
/
d
+
d
) by using O
(
m
a
x
{
(
p
-
1
)
/
d
,
d
}
) storage. In the extreme case where there is a factor d
∣
(
p
-
1
) with d
≈
p, then one can solve the ECDLP in O
(
p
4
) steps, which is much efficient than that for solving DLP in general groups (which requires O
(
p
)).Thep
+
1 case is that P
,
α
P
,
α
2
P
,
…
,
α
2
d
P are given for a positive divisor d of p
+
1. This case maps α to (
α
+
θ
)
(
p
-
1
)
·
d, where θ
∈
F
p
2
∖
F
p, and the subgroup of F
p
2
∗ 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
1
=
α
P
,
P
2
=
α
2
P
,
…
,
P
2
d
=
α
2
d
P
∈
G
}, d
∣
p
+
1, a a quadratic nonresidue of Z
p, and θ a root of X
2
-
a in F
p, H
≤
F
p
[
θ
]
∗, β
=
β
0
+
β
1
θ, and H
=
p
+
1;
Output:α
∈
Z
p
∗:
(1) Find a generator ζ
∈
H,
(2) Set ζ
d
←
ζ
d,  ζ
-
d
←
ζ
d
-
1,
(3) m
←
(
p
+
1
)
/
d, m
^
←
(
p
+
1
)
/
m
d,
(4) P
1
(
x
)
←
∑
i
=
0
d
‍
2
d
2
i
a
i
x
2
i
P, P
2
(
x
)
←
∑
i
=
0
d
-
1
‍
2
d
2
i
+
1
a
i
x
2
i
+
1
P, P
3
(
x
)
←
∑
i
=
0
d
‍
d
i
(
-
a
)
i
x
2
i
P, and β
d
←
(
P
1
x
+
P
2
x
θ
)
/
P
3
(
x
),
(5) Find 0
≤
u
<
m, 0
≤
v
≤
m
^ such that ζ
d
-
u
β
d
=
ζ
d
m
v,
(6) k
1
←
u
+
m
v,
(7) Set ζ
e
=
ζ
(
p
+
1
)
/
d,
(8) m
′
←
d, m
^
′
←
d
/
m
′,
(9) Find 0
≤
u
′
<
m
′, 0
≤
v
′
≤
m
^
′ such that β
ζ
e
-
u
′
ζ
-
k
2
=
ζ
e
m
′
v
′,
(10) k
2
←
u
′
+
m
′
v
′,
(11) β
←
ζ
k
1
+
k
2
(
p
+
1
)
/
d,
(12) Output α
=
β
1
/
(
β
0
+
1
).The secret keyα
∈
F
p
∗ can be recovered in time complexity O
(
(
p
+
1
)
/
d
+
d
) by using O
(
max
⁡
{
(
p
+
1
)
/
d
,
d
}
) storage.


## 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 α
∈
F
p
∗ from some additional information such as α
i
P
∈
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
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
,
α
P
,
α
d
P, where P has order p and d
∣
(
p
-
1
). Fix ζ
∈
Z
p
∗ of order equal to (
p
-
1
), so that ζ
d has order (
p
-
1
)
/
d. Since α
d has order modulo p dividing (
p
-
1
)
/
d, we have α
d
≡
(
ζ
d
)
x
(
mod
⁡
p
) for some integer 0
≤
k
1
<
(
p
-
1
)
/
d. Writing m
←
(
p
-
1
)
/
d and k
1
=
u
+
m
v with 0
≤
u
,
v
<
m we have α
d
P
=
(
ζ
d
)
u
(
ζ
m
d
)
v
P. Hence one can compute a list of values (
ζ
-
d
u
)
P
d and a list of values (
ζ
d
m
)
v
P and find in O
(
(
p
-
1
)
/
d
) steps the matching pair (
u
,
v
). Writing k
1
=
u
+
m
v we have α
d
≡
(
ζ
d
)
k
(
mod
⁡
p
). To find a we write α
=
ζ
k and note that k
=
k
1
+
k
2
(
p
-
1
)
/
d for some 0
≤
k
2
<
d. By a similar method based on α
P one computes k
2 in O
(
d
) steps and hence computes α. Overall we compute α in O
(
m
a
x
{
(
p
-
1
)
/
d
,
d
}
) group operations.Thep
-
1 case is that P
,
α
P
,
α
d
P are given for a positive divisor d of p
-
1. This case maps α to α
d and the subgroup of F
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
1
=
α
P
,
P
d
=
α
d
P
∈
G
}, d
∣
p
-
1;
Output:α
∈
Z
p
∗:
(1) Find a generator ζ
∈
Z
p
∗,
(2) Set ζ
d
←
ζ
d,
(3) m
←
(
p
-
1
)
/
d,  m
^
←
(
p
-
1
)
/
m
d,
(4) Find 0
≤
u
<
m, 0
≤
v
≤
m
^ such that ζ
d
-
u
P
d
=
ζ
d
m
v
P,
(5) k
1
←
u
+
m
v,
(6) Set ζ
e
=
ζ
(
p
-
1
)
/
d,
(7) m
′
←
d,  m
^
′
←
d
/
m
′,
(8) Find 0
≤
u
′
<
m
′,  0
≤
v
′
≤
m
^
′ such that ζ
e
-
u
′
ζ
-
k
1
P
1
=
ζ
e
m
′
v
′
P,
(9) k
2
←
u
′
+
m
′
v
′,
(10) Output α
=
ζ
k
1
+
k
2
(
p
-
1
)
/
d.The secret keyα
∈
F
p
∗ can be recovered in time complexity O
(
(
p
-
1
)
/
d
+
d
) by using O
(
m
a
x
{
(
p
-
1
)
/
d
,
d
}
) storage. In the extreme case where there is a factor d
∣
(
p
-
1
) with d
≈
p, then one can solve the ECDLP in O
(
p
4
) steps, which is much efficient than that for solving DLP in general groups (which requires O
(
p
)).Thep
+
1 case is that P
,
α
P
,
α
2
P
,
…
,
α
2
d
P are given for a positive divisor d of p
+
1. This case maps α to (
α
+
θ
)
(
p
-
1
)
·
d, where θ
∈
F
p
2
∖
F
p, and the subgroup of F
p
2
∗ 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
1
=
α
P
,
P
2
=
α
2
P
,
…
,
P
2
d
=
α
2
d
P
∈
G
}, d
∣
p
+
1, a a quadratic nonresidue of Z
p, and θ a root of X
2
-
a in F
p, H
≤
F
p
[
θ
]
∗, β
=
β
0
+
β
1
θ, and H
=
p
+
1;
Output:α
∈
Z
p
∗:
(1) Find a generator ζ
∈
H,
(2) Set ζ
d
←
ζ
d,  ζ
-
d
←
ζ
d
-
1,
(3) m
←
(
p
+
1
)
/
d, m
^
←
(
p
+
1
)
/
m
d,
(4) P
1
(
x
)
←
∑
i
=
0
d
‍
2
d
2
i
a
i
x
2
i
P, P
2
(
x
)
←
∑
i
=
0
d
-
1
‍
2
d
2
i
+
1
a
i
x
2
i
+
1
P, P
3
(
x
)
←
∑
i
=
0
d
‍
d
i
(
-
a
)
i
x
2
i
P, and β
d
←
(
P
1
x
+
P
2
x
θ
)
/
P
3
(
x
),
(5) Find 0
≤
u
<
m, 0
≤
v
≤
m
^ such that ζ
d
-
u
β
d
=
ζ
d
m
v,
(6) k
1
←
u
+
m
v,
(7) Set ζ
e
=
ζ
(
p
+
1
)
/
d,
(8) m
′
←
d, m
^
′
←
d
/
m
′,
(9) Find 0
≤
u
′
<
m
′, 0
≤
v
′
≤
m
^
′ such that β
ζ
e
-
u
′
ζ
-
k
2
=
ζ
e
m
′
v
′,
(10) k
2
←
u
′
+
m
′
v
′,
(11) β
←
ζ
k
1
+
k
2
(
p
+
1
)
/
d,
(12) Output α
=
β
1
/
(
β
0
+
1
).The secret keyα
∈
F
p
∗ can be recovered in time complexity O
(
(
p
+
1
)
/
d
+
d
) by using O
(
max
⁡
{
(
p
+
1
)
/
d
,
d
}
) storage.


## 3. Partitions of Group Elements

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


### 3.1. Multiplicative Cyclic Subgroup ofZ
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 ofZ
p
-
1
∗, where p is an odd prime.LetS be a subset of Z
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
p
-
1
∗ by K
=
(
1
+
λ
Z
p
-
1
)
∩
Z
p
-
1
∗, where p
-
1
=
d
λ, λ is an even integer, and d is an odd prime number.Lemma 3.
LetK
=
{
n
λ
+
1
:
n
∈
[
0
,
(
p
-
1
)
/
λ
)
}
∩
Z
p
-
1
∗. Thus K is a multiplicative subgroup of Z
p
-
1
∗.Proof.
Let1
+
i
λ, 1
+
j
λ
∈
K; then (
1
+
i
λ
)
(
1
+
j
λ
)
mod
⁡
(
p
-
1
)
≡
1
+
(
i
+
j
+
i
j
λ
)
λ
mod
⁡
(
p
-
1
). Since gcd
⁡
(
1
+
i
λ
,
p
-
1
)
=
1 and gcd
⁡
(
1
+
j
λ
,
p
-
1
)
=
1, this means gcd
⁡
(
(
1
+
i
λ
)
(
1
+
j
λ
)
,
p
-
1
)
=
1. So (
1
+
i
λ
)
(
1
+
j
λ
)
∈
K.
Let1
+
i
λ
∈
K; we assume (
1
+
i
λ
)
(
1
+
j
λ
)
≡
1
mod
⁡
(
p
-
1
). Since 1
+
(
i
+
j
+
i
j
λ
)
λ
≡
1
mod
⁡
(
p
-
1
)
⇒
i
+
j
(
1
+
λ
)
≡
0
mod
⁡
d and gcd
⁡
(
d
,
1
+
i
λ
)
=
1, then there exists j such that 1
+
j
λ is the inverse of 1
+
i
λ.
It is closed under multiplication and inversion. ThereforeK is a multiplicative subgroup of Z
p
-
1
∗.Sinceλ is an even integer, every element of K is as form 1
+
n
λ so that λ
=
gcd
⁡
(
K
-
1
), where K
-
1
=
{
k
-
1
:
k
∈
K
}.


### 3.2. Group Action

Definition 4 (see [16]).
An action of groupG on a set S is a function G
×
S
→
S (usually denoted by (
g
,
x
)
↦
g
∘
x
) such that for all g
1
,
g
2
∈
G, x
∈
S satisfies: (1)
g
1
g
2
∘
x
=
g
1
∘
g
2
∘
x
,
e
∘
x
=
x
,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 groupG on given set S, the notation g
x 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.LetG be a group that acts on a set S. The relation on S defined by x
~
x
′
⇔
g
x
=
x
′ for some g
∈
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
∈
S is denoted as 〈
x
〉.A group action ofG on a set S induces a partition of S via the equivalence relation defined by x
~
x
′
⇔
g
∘
x
=
x
′ for some g
∈
G. The equivalence classes are called orbits of S under the action of G; usually the orbit of x
∈
S is denoted as 〈
x
〉. We define the set of fixed points of S under the action of G by Fix
⁡
(
G
)
=
{
x
∈
S
:
g
∘
x
=
x for all g
∈
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 andnonfixed points.We define the action of subgroupK on F
p
∗ such that K
×
F
p
∗
→
F
p
∗ satisfies (
k
,
x
)
↦
x
k for all k
∈
K and x
∈
F
p
∗. This map induces a set x
K
=
{
x
k
:
k
∈
K
} that is called a K-orbit of x. In particular, Fix
⁡
(
K
)
=
{
x
∈
F
p
∗
∣
x
k
≡
x
mod
⁡
(
p
-
1
), for every k
∈
K
} is a subgroup of F
p
∗, which is the set of fixed points.Letξ be a primitive element in Z
p; then ζ
=
ξ
(
p
-
1
)
/
λ is a generator of a cyclic group. Obviously, the fixed point set is generated by ζ, where 〈
ζ
〉
=
{
x
∈
F
p
∗
:
x
λ
≡
1
mod
⁡
(
p
-
1
)
} and λ
=
gcd
⁡
{
k
-
1
:
k
∈
K
}.By using this group action onF
p
∗, we can efficiently partition F
p
∗. Thus the elements of F
p
∗ can be represented with only a few subsets.


## 3.1. Multiplicative Cyclic Subgroup ofZ
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 ofZ
p
-
1
∗, where p is an odd prime.LetS be a subset of Z
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
p
-
1
∗ by K
=
(
1
+
λ
Z
p
-
1
)
∩
Z
p
-
1
∗, where p
-
1
=
d
λ, λ is an even integer, and d is an odd prime number.Lemma 3.
LetK
=
{
n
λ
+
1
:
n
∈
[
0
,
(
p
-
1
)
/
λ
)
}
∩
Z
p
-
1
∗. Thus K is a multiplicative subgroup of Z
p
-
1
∗.Proof.
Let1
+
i
λ, 1
+
j
λ
∈
K; then (
1
+
i
λ
)
(
1
+
j
λ
)
mod
⁡
(
p
-
1
)
≡
1
+
(
i
+
j
+
i
j
λ
)
λ
mod
⁡
(
p
-
1
). Since gcd
⁡
(
1
+
i
λ
,
p
-
1
)
=
1 and gcd
⁡
(
1
+
j
λ
,
p
-
1
)
=
1, this means gcd
⁡
(
(
1
+
i
λ
)
(
1
+
j
λ
)
,
p
-
1
)
=
1. So (
1
+
i
λ
)
(
1
+
j
λ
)
∈
K.
Let1
+
i
λ
∈
K; we assume (
1
+
i
λ
)
(
1
+
j
λ
)
≡
1
mod
⁡
(
p
-
1
). Since 1
+
(
i
+
j
+
i
j
λ
)
λ
≡
1
mod
⁡
(
p
-
1
)
⇒
i
+
j
(
1
+
λ
)
≡
0
mod
⁡
d and gcd
⁡
(
d
,
1
+
i
λ
)
=
1, then there exists j such that 1
+
j
λ is the inverse of 1
+
i
λ.
It is closed under multiplication and inversion. ThereforeK is a multiplicative subgroup of Z
p
-
1
∗.Sinceλ is an even integer, every element of K is as form 1
+
n
λ so that λ
=
gcd
⁡
(
K
-
1
), where K
-
1
=
{
k
-
1
:
k
∈
K
}.


## 3.2. Group Action

Definition 4 (see [16]).
An action of groupG on a set S is a function G
×
S
→
S (usually denoted by (
g
,
x
)
↦
g
∘
x
) such that for all g
1
,
g
2
∈
G, x
∈
S satisfies: (1)
g
1
g
2
∘
x
=
g
1
∘
g
2
∘
x
,
e
∘
x
=
x
,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 groupG on given set S, the notation g
x 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.LetG be a group that acts on a set S. The relation on S defined by x
~
x
′
⇔
g
x
=
x
′ for some g
∈
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
∈
S is denoted as 〈
x
〉.A group action ofG on a set S induces a partition of S via the equivalence relation defined by x
~
x
′
⇔
g
∘
x
=
x
′ for some g
∈
G. The equivalence classes are called orbits of S under the action of G; usually the orbit of x
∈
S is denoted as 〈
x
〉. We define the set of fixed points of S under the action of G by Fix
⁡
(
G
)
=
{
x
∈
S
:
g
∘
x
=
x for all g
∈
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 andnonfixed points.We define the action of subgroupK on F
p
∗ such that K
×
F
p
∗
→
F
p
∗ satisfies (
k
,
x
)
↦
x
k for all k
∈
K and x
∈
F
p
∗. This map induces a set x
K
=
{
x
k
:
k
∈
K
} that is called a K-orbit of x. In particular, Fix
⁡
(
K
)
=
{
x
∈
F
p
∗
∣
x
k
≡
x
mod
⁡
(
p
-
1
), for every k
∈
K
} is a subgroup of F
p
∗, which is the set of fixed points.Letξ be a primitive element in Z
p; then ζ
=
ξ
(
p
-
1
)
/
λ is a generator of a cyclic group. Obviously, the fixed point set is generated by ζ, where 〈
ζ
〉
=
{
x
∈
F
p
∗
:
x
λ
≡
1
mod
⁡
(
p
-
1
)
} and λ
=
gcd
⁡
{
k
-
1
:
k
∈
K
}.By using this group action onF
p
∗, we can efficiently partition F
p
∗. Thus the elements of F
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

Letp
-
1
=
2
e
1
∏
i
∈
I
‍
p
i
e
i, where I
=
{
2,3
,
…
,
t
} is an index set, p
2
,
…
,
p
t are distinct odd prime numbers, and each e
i
≥
1. We choose a prime divisor p
j of p
-
1 with e
j
=
1, denoted as p
j
=
d. Let λ
=
2
e
1
∏
i
∈
I
∖
j
‍
p
i
e
i
=
(
p
-
1
)
/
d. It is equivalent to gcd
⁡
(
λ
,
d
)
=
1. We generate a set K that is defined by K
:
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
}.Proposition 5.
LetK
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
}
∩
Z
p
-
1
∗ be a multiplicative subgroup of Z
p
-
1
∗. Thus the order of K is φ
(
d
), where φ denotes Euler’s totient function.Let(
p
-
1
)
/
λ
=
d be prime; then |
K
|
=
d
-
1. We note that gcd
⁡
(
λ
,
d
)
=
1 and 1
+
n
λ, where 0
≤
n
<
d. Obviously, 1
+
n
λ is a complete residue modulo d for 0
≤
n
<
d. Thus, there exists unique 0
≤
n
′
<
d such that d
∣
1
+
n
′
λ. So all the elements of K can be expressed by K
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
∖
n
′
}. Thus we know that |
K
|
=
φ
(
d
)
=
d
-
1.Proposition 6.
LetK
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
∖
n
′
} be a multiplicative subgroup of Z
p
-
1
∗. If g
c
d
(
λ
,
d
)
=
1, then K is a cyclic group.Proof.
We define a mapf
:
K
→
Z
d
∗, where Z
d
∗ is a multiplicative cyclic group of order d
-
1. The map f is defined by f
:
1
+
n
λ
→
(
1
+
n
λ
)
mod
⁡
d for every 1
+
n
λ
∈
K.
Let1
+
n
λ
=
k
1
d
+
t
1 and 1
+
m
λ
=
k
2
d
+
t
2, where 0
≤
t
1
,
t
2
<
d:(2)
1
+
n
λ
1
+
m
λ
mod
⁡
d
=
k
1
d
+
t
1
k
2
d
+
t
2
mod
⁡
d
=
k
1
k
2
d
2
+
k
1
t
2
+
t
1
k
2
d
+
t
1
t
2
mod
⁡
d
=
t
1
t
2
mod
⁡
d
,
1
+
n
λ
mod
⁡
d
·
1
+
m
λ
mod
⁡
d
=
k
1
d
+
t
1
mod
⁡
d
·
k
2
d
+
t
2
mod
⁡
d
=
t
1
mod
⁡
d
·
t
2
mod
⁡
d
=
t
1
t
2
mod
⁡
d
.
Hence(
1
+
n
λ
)
(
1
+
m
λ
)
mod
⁡
d
≡
(
1
+
n
λ
)
mod
⁡
d
·
(
1
+
m
λ
)
mod
⁡
d; it implies that the map f is a group-homomorphism for the multiplicative structures on K and Z
d
∗. In order to prove the map is bijective, we only need to prove the map f is injective.
If1
+
n
λ
≠
1
+
m
λ, then (
1
+
n
λ
)
mod
⁡
d
≠
(
1
+
m
λ
)
mod
⁡
d for all 0
≤
n
,
m
<
d and n
≠
m. Suppose (
1
+
n
λ
)
mod
⁡
d
=
(
1
+
m
λ
)
mod
⁡
d; then d
∣
(
n
-
m
)
λ. Since gcd
⁡
(
λ
,
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
d
∗ are isomorphism (written as K
≅
Z
d
∗).
Therefore the groupK is a cyclic group.Then we need to find a generator ofK. Since K is a cyclic group and K
≅
Z
d
∗, the homomorphism f maps the generator of K to the generator of Z
d
∗. Let γ be a generator of Z
d
∗; then K
=
〈
f
-
1
(
γ
)
〉. The following proposition implies that x
,
x
k
,
x
k
2
,
…
,
x
k
φ
(
d
)
-
1 are all the distinct elements for x
∈
F
p
∗
∖
〈
ζ
〉, where k is a generator of K.Proposition 7.
LetK be defined as above and ζ a generator of Fix
⁡
(
K
); then all elements x
,
x
k
,
…
,
x
k
φ
(
d
)
-
1 in the same orbit are distinct for every x
∈
F
p
∗
∖
〈
ζ
〉.Proof.
Suppose thatx
k
i
=
x
k
j for 0
≤
i
,
j
<
d, i
≠
j. Writing this as x
k
i
-
k
j
=
1, we know p
-
1
∣
k
i
-
k
j. Since k
i
-
k
j
=
l
λ, where 0
≤
l
<
(
p
-
1
)
/
λ, notice that o
r
d
(
x
)
=
p
-
1; we have (
p
-
1
)
∣
l
λ. However, p
-
1
>
l
λ; this is a contradiction. Thus x
,
x
k
,
…
,
x
k
φ
(
d
)
-
1 are distinct for 0
≤
i
,
j
<
d, i
≠
j.Letζ be a generator of a cyclic group of fixed point. In the following we mainly discuss the relation between ζ
i
x
K and ζ
j
x
K under the condition g
c
d
(
λ
,
d
)
=
1 for all 0
≤
i
,
j
≤
λ
-
1 and i
≠
j, where ζ is a fixed point and x is a nonfixed point.Proposition 8.
LetK be a multiplicative subgroup of Z
p
-
1
∗ and ζ a generator of fixed point for λ
=
gcd
⁡
(
K
-
1
). If gcd
⁡
(
λ
,
d
)
=
1, then any two orbits ζ
i
x
K and ζ
j
x
K are disjoint for 0
≤
i
,
j
≤
λ
-
1, i
≠
j.Proof.
Any two orbitsζ
i
x
K and ζ
j
x
K are disjoint for 0
≤
i
,
j
≤
λ
-
1, i
≠
j. It is equivalent to (
ζ
i
x
K
)
∩
(
ζ
j
x
K
)
=
∅. Suppose that (
ζ
i
x
K
)
∩
(
ζ
j
x
K
)
≠
∅ for some i
,
j. This means that ζ
i
x
K
=
ζ
j
x
K and y
=
ζ
i
-
j
=
x
k
m
-
k
n, where k
m
,
k
n
∈
K. Since (
ζ
i
-
j
)
λ
=
1 and (
x
k
m
-
k
n
)
d
=
1 for x
∈
F
p
∗, the order of y divides both λ and d. Then it divides gcd
⁡
(
λ
,
d
)
=
1, from which it follows that y must be equal to 1. This is a contradiction, so ζ
i
x
K and ζ
j
x
K are disjoint. On the other hand, if i
=
j, there is natural ζ
i
x
K
=
ζ
j
x
K.From the above discussion, we conclude that two orbitsζ
i
x
K and ζ
j
x
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
n
f
p) and the fixed points (denoted as G
f
p). The group G can be expressed by G
=
G
n
f
p
∪
G
f
p, where ∪ denotes the disjoint union.The nonfixed points partG
n
f
p behaves just like an extended orbit. G
n
f
p can be partitioned by the disjoint union of distinct G
x
,
n
f
p, such as G
x
,
n
f
p
=
x
K
∪
ζ
x
K
∪
⋯
∪
ζ
λ
-
1
x
K where we choose x
∈
G as a nonfixed point representative element, and ζ
∈
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 elementsx
,
ζ
x
,
…
,
ζ
λ
-
1
x as the different representatives for distinct orbits. Obviously, any two orbits ζ
i
x
K and ζ
j
x
K are one-to-one correspondence, where 0
≤
i
,
j
<
λ. Thus any two orbits have the same cardinality.Hence, the cardinality ofG
x
,
n
f
p can be expressed by |
K
|
λ for x
∈
G. The order of G can be expressed by |
G
|
=
|
G
x
,
n
f
p
∪
G
f
p
|
=
(
|
K
|
+
1
)
λ for a non-fixed point x
∈
G and a fixed point ζ
∈
G.Example 9.
LetK
=
{
1,5
,
9,13,17,25
}
≤
Z
28
∗; define a map x
↦
x
k
i for k
=
5 and 0
≤
i
≤
5. We consider a group partition method on Z
71
∗. Then we have λ
=
4 disjoint orbits of length φ
(
d
)
=
6. Since there is one-to-one correspondence between any two orbits, the group Z
29
∗ can be divided as follows:(3)
2
K
=
2,3
,
19,14,21,11
,
4
K
=
25
×
2
K
=
4,9
,
13,22,6
,
5
,
7
K
=
70
×
2
K
=
7,16,20,25,24,23
,
8
K
=
57
×
2
K
=
8,27,15,18,10,26
.
So the cardinality of every orbit is|
K
|
=
|
2
K
|
=
|
4
K
|
=
|
7
K
|
=
|
8
K
|
=
6. We have 4 fixed points G
f
p
=
〈
12
〉
=
{
1,12,17,28
} and note that 1
4
≡
1
2
4
≡
1
7
4
≡
2
8
4
≡
1
mod
⁡
29. Obviously, G
n
f
p can be represented as G
n
f
p
=
2
K
∪
4
K
∪
7
K
∪
8
K. Thus Z
29
∗ can be partitioned by F
71
∗
=
Fix
⁡
(
K
)
∪
nFix
(
K
).


## 4.1. A Group Partition

Letp
-
1
=
2
e
1
∏
i
∈
I
‍
p
i
e
i, where I
=
{
2,3
,
…
,
t
} is an index set, p
2
,
…
,
p
t are distinct odd prime numbers, and each e
i
≥
1. We choose a prime divisor p
j of p
-
1 with e
j
=
1, denoted as p
j
=
d. Let λ
=
2
e
1
∏
i
∈
I
∖
j
‍
p
i
e
i
=
(
p
-
1
)
/
d. It is equivalent to gcd
⁡
(
λ
,
d
)
=
1. We generate a set K that is defined by K
:
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
}.Proposition 5.
LetK
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
}
∩
Z
p
-
1
∗ be a multiplicative subgroup of Z
p
-
1
∗. Thus the order of K is φ
(
d
), where φ denotes Euler’s totient function.Let(
p
-
1
)
/
λ
=
d be prime; then |
K
|
=
d
-
1. We note that gcd
⁡
(
λ
,
d
)
=
1 and 1
+
n
λ, where 0
≤
n
<
d. Obviously, 1
+
n
λ is a complete residue modulo d for 0
≤
n
<
d. Thus, there exists unique 0
≤
n
′
<
d such that d
∣
1
+
n
′
λ. So all the elements of K can be expressed by K
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
∖
n
′
}. Thus we know that |
K
|
=
φ
(
d
)
=
d
-
1.Proposition 6.
LetK
=
{
1
+
n
λ
:
n
∈
[
0
,
d
)
∖
n
′
} be a multiplicative subgroup of Z
p
-
1
∗. If g
c
d
(
λ
,
d
)
=
1, then K is a cyclic group.Proof.
We define a mapf
:
K
→
Z
d
∗, where Z
d
∗ is a multiplicative cyclic group of order d
-
1. The map f is defined by f
:
1
+
n
λ
→
(
1
+
n
λ
)
mod
⁡
d for every 1
+
n
λ
∈
K.
Let1
+
n
λ
=
k
1
d
+
t
1 and 1
+
m
λ
=
k
2
d
+
t
2, where 0
≤
t
1
,
t
2
<
d:(2)
1
+
n
λ
1
+
m
λ
mod
⁡
d
=
k
1
d
+
t
1
k
2
d
+
t
2
mod
⁡
d
=
k
1
k
2
d
2
+
k
1
t
2
+
t
1
k
2
d
+
t
1
t
2
mod
⁡
d
=
t
1
t
2
mod
⁡
d
,
1
+
n
λ
mod
⁡
d
·
1
+
m
λ
mod
⁡
d
=
k
1
d
+
t
1
mod
⁡
d
·
k
2
d
+
t
2
mod
⁡
d
=
t
1
mod
⁡
d
·
t
2
mod
⁡
d
=
t
1
t
2
mod
⁡
d
.
Hence(
1
+
n
λ
)
(
1
+
m
λ
)
mod
⁡
d
≡
(
1
+
n
λ
)
mod
⁡
d
·
(
1
+
m
λ
)
mod
⁡
d; it implies that the map f is a group-homomorphism for the multiplicative structures on K and Z
d
∗. In order to prove the map is bijective, we only need to prove the map f is injective.
If1
+
n
λ
≠
1
+
m
λ, then (
1
+
n
λ
)
mod
⁡
d
≠
(
1
+
m
λ
)
mod
⁡
d for all 0
≤
n
,
m
<
d and n
≠
m. Suppose (
1
+
n
λ
)
mod
⁡
d
=
(
1
+
m
λ
)
mod
⁡
d; then d
∣
(
n
-
m
)
λ. Since gcd
⁡
(
λ
,
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
d
∗ are isomorphism (written as K
≅
Z
d
∗).
Therefore the groupK is a cyclic group.Then we need to find a generator ofK. Since K is a cyclic group and K
≅
Z
d
∗, the homomorphism f maps the generator of K to the generator of Z
d
∗. Let γ be a generator of Z
d
∗; then K
=
〈
f
-
1
(
γ
)
〉. The following proposition implies that x
,
x
k
,
x
k
2
,
…
,
x
k
φ
(
d
)
-
1 are all the distinct elements for x
∈
F
p
∗
∖
〈
ζ
〉, where k is a generator of K.Proposition 7.
LetK be defined as above and ζ a generator of Fix
⁡
(
K
); then all elements x
,
x
k
,
…
,
x
k
φ
(
d
)
-
1 in the same orbit are distinct for every x
∈
F
p
∗
∖
〈
ζ
〉.Proof.
Suppose thatx
k
i
=
x
k
j for 0
≤
i
,
j
<
d, i
≠
j. Writing this as x
k
i
-
k
j
=
1, we know p
-
1
∣
k
i
-
k
j. Since k
i
-
k
j
=
l
λ, where 0
≤
l
<
(
p
-
1
)
/
λ, notice that o
r
d
(
x
)
=
p
-
1; we have (
p
-
1
)
∣
l
λ. However, p
-
1
>
l
λ; this is a contradiction. Thus x
,
x
k
,
…
,
x
k
φ
(
d
)
-
1 are distinct for 0
≤
i
,
j
<
d, i
≠
j.Letζ be a generator of a cyclic group of fixed point. In the following we mainly discuss the relation between ζ
i
x
K and ζ
j
x
K under the condition g
c
d
(
λ
,
d
)
=
1 for all 0
≤
i
,
j
≤
λ
-
1 and i
≠
j, where ζ is a fixed point and x is a nonfixed point.Proposition 8.
LetK be a multiplicative subgroup of Z
p
-
1
∗ and ζ a generator of fixed point for λ
=
gcd
⁡
(
K
-
1
). If gcd
⁡
(
λ
,
d
)
=
1, then any two orbits ζ
i
x
K and ζ
j
x
K are disjoint for 0
≤
i
,
j
≤
λ
-
1, i
≠
j.Proof.
Any two orbitsζ
i
x
K and ζ
j
x
K are disjoint for 0
≤
i
,
j
≤
λ
-
1, i
≠
j. It is equivalent to (
ζ
i
x
K
)
∩
(
ζ
j
x
K
)
=
∅. Suppose that (
ζ
i
x
K
)
∩
(
ζ
j
x
K
)
≠
∅ for some i
,
j. This means that ζ
i
x
K
=
ζ
j
x
K and y
=
ζ
i
-
j
=
x
k
m
-
k
n, where k
m
,
k
n
∈
K. Since (
ζ
i
-
j
)
λ
=
1 and (
x
k
m
-
k
n
)
d
=
1 for x
∈
F
p
∗, the order of y divides both λ and d. Then it divides gcd
⁡
(
λ
,
d
)
=
1, from which it follows that y must be equal to 1. This is a contradiction, so ζ
i
x
K and ζ
j
x
K are disjoint. On the other hand, if i
=
j, there is natural ζ
i
x
K
=
ζ
j
x
K.From the above discussion, we conclude that two orbitsζ
i
x
K and ζ
j
x
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
n
f
p) and the fixed points (denoted as G
f
p). The group G can be expressed by G
=
G
n
f
p
∪
G
f
p, where ∪ denotes the disjoint union.The nonfixed points partG
n
f
p behaves just like an extended orbit. G
n
f
p can be partitioned by the disjoint union of distinct G
x
,
n
f
p, such as G
x
,
n
f
p
=
x
K
∪
ζ
x
K
∪
⋯
∪
ζ
λ
-
1
x
K where we choose x
∈
G as a nonfixed point representative element, and ζ
∈
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 elementsx
,
ζ
x
,
…
,
ζ
λ
-
1
x as the different representatives for distinct orbits. Obviously, any two orbits ζ
i
x
K and ζ
j
x
K are one-to-one correspondence, where 0
≤
i
,
j
<
λ. Thus any two orbits have the same cardinality.Hence, the cardinality ofG
x
,
n
f
p can be expressed by |
K
|
λ for x
∈
G. The order of G can be expressed by |
G
|
=
|
G
x
,
n
f
p
∪
G
f
p
|
=
(
|
K
|
+
1
)
λ for a non-fixed point x
∈
G and a fixed point ζ
∈
G.Example 9.
LetK
=
{
1,5
,
9,13,17,25
}
≤
Z
28
∗; define a map x
↦
x
k
i for k
=
5 and 0
≤
i
≤
5. We consider a group partition method on Z
71
∗. Then we have λ
=
4 disjoint orbits of length φ
(
d
)
=
6. Since there is one-to-one correspondence between any two orbits, the group Z
29
∗ can be divided as follows:(3)
2
K
=
2,3
,
19,14,21,11
,
4
K
=
25
×
2
K
=
4,9
,
13,22,6
,
5
,
7
K
=
70
×
2
K
=
7,16,20,25,24,23
,
8
K
=
57
×
2
K
=
8,27,15,18,10,26
.
So the cardinality of every orbit is|
K
|
=
|
2
K
|
=
|
4
K
|
=
|
7
K
|
=
|
8
K
|
=
6. We have 4 fixed points G
f
p
=
〈
12
〉
=
{
1,12,17,28
} and note that 1
4
≡
1
2
4
≡
1
7
4
≡
2
8
4
≡
1
mod
⁡
29. Obviously, G
n
f
p can be represented as G
n
f
p
=
2
K
∪
4
K
∪
7
K
∪
8
K. Thus Z
29
∗ can be partitioned by F
71
∗
=
Fix
⁡
(
K
)
∪
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 polynomialf
(
x
)
∈
F
p
[
x
] having the same value for the elements in the same orbit. We define a function f
(
x
) by(4)
f
x
≔
x
+
x
k
+
x
k
2
⋯
+
x
k
d
-
2
+
x
k
φ
d
-
1
∈
F
p
x
,where k
φ
(
d
)
≡
1
mod
⁡
(
p
-
1
). It implies that x
,
x
k
,
…
,
x
k
φ
(
d
)
-
1 are all distinct elements and that this sequence is repeated for further powers. Furthermore, we define the equivalence relation ~ on F
p
∗ as follows:(5)
x
~
x
,
x
k
,
…
,
x
k
φ
d
-
1
⟼
f
x
ζ
x
~
ζ
x
,
ζ
x
k
,
…
,
ζ
x
k
φ
d
-
1
⟼
ζ
f
x
⋮
ζ
λ
-
1
x
~
ζ
λ
-
1
x
,
ζ
λ
-
1
x
k
,
…
,
ζ
λ
-
1
x
k
φ
d
-
1
⟼
ζ
λ
-
1
f
x
,where ζ is a fixed point and ζ
i
x are the representatives of distinct orbits.This relation partitions the groupF
p
∗ into different equivalence classes, and each class contains φ
(
d
) elements. Obviously, any two equivalence classes, that is, 〈
ζ
i
x
〉 and 〈
ζ
j
x
〉, have one-to-one correspondence for all i
,
j and i
≠
j.Proposition 10.
LetK be multiplicative subgroup of Z
p
-
1
∗ and ζ a generator of fixed point. Then we have f
(
x
)
≡
f
(
x
k
)
≡
⋯
≡
f
(
x
k
φ
(
d
)
-
1
)
mod
⁡
p and f
(
ζ
i
x
)
≡
ζ
i
f
(
x
)
mod
⁡
p, where x
∈
F
p
∗
∖
〈
ζ
〉, k
∈
K, and 0
≤
i
≤
λ
-
1.Proof.
One hasζ
k
≡
ζ
mod
⁡
p for all k
∈
K; the orbit generated by ζ
i
x satisfies (
ζ
i
x
)
K
=
ζ
i
x
K for all 0
≤
i
≤
λ
-
1.


### 5.1. The Proposed Algorithm

Theorem 11.
LetG
=
〈
P
〉 be an additive cyclic group of prime order p with a generator P. Let K be a multiplicative subgroup of F
p
-
1
∗ with λ
=
gcd
⁡
(
K
-
1
). Suppose that a generator ζ of F
p
-
1
∗ and P
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P are given. Then α
∈
F
p
∗ can be computed in time 2
(
p
-
1
)
/
d
+
(
d
-
1
) group operations by using storage for (
p
-
1
)
/
d elements of G.Proof.
LetG
=
〈
P
〉 be an additive cyclic group generated by an element P of prime order p. Polynomial f
(
x
)
=
x
+
x
k
+
x
k
2
+
⋯
+
x
k
φ
(
d
)
-
1
mod
⁡
p has the same value for all elements in an orbit, and it is to say that f
(
α
)
≡
f
(
α
k
)
≡
⋯
≡
f
(
α
k
φ
(
d
)
-
1
)
mod
⁡
p, where k
,
k
2
,
…
,
k
φ
(
d
)
-
1
∈
K and α
∈
F
p
∗.
GivenP
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G, we first compute f
(
α
)
P
=
α
P
+
α
k
P
⋯
+
α
k
φ
(
d
)
-
1
P
∈
G. Then we randomly choose a nonfixed element β from F
p
∗ and evaluate f
(
x
) at β. There exist nonnegative integers 0
≤
i
,
j
≤
λ
-
1 such that ζ
t
f
(
α
)
=
f
(
β
).
If we takem
=
(
p
-
1
)
/
d, t can be expressed in a unique manner as t
=
m
v
+
u, where 0
≤
u
,
v
<
m. This implies that (6)
ζ
m
v
f
α
=
ζ
-
u
f
β
.
Sincef
(
α
) is unknown value, in practice, we search for integers u and v that satisfy(7)
ζ
m
v
f
α
P
=
ζ
-
u
f
β
P
.
In order to find sucht, we use Baby-Step Giant-Step [1] method. We construct a lookup table, which contains all the pairs (
ζ
-
u
f
(
β
)
P
,
u
) for 0
≤
u
<
m, and we sort the table by the first component. Then we compute ζ
m
v
f
(
α
)
P for each 0
≤
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 2
m group operations by using storage for m elements of G. Then t can be found.
There isζ
t
f
(
α
)
P
=
f
(
β
)
P or equivalently f
(
ζ
t
α
)
P
=
f
(
β
)
P. Since the kth power of any point is still in the same orbit, there exists an integer k
l
∈
K such that ζ
t
α
P
=
β
k
l
P. We compute β
k
i
P and compare with ζ
t
α
P in G, where 0
≤
i
≤
λ
-
1. This gives α
=
ζ
-
t
·
β
k
l.We briefly describe this method in Algorithm12. The algorithm is probabilistic, in which β
∈
F
p
∗ satisfies ζ
t
f
(
α
)
P
=
f
(
β
)
P for our attack. Since all elements of group F
p
∗ can be represented by fixed point and nonfixed point, the probability that a random element β
∈
F
p
∗ is a nonfixed point is φ
(
d
)
λ
/
p
=
1
-
λ
/
p, which is sufficiently large.Algorithm 12 (a new algorithm to ECDLP with auxiliary inputs).
Consider the following:Input: let{
P
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G
}, {
k
,
k
2
,
…
,
k
φ
(
d
)
-
1
∈
K
}, and ξ a primitive element in F
p, f
(
x
)
=
x
+
x
k
+
x
k
2
⋯
+
x
k
φ
(
d
)
-
1;
Output:α
∈
F
p
∗:
(1) Set ζ
←
ξ
d,
(2) [Step 1] Compute f
(
α
)
P
=
α
P
+
α
k
P
⋯
+
α
k
φ
(
d
)
-
1
P,
(3) Randomly choose β
∈
F
p
∗ and compute f
(
β
)
P
=
(
β
+
β
k
⋯
+
β
k
φ
(
d
)
-
1
)
P,
(4) [Step 2] m
←
λ,
(5) Find 0
≤
u
,
v
<
m, such that ζ
m
v
f
(
α
)
P
=
ζ
-
u
f
(
β
)
P,
(6) In case of failure, return to line 3 until t
←
m
v
+
u,
(7) [Step 3] Find k
l
∈
K
,
0
<
l
<
φ
(
d
) such that ζ
t
α
P
=
β
k
l
P,
(8) Output α
=
ζ
-
t
·
β
k
l
.In summary, ifP
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P and multiplicative group K are given, the proposed algorithm computes α approximately in O
(
(
p
-
1
)
/
d
+
d
) group operations with storage O
(
(
p
-
1
)
/
d
) in G.


## 5.1. The Proposed Algorithm

Theorem 11.
LetG
=
〈
P
〉 be an additive cyclic group of prime order p with a generator P. Let K be a multiplicative subgroup of F
p
-
1
∗ with λ
=
gcd
⁡
(
K
-
1
). Suppose that a generator ζ of F
p
-
1
∗ and P
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P are given. Then α
∈
F
p
∗ can be computed in time 2
(
p
-
1
)
/
d
+
(
d
-
1
) group operations by using storage for (
p
-
1
)
/
d elements of G.Proof.
LetG
=
〈
P
〉 be an additive cyclic group generated by an element P of prime order p. Polynomial f
(
x
)
=
x
+
x
k
+
x
k
2
+
⋯
+
x
k
φ
(
d
)
-
1
mod
⁡
p has the same value for all elements in an orbit, and it is to say that f
(
α
)
≡
f
(
α
k
)
≡
⋯
≡
f
(
α
k
φ
(
d
)
-
1
)
mod
⁡
p, where k
,
k
2
,
…
,
k
φ
(
d
)
-
1
∈
K and α
∈
F
p
∗.
GivenP
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G, we first compute f
(
α
)
P
=
α
P
+
α
k
P
⋯
+
α
k
φ
(
d
)
-
1
P
∈
G. Then we randomly choose a nonfixed element β from F
p
∗ and evaluate f
(
x
) at β. There exist nonnegative integers 0
≤
i
,
j
≤
λ
-
1 such that ζ
t
f
(
α
)
=
f
(
β
).
If we takem
=
(
p
-
1
)
/
d, t can be expressed in a unique manner as t
=
m
v
+
u, where 0
≤
u
,
v
<
m. This implies that (6)
ζ
m
v
f
α
=
ζ
-
u
f
β
.
Sincef
(
α
) is unknown value, in practice, we search for integers u and v that satisfy(7)
ζ
m
v
f
α
P
=
ζ
-
u
f
β
P
.
In order to find sucht, we use Baby-Step Giant-Step [1] method. We construct a lookup table, which contains all the pairs (
ζ
-
u
f
(
β
)
P
,
u
) for 0
≤
u
<
m, and we sort the table by the first component. Then we compute ζ
m
v
f
(
α
)
P for each 0
≤
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 2
m group operations by using storage for m elements of G. Then t can be found.
There isζ
t
f
(
α
)
P
=
f
(
β
)
P or equivalently f
(
ζ
t
α
)
P
=
f
(
β
)
P. Since the kth power of any point is still in the same orbit, there exists an integer k
l
∈
K such that ζ
t
α
P
=
β
k
l
P. We compute β
k
i
P and compare with ζ
t
α
P in G, where 0
≤
i
≤
λ
-
1. This gives α
=
ζ
-
t
·
β
k
l.We briefly describe this method in Algorithm12. The algorithm is probabilistic, in which β
∈
F
p
∗ satisfies ζ
t
f
(
α
)
P
=
f
(
β
)
P for our attack. Since all elements of group F
p
∗ can be represented by fixed point and nonfixed point, the probability that a random element β
∈
F
p
∗ is a nonfixed point is φ
(
d
)
λ
/
p
=
1
-
λ
/
p, which is sufficiently large.Algorithm 12 (a new algorithm to ECDLP with auxiliary inputs).
Consider the following:Input: let{
P
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G
}, {
k
,
k
2
,
…
,
k
φ
(
d
)
-
1
∈
K
}, and ξ a primitive element in F
p, f
(
x
)
=
x
+
x
k
+
x
k
2
⋯
+
x
k
φ
(
d
)
-
1;
Output:α
∈
F
p
∗:
(1) Set ζ
←
ξ
d,
(2) [Step 1] Compute f
(
α
)
P
=
α
P
+
α
k
P
⋯
+
α
k
φ
(
d
)
-
1
P,
(3) Randomly choose β
∈
F
p
∗ and compute f
(
β
)
P
=
(
β
+
β
k
⋯
+
β
k
φ
(
d
)
-
1
)
P,
(4) [Step 2] m
←
λ,
(5) Find 0
≤
u
,
v
<
m, such that ζ
m
v
f
(
α
)
P
=
ζ
-
u
f
(
β
)
P,
(6) In case of failure, return to line 3 until t
←
m
v
+
u,
(7) [Step 3] Find k
l
∈
K
,
0
<
l
<
φ
(
d
) such that ζ
t
α
P
=
β
k
l
P,
(8) Output α
=
ζ
-
t
·
β
k
l
.In summary, ifP
,
α
P
,
α
k
P
,
…
,
α
k
φ
(
d
)
-
1
P and multiplicative group K are given, the proposed algorithm computes α approximately in O
(
(
p
-
1
)
/
d
+
d
) group operations with storage O
(
(
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 groupG with 61-bit order.


### 6.1. Parameters

We use an addition cyclic groupG
=
〈
P
〉 with order p on an elliptic curve y
2
+
x
y
=
x
3
+
x
2
+
415485412408256448 defined over a binary finite field F
2
61. Concrete values of these parameters are summarized in the following:(i)
q
=
0
x
2000000000000000
61
-
bit
=
2
61,
(ii)
#
E
=
0
x
1
F
F
F
F
F
F
F
F
35
A
B
90
A
(
61
-
bit
)
=
2305843009001535754
=
2
×
1152921504500767877,
(iii)
p
=
0
x
F
F
F
F
F
F
F
F
9
A
D
5
C
85
(
61
-
bit
)
=
1152921504500767877,
(iv)
p
-
1
=
0
x
F
F
F
F
F
F
F
F
9
A
D
5
C
84
(
61
-
bit
)
=
2
2
×
7
×
1213
×
33945398201059, where #
E denotes the number of points in E
F
2
61. In the implementation of our new algorithm, we use the following parameters: (i)
λ
=
950471149629652
(
50
-
bit
),
(ii)
λ
=
30829713
(
25
-
bit
),
(iii)
k
=
1900942299259305,
(iv)
d
=
1213, |
K
|
=
1212, K
=
{
k
i
∣
i
∈
[
0,1211
]
},
(v)
G
f
p
=
〈
ζ
〉
=
〈
917376305973559977
〉 and |
G
f
p
|
=
λ.Here,d is chosen to minimize the time complexity of our algorithm. The element ζ is chosen as the generator of the multiplicative group G
f
p. A base point P is randomly chosen from points in E
(
F
q
) with order p. Given the coordinate of P
,
P
1
=
α
P
,
P
2
=
α
k
P
,
P
3
=
α
k
2
P
,
…
,
P
1212
=
α
k
1211
P, the corresponding values for x and y are as follows:(8)
x
P
=
0
x
15934
F
D
A
439710
F
D
,
y
P
=
0
x
23394044
E
191
A
D
5
x
P
1
=
0
x
1
E
B
F
B
F
5362
E
A
038
C
,
y
P
1
=
0
x
1499
B
155
A
750
C
E
2
C
x
P
2
=
0
x
1
A
8
D
E
21
E
255
B
38
F
8
,
y
P
2
=
0
x
1
A
16
E
1
F
6
A
5367
A
3
B
⋮
x
P
1212
=
0
x
2
C
878114
B
D
6109
E
,
y
P
1212
=
0
x
11
C
28
E
A
554
F
98437
.


### 6.2. Results

In this experiment, we randomly choose an elementβ
=
916588465071928542.Step 1.
We computef
(
α
)
P
=
α
P
+
α
k
P
+
⋯
+
α
k
1211
P and f
(
β
)
P
=
(
β
+
β
k
+
⋯
+
β
k
1211
)
P as follows:(9)
x
f
α
P
=
0
x
F
18
B
C
6972
D
D
660
F
,
y
f
α
P
=
0
x
103
F
35553
C
14
D
081
,
x
f
β
P
=
0
x
16983
D
29
C
E
603
A
F
0
,
y
f
β
P
=
0
x
13
E
3
C
F
104
F
63
D
01
D
.Step 2.
We search for the integer0
≤
t
<
λ such that (10)
ζ
t
·
f
α
P
=
f
β
P
.
It is equivalent to searching for integer0
≤
u
,
v
<
λ, such that (11)
ζ
λ
v
·
f
α
P
=
ζ
-
u
·
f
β
P
.
We establish two databasesD
B
L
=
{
ζ
i
λ
v
·
f
(
α
)
P
} and D
B
R
=
{
ζ
-
j
·
f
(
β
)
P
}. To establish database D
B
R, we have to compute and store the following points:(12)
ζ
-
0
·
f
β
P
,
ζ
-
1
·
f
β
P
,
ζ
-
2
·
f
β
P
,
…
,
ζ
-
λ
-
1
·
f
β
P
.
In order to reduce the storage space, we use the point compression technique as [18]. Each point ζ
-
j
·
f
(
β
)
P is digested as L
S
B
64
(
M
D
5
(
x
(
P
)
∥
y
(
P
)
)
), so each point needs 8 bytes.
Thus,λ
×
8
=
246637704 bytes (≈235.2 Mbytes) is required for D
B
R, and about 6.5 hours is required in total (on Pentium® Dual-Core CPU E5700 3.00 GHz). To establish database D
B
L,(13)
ζ
0
·
λ
·
f
α
P
,
ζ
1
·
λ
·
f
α
P
,
ζ
2
·
λ
·
f
α
P
,
…
,
ζ
λ
-
1
·
λ
·
f
α
Pwere computed and stored. With the same space saving technique, λ
×
8
=
246637704 bytes (≈235.2 Mbytes) was required for D
B
L, and 6.5 hours was required in total.
Then, a collisionζ
λ
v
·
f
(
α
)
P
=
ζ
-
u
·
f
(
β
)
P between two databases D
B
L and D
B
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 (14)
t
=
λ
v
+
u
=
215808226 can be found.Step 3.
To findα, we have known an integer t that satisfies ζ
t
·
f
(
α
)
P
=
f
(
β
)
P; it is equivalent to ζ
t
·
α
P
=
β
k
l
P for 0
≤
l
≤
1211. Locate ζ
t
·
α
P from the set {
β
k
l
P
} to find 0
≤
l
≤
1211 such that ζ
t
·
α
P
=
β
k
l
P. Finally, we succeed in finding a solution α
=
ζ
-
t
·
β
k
l
=
1073972411177481784 for l
=
1093.


## 6.1. Parameters

We use an addition cyclic groupG
=
〈
P
〉 with order p on an elliptic curve y
2
+
x
y
=
x
3
+
x
2
+
415485412408256448 defined over a binary finite field F
2
61. Concrete values of these parameters are summarized in the following:(i)
q
=
0
x
2000000000000000
61
-
bit
=
2
61,
(ii)
#
E
=
0
x
1
F
F
F
F
F
F
F
F
35
A
B
90
A
(
61
-
bit
)
=
2305843009001535754
=
2
×
1152921504500767877,
(iii)
p
=
0
x
F
F
F
F
F
F
F
F
9
A
D
5
C
85
(
61
-
bit
)
=
1152921504500767877,
(iv)
p
-
1
=
0
x
F
F
F
F
F
F
F
F
9
A
D
5
C
84
(
61
-
bit
)
=
2
2
×
7
×
1213
×
33945398201059, where #
E denotes the number of points in E
F
2
61. In the implementation of our new algorithm, we use the following parameters: (i)
λ
=
950471149629652
(
50
-
bit
),
(ii)
λ
=
30829713
(
25
-
bit
),
(iii)
k
=
1900942299259305,
(iv)
d
=
1213, |
K
|
=
1212, K
=
{
k
i
∣
i
∈
[
0,1211
]
},
(v)
G
f
p
=
〈
ζ
〉
=
〈
917376305973559977
〉 and |
G
f
p
|
=
λ.Here,d is chosen to minimize the time complexity of our algorithm. The element ζ is chosen as the generator of the multiplicative group G
f
p. A base point P is randomly chosen from points in E
(
F
q
) with order p. Given the coordinate of P
,
P
1
=
α
P
,
P
2
=
α
k
P
,
P
3
=
α
k
2
P
,
…
,
P
1212
=
α
k
1211
P, the corresponding values for x and y are as follows:(8)
x
P
=
0
x
15934
F
D
A
439710
F
D
,
y
P
=
0
x
23394044
E
191
A
D
5
x
P
1
=
0
x
1
E
B
F
B
F
5362
E
A
038
C
,
y
P
1
=
0
x
1499
B
155
A
750
C
E
2
C
x
P
2
=
0
x
1
A
8
D
E
21
E
255
B
38
F
8
,
y
P
2
=
0
x
1
A
16
E
1
F
6
A
5367
A
3
B
⋮
x
P
1212
=
0
x
2
C
878114
B
D
6109
E
,
y
P
1212
=
0
x
11
C
28
E
A
554
F
98437
.


## 6.2. Results

In this experiment, we randomly choose an elementβ
=
916588465071928542.Step 1.
We computef
(
α
)
P
=
α
P
+
α
k
P
+
⋯
+
α
k
1211
P and f
(
β
)
P
=
(
β
+
β
k
+
⋯
+
β
k
1211
)
P as follows:(9)
x
f
α
P
=
0
x
F
18
B
C
6972
D
D
660
F
,
y
f
α
P
=
0
x
103
F
35553
C
14
D
081
,
x
f
β
P
=
0
x
16983
D
29
C
E
603
A
F
0
,
y
f
β
P
=
0
x
13
E
3
C
F
104
F
63
D
01
D
.Step 2.
We search for the integer0
≤
t
<
λ such that (10)
ζ
t
·
f
α
P
=
f
β
P
.
It is equivalent to searching for integer0
≤
u
,
v
<
λ, such that (11)
ζ
λ
v
·
f
α
P
=
ζ
-
u
·
f
β
P
.
We establish two databasesD
B
L
=
{
ζ
i
λ
v
·
f
(
α
)
P
} and D
B
R
=
{
ζ
-
j
·
f
(
β
)
P
}. To establish database D
B
R, we have to compute and store the following points:(12)
ζ
-
0
·
f
β
P
,
ζ
-
1
·
f
β
P
,
ζ
-
2
·
f
β
P
,
…
,
ζ
-
λ
-
1
·
f
β
P
.
In order to reduce the storage space, we use the point compression technique as [18]. Each point ζ
-
j
·
f
(
β
)
P is digested as L
S
B
64
(
M
D
5
(
x
(
P
)
∥
y
(
P
)
)
), so each point needs 8 bytes.
Thus,λ
×
8
=
246637704 bytes (≈235.2 Mbytes) is required for D
B
R, and about 6.5 hours is required in total (on Pentium® Dual-Core CPU E5700 3.00 GHz). To establish database D
B
L,(13)
ζ
0
·
λ
·
f
α
P
,
ζ
1
·
λ
·
f
α
P
,
ζ
2
·
λ
·
f
α
P
,
…
,
ζ
λ
-
1
·
λ
·
f
α
Pwere computed and stored. With the same space saving technique, λ
×
8
=
246637704 bytes (≈235.2 Mbytes) was required for D
B
L, and 6.5 hours was required in total.
Then, a collisionζ
λ
v
·
f
(
α
)
P
=
ζ
-
u
·
f
(
β
)
P between two databases D
B
L and D
B
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 (14)
t
=
λ
v
+
u
=
215808226 can be found.Step 3.
To findα, we have known an integer t that satisfies ζ
t
·
f
(
α
)
P
=
f
(
β
)
P; it is equivalent to ζ
t
·
α
P
=
β
k
l
P for 0
≤
l
≤
1211. Locate ζ
t
·
α
P from the set {
β
k
l
P
} to find 0
≤
l
≤
1211 such that ζ
t
·
α
P
=
β
k
l
P. Finally, we succeed in finding a solution α
=
ζ
-
t
·
β
k
l
=
1073972411177481784 for l
=
1093.


## 7. Conclusion

In this paper, we propose a new ECDLP-wAI and give an algorithm to solve the ECDLP efficiently. When given some pointsP
,
α
P
,
α
k
P
,
α
k
2
P
,
α
k
3
P
,
…
,
α
k
φ
(
d
)
-
1
P
∈
G and multiplicative cyclic group K, our new algorithm can recover the secret key α
∈
F
p
∗ in O
(
(
p
-
1
)
/
d
+
d
) group operations by using O
(
(
p
-
1
)
/
d
) storage, where k is a generator of K and φ
(
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.



---

*Source: 5361695-2016-06-28.xml*