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
 
Search WWH ::




Custom Search