Cryptography Reference
In-Depth Information
transformed into Hessian form and the point operation for Hessian curves can be
implemented in a highly parallel way. As a result, the Hessian curves can provide
around a 40 percent performance improvement over the Weierstrass curves [18].
Furthermore, Joye and Quisquater [14] suggest that the unified formula for the
addition of points on Hessian curves can be used as a means for preventing side
channel attack.
In this paper, we consider the problems on Hessian curves. One of our contri-
bution is giving the geometric interpretation of the group law on Hessian curves.
As far as we know, this is the first geometric interpretation. Another contribution
is that we develop explicit formulas for computing pairings on Hessian curves.
Excepted for the very special elliptic curves with
a
4
=0,
a
6
=
b
2
, our formulas
are fastest for Tate pairing computation up to date.
2
Preliminaries
Let
F
p
be a finite field with
p
elements where
p>
2 is prime. Consider positive
integer
r
such that
r
is relative prime to the characteristic of the field
F
p
.Denote
the embedding degree by
k
, i.e. the smallest positive integer such that
r
divides
p
k
−
1. The elliptic curve in Weierstrass form is defined as
E
:
y
2
=
x
3
+
ax
+
b,
∈
F
p
,4
a
3
+27
b
2
where
a, b
=0
∈
F
p
.Let
P
be a point in
E
(
F
p
k
)[
r
]and
Q
F
p
k
). Define
f
i,P
to be a function on the elliptic curve with its divisor
div(
f
i,P
)=
i
(
P
)
∈
E
(
−
(
iP
)
−
(
i
−
1)(
O
),
i
∈
Z
. Consider the divisor
D
=(
Q
+
R
)
−
(
R
)
with
R
being a random point in
E
(
F
p
k
) such that
D
is coprime with (
P
)
−
O
(
).
Then the reduced Tate pairing [9] is a map
→
F
p
k
/
(
F
p
k
)
r
;
e
r
:
E
(
F
p
k
)[
r
]
×
E
(
F
p
k
)
/rE
(
F
p
k
)
(
f
r,P
(
D
))
(
p
k
−
1)
/r
.
If the function
f
r,P
in the definition is normalized, then one can simply work
with the point
Q
, i.e. the reduced Tate pairing is:
(
P, Q
)
→
e
r
(
P, Q
)=(
f
r,P
(
Q
))
(
p
k
−
1)
/r
.
Let
g
iP,jP
),
then
g
iP,jP
=
l
iP,jP
/v
(
i
+
j
)
P
,where
l
iP,jP
is the equation of the line through
iP
,
jP
and
v
(
i
+
j
)
P
is the equation of the vertical line through (
i
+
j
)
P
.Fromthe
definition of
f
r,P
,wecanseethat
be the function such that div(
g
iP,jP
)=(
iP
)+(
jP
)
−
((
i
+
j
)
P
)
−
(
O
div(
f
i
+
j,P
)=(
i
+
j
)(
P
)
−
((
i
+
j
)
P
)
−
(
i
+
j
−
1)(
O
)
=
i
(
P
)
−
(
iP
)
−
(
i
−
1)(
O
)
+
j
(
P
)
−
(
jP
)
−
(
j
−
1)(
O
)
(1)
+(
iP
)+(
jP
)
)
=div(
f
i,P
)+div(
f
j,P
)+div(
g
iP,jP
)
.
−
((
i
+
j
)
P
)
−
(
O
Search WWH ::
Custom Search