Cryptography Reference
In-Depth Information
for some
g
1
(
x
)
,g
2
(
x
)
∈ Z
[
x
]. It follows from Lemma
26.3.16
that, for some
c
∈ N
a
T
(
Q,P
)
cg
1
(
s
)
ˆ
t
r
(
Q,P
)
g
2
(
s
)
a
s,h
(
x
)
(
Q,P
)
=
and so
a
s,h
(
x
)
is a bilinear pairing on
G
2
×
G
1
.
Finally, we need to prove non-degeneracy. By assumption,
r
2
(
s
k
|
−
1) and so, in the
version of Theorem
26.3.13
of Exercise
26.3.14
,
r
|
L
. It follows that
a
T
(
Q,P
)
=
1. Hence,
ˆ
t
r
(
Q,P
)
g
2
(
s
)
. To complete the proof, note that
g
2
(
s
)
a
s,h
(
x
)
(
Q,P
)
=
=
h
(
s
)
/r
, and so
a
s,h
(
x
)
is non-degenerate if and only if
r
2
h
(
s
).
Hess [
257
] explains that this construction is “complete” in the sense that every bilinear
map coming from functions in a natural class must correspond to some polynomial
h
(
x
).
Hess also proves that any polynomial
h
(
x
)
=
i
=
0
h
i
x
i
∈ Z
[
x
] satisfying the required
conditions is such that
i
=
0
|
r
1
/ϕ
(
k
)
. Polynomials
h
(
x
) that have one coefficient of
size
r
1
/ϕ
(
k
)
and all other coefficients small satisfy the optimality conjecture. Good choices for
the polynomial
h
(
x
) are found by considering exactly the same lattice as in equation (
26.8
)
(though in [
257
] it is written with
q
replaced by
s
).
h
i
|≥
26.4 Reduction of ECDLP to finite fields
An early application of pairings in elliptic curve cryptography was to reduce the discrete
logarithm problem in
E
(
F
q
)[
n
], when gcd(
n,q
)
=
1, to the discrete logarithm problem in
the multiplicative group of a finite extension of
F
q
. Menezes, Okamoto and Vanstone [
375
]
used the Weil pairing to achieve this, while Frey and Ruck [
196
] used the reduced Tate-
Lichtenbaum pairing. The case gcd(
n,q
)
1 will be handled in Section
26.4.1
.
The basic idea is as follows: given an instance
P
,
Q
=
=
[
a
]
P
of the discrete logarithm
problem in
E
(
F
q
)[
n
] and a non-degenerate bilinear pairing
e
, one finds a point
R
∈
E
(
F
q
)
z
a
in
µ
n
⊆ F
q
k
where
k
such that
z
k
(
q,n
)is
the embedding degree. When
q
is a prime power that is not prime then there is the possibility
that
µ
r
lies in a proper subfield of
=
e
(
P,R
)
=
1. It follows that
e
(
Q,R
)
=
=
F
q
k
, in which case re-define
k
to be the smallest positive
F
q
) containing
µ
n
.
The point is that if
k
is sufficiently small then index calculus algorithms in
F
q
k
is the smallest field of characteristic char(
rational number such that
F
q
k
could be
faster than the baby-step-giant-step or Pollard rho algorithms in
E
(
F
q
)[
n
]. Hence, one has
reduced the discrete logarithm problem to a potentially easier problem. The reduction of
the DLP from
E
(
F
q
k
is called the
MOV/FR attack
.
Menezes, Okamoto and Vanstone [
375
] suggested to use the Weil pairing for the above
idea. In this case, the point
R
can, in principle, be defined over a large extension of
F
q
) to a subgroup of
F
q
.Frey
and R uck explained that the Tate-Lichtenbaum pairing is a more natural choice, since it is
sufficient to take a suitable point
R
k
(
q,n
) is the embedding degree.
Balasubramanian and Koblitz [
25
] showed that, in most cases, it is also sufficient to work
in
E
(
∈
E
(
F
q
k
) where
k
=
F
q
k
) when using the Weil pairing.
