Cryptography Reference
In-Depth Information
more,
G
2
is now instantiated with a very specific subgroup of
E
(
F
q
k
)
[
r
]
, namely the
q
-eigenspace of Frobenius, i.e.,
x
q
y
q
G
2
={
(
x
,
y
)
∈
E
(
F
q
k
)
[
r
]|
(
,
)
=[
q
]
(
x
,
y
)
}
.
The definition then is very similar to the reduced Tate pairing: let
T
=
q
−
#
E
(
F
q
)
;
then the reduced ate pairing is
q
k
−
1
r
e
a
(
ˆ
P
,
Q
)
=
f
T
,
Q
(
P
)
.
After its invention, several other variants of the ate pairing were introduced in [170,
250, 274, 434], finally culminating in the notion of optimal pairing [180, 407] but
all have the same structure: all compute a (product of) Miller functions followed by
a final powering.
13.3 Attacks
In the following, we outline (in chronological order) attacks that represent the state
of the art in this field; the attacks can be roughly categorized as injecting faults into
either
1. the parametrization, specifically the Miller loop bound, or
2. intermediate computation, specifically the Miller variable.
13.3.1 Attack
1
Page and Vercauteren [318] attack the Duursma-Lee algorithm using a fault that
changes the Miller loop bound: the fault model assumes that a random fault is induced
in
m
, and this creates an observable difference in the number of iterations within the
Miller loop. For two fixed inputs, the approach computes two results (one valid and
one faulty); the security-critical input can be extracted from their quotient since this
effectively cancels out terms not influenced by the fault.
13.3.1.1 Recovering a Point
Consider the Duursma-Lee algorithm invoked with inputs
P
=
(
x
P
,
y
P
)
and
Q
=
(
where
P
is a security-critical point and
Q
is selected by the attack
e
r; assume
for the moment that the final powering (i.e., line 9) does not exist. Let
e
Δ
x
Q
,
y
Q
)
denote
the invocation of Algorithm 13.2 where an attacker induces some transient fault that
replaces the loop bound
m
(in Line 2) with
Δ
. Given this ability, instead of producing
