Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 171

LEMMA 6.1
A ssu m e 3

n .If P ∈ E ( F q ) has order exactly n ,then e n ( P, P ) isaprimitive

n throotofunity.

PROOF Suppose uP = vβ ( P ) for some integers u, v .Then

β ( vP )= vβ ( P )= uP ∈ E ( F q ) .

If vP = ∞ ,then uP = ∞ ,so u ≡ 0(mod n ). If vP = ∞ ,write vP =( x, y )

with x, y ∈ F q .Then

( ωx, y )= β ( vP ) ∈ E ( F q ) .

Since ω ∈ F q ,wemusthave x = 0. Therefore vP =(0 , ± 1), which has order
3. This is impossible since we have assumed that 3 n . It follows that the
only relation of the form uP = vβ ( P )has u, v ≡ 0(mod n ), so P and β ( P )
form a basis of E [ n ]. By Corollary 3.10, e n ( P, P )= e n ( P, β ( P )) is a primitive
n th root of unity.

Suppose now that we know P, aP, bP, Q and we want to decide whether or
not Q = abP . First, use the usual Weil pairing to decide whether or not Q is a
multiple of P . By Lemma 5.1, Q is a multiple of P if and only if e n ( P, Q )=1.
Assume this is the case, so Q = tP for some t .Wehave

e n ( aP, bP )= e n ( P, P ) ab = e n ( P, abP ) d e n ( Q, P )= e n ( P, P ) t .

Assume 3 n .Then e n ( P, P ) is a primitive n th root of unity, so

Q = abP ⇐⇒ t ≡ ab (mod n ) ⇐⇒ e n ( aP, bP )= e n ( Q, P ) .

This solves the Decision Die-Hellman problem in this case. Note that we
did not need to compute any discrete logs, even in finite fields. All that was
needed was to compute the Weil pairing.
The above method was pointed out by Joux and Nguyen. For more on the
Decision Di e-Hellman problem, see [13].
Joux [56] (see also [124]) has given another application of the modified
Weil pairing to what is known as tripartite Di e-Hellman key exchange.
Suppose Alice, Bob, and Chris want to establish a common key. The standard
Die-Hellman procedure requires two rounds of interaction. The modified
Weil pairing allows this to be cut to one round. As above, let E be the curve
y 2 = x 3 +1 over F q ,where q ≡ 2(mod3). Let P be a point of order n .
Usually, n should be chosen to be a large prime. Alice, Bob, and Chris do the
following.

1. Alice, Bob, and Chris choose secret integers a, b, c mod n , respectively.

2. Alice broadcasts aP , Bob broadcasts bP , and Chris broadcasts cP .