Cryptography Reference
In-Depth Information
degree. Let
E
(
F
q
)
[
r
]
denote the subgroup of
E
(
F
q
)
of all points of order dividing
r
, and similarly for the degree
k
extension of
F
q
.
To support a description of the attacks we outline parametrizations of, and algo-
rithms for several, concrete pairings. However, we let
e
: G
1
× G
2
−→ G
T
g
enerically denote such a pairing, whose specific type is determined by the context;
e
denotes the same pairing wherein some fault occurs or is injected. The two groups
G
1
and
G
2
will be subgroups of elliptic curve groups, whereas
G
T
is a subgroup of
the multiplicative group of a finite field.
All currently known pairings evaluate a combination of so-called “Miller func-
tions”, written
f
n
,
P
(
·
)
G
2
. Such a
function is defined as a ratio of two bivariate polynomials, and can be evaluated at an
elliptic curve point
Q
to yield a resulting finite field element. As is the case for ratios
of univariate polynomials, such a function is uniquely determined (up to multiplica-
tion by a constant) by its zeroes and poles and their respective multiplicities. This
information is precisely contained in the divisor of a function, namely the formal
sum of the zeroes and poles with multiplicities. A Miller function
f
n
,
P
satisfies
for a given scalar
n
and a point
P
, in either
G
1
or
div
(
f
n
,
P
)
=
n
(
P
)
−
(
[
n
]
P
)
−
(
n
−
1
)O,
i.e., the function has a zero at
P
of order
n
, a pole of order 1 at the point
[
n
]
P
and a
pole of order
n
.
Miller [286] described an efficient procedure to compute any function
f
n
,
P
and
evaluate it at an elliptic curve point. The crucial ingredient is a simple “double-and-
add” strategy based on the following observation: let
i
and
j
be positive integers;
then
−
1at
O
l
[
i
]
P
,
[
j
]
P
v
f
i
+
j
,
P
=
f
i
,
P
·
f
j
,
P
·
P
,
(13.1)
[
i
+
j
]
where
l
[
i
]
P
,
[
j
]
P
is the equation of the line through
[
i
]
P
and
[
j
]
P
(or the tangent line
[
]
=[
]
[
+
]
when
P
.
The resulting algorithm is described in Algorithm 13.1. Scott [364] gives an overview
various approaches to optimization of the algorithm, an important example being the
denominator elimination approach due to Barreto et al. [25]; this allows removal
(assuming a suitable parametrization) of the computationally expensive inversions
otherwise required during updates to the Miller variable
f
.
i
P
j
P
), and
v
[
i
+
j
]
P
is the equation of the vertical line through
i
j
13.2.1 The Weil Pairing
The Weil pairing was introduced by Weil [287, 418] in 1940 in his proof of the
Riemann hypothesis for curves. The simplified definition is as follows: let
E
be an
elliptic curve over
F
q
and let
P
,
Q
∈
E
(
F
q
k
)
[
r
]
with
P
=
Q
; then
