Cryptography Reference
In-Depth Information
The cost of these formulas is 1M+km+1S+3m+6s, where S is the cost of a
squaring in
F
p
k
. Note that we have ignored the cost of multiplication by
d
for
the reason that
d
can be selected specially.
We give an overview of the best formulas in the literature for pairing com-
putation on Edwards curves and for the different forms of Weierstrass curves in
Jacobian coordinates. Their performance is summarized in Table 1. We compare
the results with our new pairing formulas for Hessian curves. We find that our ad-
dition algorithm is fastest and our doubling algorithm is only slower than the one
in [8]. However, the curves considered in [8] are extremely special: for
p
≡
2mod3
these curves are supersingular and thus have
k
= 2 and for
p
1 mod 3 a total
of 3 isomorphism classes is covered by this curve shape. Therefore, our new for-
mulas for Tate pairings on Hessian curves are faster than all formulas excepted
for the very special curves with
a
4
=0,
a
6
=
b
2
.
≡
Table 1.
Costs of pairing computation
DBL
mADD
J
,[5],[11]
1M+km+1S+1m+11s+1m
a
4
1M+km+9m+3s
J
,[1],[11]
1M+km+1S+1m+11s+1m
a
4
1M+km+6m+6s
J
,
a
4
=
−
3,[5]
1M+km+1S+7m+4s
1M+km+9m+3s
J
,
a
4
=
−
3,[1]
1M+km+1S+6m+5s
1M+km+6m+6s
J
,
a
4
= 0,[5],[6]
1M+km+1S+6m+5s
1M+km+9m+3s
J
,
a
4
= 0,[1]
1M+km+1S+3m+8s
1M+km+6m+6s
P
,
a
4
=0,
a
6
=
b
2
,[8]
1M+km+1S+3m+5s
1M+km+10m+2s+1m
b
E
,[11]
1M+km+1S+8m+4s+1m
d
1M+km+14m+4s+1m
d
E
,[1]
1M+km+1S+6m+5s
1M+km+12m
H
, this paper
1M+km+1S+3m+6s
1M+km+10m
5Con lu on
In this paper, we first give the geometric interpretation of the group law on
Hessian curves, and then propose a new algorithm to compute Tate pairings
on elliptic curves in Hessian form. Compared with the methods for Weierstrass
curves and Edwards curves, our algorithm is fastest for pairing computation
excepted for the very special curves with
a
4
=0,
a
6
=
b
2
.
References
1. Arene, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster Computation of Tate
Pairings, Cryptology ePrint Archive, Report 2009/155,
2. Bernstein, D.J., Lange, T.: Analysis and optimization of elliptic-curve single-scalar
multiplication. In: Mullen, G.L., Panario, D., Shparlinski, I.E. (eds.) Finite fields
and applications, Contemp. Math., vol. 461, pp. 1-19. American Mathematical
Society, Providence (2008)
Search WWH ::
Custom Search