Cryptography Reference
In-Depth Information
Algorithm 13.5:
A randomised Duursma-Lee algorithm 159
Input
:
P
=
(
x
P
,
y
P
)
∈
G
1
and
Q
=
(
x
Q
,
y
Q
)
∈
G
2
.
Output
:
e
(
P
,
Q
)
∈
G
T
.
1
r
0
∈
R
F
q
6
,
r
1
∈
R
Z
f
0
←
r
0
,
f
1
←
1
2
3
m
←
m
+
r
1
1
upto
m
do
4
for
i
=
←
x
P
,
y
P
←
y
P
x
P
5
μ
←
x
P
+
x
Q
+
b
6
2
λ
←−
y
P
y
Q
σ
−
μ
7
2
g
←
λ
−
μρ
−
ρ
8
f
1
←
f
1
·
g
9
if
i
=
m
then
f
0
←
f
1
else
f
0
←
f
0
10
x
Q
←
x
1
/
3
Q
,
y
Q
←
y
1
/
3
Q
11
12
end
13
return
f
q
3
−
1
0
For example, one can check that intermediate elliptic curve points satisfy the curve
equation; this guards against faults in their coordinates. The Tate pairing offers an
attractive extension of this approach; the final value of the accumulator point (i.e.,
the value of
T
after execution of the Miller loop) should be
T
. However, similar
checks on finite field elements (e.g., the Miller variable) are more problematic. With
a large prime characteristic base field, one might make use of
=
O
1. the encoding strategy of Gaubatz, Sunar and Karpovsky [156], which lends itself
to modular multi-precision arithmetic such as the approaches of Montgomery
[293] or Barrett [27],
2. or the checksum-oriented “wooping” approach of Bos [59, Chap. 6].
Ozturk [316, Chap. 5] discusses fault-resilient arithmetic with direct consideration
of the Tate pairing; the work expands on Ozturk et al. [317], and uses
F
3
m
(and
extensions thereof) as an example. Although generally applicable, the focus in on
the extension field in particular since this helps to minimize latency.
13.4.3 Randomised or Fault-Resilient Miller Loop Counter
Ozturk [316, Sect. 5.3] discusses the use of fault-resilient counters to foil attacks
focused on changing the Miller loop bound; suggested instantiations include those
of Gaubatz et al. [156].
Ghosh et al. [159, Sect. 4] take a different approach, opting to randomize the loop
bound as detailed in Algorithm 13.5. The idea is to perform
m
>
m
iterations in total,
storing the correct result in the iteration where
i
=
m
. Although the implications for