Cryptography Reference
In-Depth Information
Algorithm 13.2:
The Duursma-Lee algorithm
Input
:
P
=
(
x
P
,
y
P
)
∈
G
1
and
Q
=
(
x
Q
,
y
Q
)
∈
G
2
Output
:
e
(
P
,
Q
)
∈
G
T
1
f
←
1
2
for
i
=
1
upto
m
do
3
x
P
,
y
P
y
P
x
P
←
←
μ
←
x
P
+
x
Q
+
b
4
2
λ
←−
y
P
y
Q
σ
−
μ
5
2
g
←
λ
−
μρ
−
ρ
6
f
←
f
·
g
7
x
1
/
3
Q
y
1
/
3
Q
x
Q
←
,
y
Q
←
8
9
end
10
return
f
q
3
−
1
reduced Tate pairing when the arguments are restricted to a cleverly chosen domain,
i.e., the eigenspaces of Frobenius.
Duursma and Lee [129] introduced an approach to evaluation using a family of
hyperelliptic curves that includes supersingular curves over finite fields of charac-
teristic 3. For
3
m
F
q
with
q
=
and
k
=
6, suitable curves are defined by an equation
of the form
y
2
x
3
E
:
=
−
x
+
b
3
2
with
b
=±
1
∈ F
3
.If
F
q
3
= F
q
[
ρ
]
/(ρ
−
ρ
−
b
)
, and
F
q
6
= F
q
3
[
σ
]
/(σ
+
1
)
,
then the distortion map
φ
:
E
(
F
q
)
→
E
(
F
q
6
)
is defined by
φ(
x
,
y
)
=
(ρ
−
x
,σ
y
)
.
Then, setting
G
1
= G
2
=
E
(
F
3
m
)
and
G
T
= F
q
6
, Algorithm 13.2 computes an
admissible, symmetric pairing.
13.2.3 The
η
and
η
G
Pairings
Barreto et al. [26] introduced the
pairing by generalizing the Duursma-Lee
approach to allow use of supersingular curves over finite fields of any small char-
acteristic; Kwon [246] independently used the same approach, and in both cases
characteristic 2 is of specific interest. The
η
pairing already has a simple final power-
ing, but work by Galbraith et al. [151] (see [312, Sect. 5.4]) demonstrates that it can
be eliminated entirely; the crucial difference is the lack of normal denominator elim-
ination, which is enabled by evaluation of additional line functions. Interestingly,
analysis of the approach demonstrates no negative security implication in terms of
pairing inversion and so on. We follow Whelan and Scott [420] by terming this
approach the
η
η
G
pairing.
2
m
For
F
q
with
q
=
and
k
=
4, suitable curves are defined by an equation of the
form
