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

6. Alice and Bob use some publicly agreed on method to extract a key from
abP . For example, they could use the last 256 bits of the x -coordinate
of abP as the key. Or they could evaluate a hash function at the x -
coordinate.

The only information that the eavesdropper Eve sees is the curve E , the finite
field F q ,andthepoints P , aP ,and bP . She therefore needs to solve the
following:

DIFFIE-HELLMAN PROBLEM
Given P , aP ,and bP in E ( F q ) , com pute abP .

If Eve can solve discrete logs in E ( F q ), then she can use P and aP to find
a . Then she can compute a ( bP )toget abP . However, it is not known whether
there is some way to compute abP without first solving a discrete log problem.
A related question is the following:

DECISION DIFFIE-HELLMAN PROBLEM
Given P , aP ,and bP in E ( F q ) ,andgiven a point Q

∈ E ( F q ) determ ine

whetherornot Q = abP .

In other words, if Eve receives an anonymous tip telling her abP ,canshe
verify that the information is correct?
The Di e-Hellman problem and the Decision Di e-Hellman problem can
be asked for arbitrary groups. Originally, they appeared in the context of
multiplicative groups F q of finite fields.
For elliptic curves, the Weil pairing can be used to solve the Decision Die-
Hellman problem in some cases. We give one such example.
Let E be the curve y 2 = x 3 +1 over F q ,where q 2 (mod 3). By Proposi-

tion 4.33, E is supersingular. Let ω ∈ F q 2 be a primitive third root of unity.
Note that ω ∈ F q since the order of F q is q − 1, which is not a multiple of 3.
Define a map

≡

β : E ( F q ) → E ( F q ) , ( x, y ) → ( ωx, y ) , β ( ∞ )= ∞ .

It is straightforward to show, using the formulas for the addition law, that β
is an isomorphism (E xercise 6.1).
Suppose P ∈ E ( F q ) has order n .Then β ( P ) also has order n . Define the
modified Weil pairing

e n ( P 1 ,P 2 )= e n ( P 1 ,β ( P 2 )) ,

where e n is the usual Weil pairing and P 1 ,P 2 ∈ E [ n ].