Cryptography Reference
In-Depth Information
performance are a potential disadvantage, this approach makes recovery of
d
in the
attack of Page and Vercauteren [318], for example, more difficult.
13.4.4 Input Randomization and Blinding
Some of the attacks described in Sect. 13.3 rely on the fact that the attacker has
knowledge of, and potentially control over, one of the input points; assume this
point is
Q
. Several potential countermeasures focus on this fact: the idea is that by
randomizing
Q
or the Miller variable, the attacker is unable to recover information
from a faulty result.
1. Page and Vercauteren [318] note that since
a
·
b
e
(
a
·
A
,
b
·
B
)
=
e
(
A
,
B
)
,
α
β
α
·
β
=
one can randomize
P
and
Q
by selecting random
and
such that
(
)
1
mod
r
, and then computing
e
(α
·
P
,β
·
Q
)
=
e
(
P
,
Q
).
2. Page and Vercauteren [318] note that since
e
(
A
,
B
+
C
)
=
e
(
A
,
B
)
·
e
(
A
,
C
),
)
−
1
,
one can randomize
Q
by precomputing a random point
R
and
S
=
e
(
P
,
R
and then computing
e
(
P
,
Q
+
R
)
·
S
=
e
(
P
,
Q
).
3. Scott [365] discusses the fact that one can randomize the Miller variable (during
each iteration) via multiplication by some random
ω
∈ F
q
; this has no effect on
the result since the randomization is eliminated by the final powering.
4. Kim et al. [230] discuss the possibility of using randomized projective coordi-
nates; the idea is to operate on the affine point
Q
=
(
x
Q
,
y
Q
)
using the projective
representative
(λ
·
x
Q
,λ
·
y
Q
,λ)
λ
∈ F
q
instead. This dictates use of a projective (re)formulation
of the pairing algorithm.
5. Shirase et al. [376] describe a scheme for randomizing input points via addition
of a random field element, and then removing the effect via reformulation of the
pairing algorithm.
for some random
An important note is that Ghosh et al. [159, Sect. 3] incorrectly rule out the first two
approaches; their argument is based on the mistaken assumption that the bilinearity of
