Cryptography Reference
In-Depth Information
Weil pairing is alternating and so
e
r
(
P,P
)
=
1. It follows from the non-degeneracy of the
pairing that
e
r
(
P,Q
)
. The Weil pairing also shows that one can
only have two independent points when
r
divides (
q
=
1 if and only if
Q
∈
P
−
1).
F
q
)), the group structure can be determined
using a randomised algorithm due to Miller [
383
,
385
]. We present this algorithm in
Algorithm
9
. Note that the algorithm of Theorem
2.15.10
is used in lines 7 and 10. The
expected running time is polynomial, but we refer to Miller [
385
] for the details.
Given the factorisation of gcd(
q
−
1
,
#
E
(
Algorithm 9
Miller's algorithm for group structure
INPUT:
E/
F
q
,
N
0
,N
1
∈ N
F
q
)
=
and
the
factorisation
of
N
0
,
where
#
E
(
N
0
N
1
,
−
=
−
gcd(
N
1
,q
1)
1 and all primes dividing
N
0
divide
q
1
F
q
)
=
OUTPUT: Integers
m
and
n
such that
E
(
(
Z
/m
Z
)
×
(
Z
/n
Z
) as a group
1:
Write
N
0
=
i
=
1
l
e
i
where
l
1
,...,l
k
are distinct primes
i
2:
For all 1
≤
i
≤
k
such that
e
i
=
1set
N
0
=
N
0
/l
i
,N
1
=
N
1
l
i
3:
m
=
1,
n
=
1
4:
while
mn
=
N
0
do
Choose random points
P
,Q
∈
E
(
F
q
)
5:
[
N
1
]
P
,
Q
[
N
1
]
Q
P
=
=
6:
Find the exact orders
m
and
n
of
P
and
Q
7:
lcm(
m
,n
)
n
=
8:
α
=
e
n
(
P,Q
)
9:
∈ F
q
:
z
n
Let
m
be the exact order of
α
in
µ
n
={
z
=
1
}
10:
11:
end while
12:
return
m
and
nN
1
Exercise 11.5.1
Show that Algorithm
9
is correct.
Exercise 11.5.2
Modify Algorithm
9
so that it outputs generators for
E
(
F
q
).
Kohel and Shparlinski [
317
] give a deterministic algorithm to compute the group struc-
ture and to find generators for
E
(
F
q
). Their algorithm requires
O
(
q
1
/
2
+
) bit operations.
11.6 Testing subgroup membership
In many cryptographic protocols, it is necessary to verify that the elements received really
do correspond to group elements with the right properties. There are a variety of attacks
that can be performed otherwise, some of which are briefly mentioned in Section
20.4.2
.
The first issue is whether a binary string corresponds to an element of the “parent group”
= F
q
. In the case of elliptic curves, one
must parse the bitstring as a point (
x,y
) and determine that (
x,y
) does satisfy the curve
equation.
G
(
F
q
). This is usually easy to check when
G
(
F
q
)
