Cryptography Reference
In-Depth Information
Definition 26.3.15
Let notation be as in Section
26.3.3
, in particular
q
is a prime power,
r
is a prime,
q
is a primitive
k
th root of unity modulo
r
and the groups
G
1
and
G
2
are
as in equation (
26.3
). Let
s
q
m
(mod
r
)forsome
m
≡
∈ N
. For any
h
(
x
)
∈ Z
[
x
] write
=
i
=
0
h
i
x
i
.Let
P
h
(
x
)
G
2
and define
f
s,h
(
x
)
,Q
to be a function normalised at
infinity (in the sense of Definition 26.3.4) such that
∈
G
1
,
Q
∈
d
h
i
(([
s
i
]
Q
)
div(
f
s,h
(
x
)
,Q
)
=
−
(
O
E
))
.
i
=
0
Define
f
s,h
(
x
)
,Q
(
P
)
(
q
k
−
1)
/r
.
a
s,h
(
x
)
(
Q,P
)
=
We stress here that
h
is a polynomial, not a rational function (as it was in previous sections).
[
q
m
]
Q
π
q
(
Q
),
Since
[
s
]
Q
=
=
a
generalisation
of
equation
(
26.5
)
shows
that
f
h
i
,Q
(
P
)
q
mi
. It follows that one can compute
f
s,h
(
x
)
,Q
(
P
) efficiently using
Miller's algorithm in a similar way to computing the pairings in the previous section. The
running time of Miller's algorithm is proportional to
i
=
0
log
2
(max
f
h
i
,
[
s
i
]
Q
(
P
)
=
)intheworse
case (it performs better when the
h
i
have a large common prefix in their binary expansion).
Hess [
257
] shows that, for certain choices of
h
(
x
),
a
s,h
(
x
)
is a non-degenerate and bilinear
pairing. The goal is also to obtain good choices for
h
(
x
) so that the pairing can be computed
using a short loop. One of the major contributions of Hess [
257
] is to prove lower bounds on
the size of the coefficients of any polynomial
h
(
x
) that leads to a non-degenerate, bilinear
pairing. This supports the optimality conjecture mentioned in the previous section.
{
1
,
|
h
i
|}
Lemma 26.3.16
Let notation be as in Definition
26.3.15
.
1. a
s,r
(
Q,P
)
is the Tate pairing.
2. a
s,x
−
s
(
Q,P
)
is a power of the ate pairing.
3. a
s,h
(
x
)
x
(
Q,P
)
a
s,h
(
x
)
(
Q,P
)
s
.
=
4. Let h
(
x
)
,g
(
x
)
∈ Z
[
x
]
. Then
a
s,h
(
x
)
+
g
(
x
)
(
Q,P
)
=
a
s,h
(
x
)
(
Q,P
)
a
s,g
(
x
)
(
Q,P
)
and
a
s,h
(
x
)
(
Q,P
)
g
(
s
)
.
=
a
s,h
(
x
)
g
(
x
)
(
Q,P
)
Exercise 26.3.17
Prove Lemma
26.3.16
.
Theorem 26.3.18
Let notation be as above. Let s
∈ N
be such that s is a primitive kth
root of unity modulo r
2
. Let h
(
x
)
0(mod
r
)
but r
2
∈ Z
[
x
]
be such that h
(
s
)
≡
h
(
s
)
. Then
a
s,h
(
x
)
is a non-degenerate, bilinear pairing on G
2
×
G
1
.
Proof
Since
s
k
q
m
(mod
r
)forsome
m
≡
1(mod
r
) it follows that
s
≡
∈ N
. Since
h
(
s
)
≡
0(mod
r
) we can write
h
(
x
)
=
g
1
(
x
)(
x
−
s
)
+
g
2
(
x
)
r
