Cryptography Reference
In-Depth Information
endomorphism is called a
distortion map
; see Section
26.6.1
. It follows that DDH is easy
on supersingular elliptic curves.
26.6 Pairing-friendly elliptic curves
The cryptographic protocols given in Sections
22.2.3
and
23.3.2
relied on “pairing groups”.
We now mention the properties needed to have a practical system, and give some popular
examples.
For pairing-based cryptography it is desired to have elliptic curves
E
over
F
q
such that:
1. there is a large prime
r
dividing #
E
(
F
q
), with gcd(
r,q
)
=
1;
2. the DLP in
E
(
F
q
)[
r
] is hard;
F
q
k
is hard, where
k
3. the DLP in
=
k
(
q,r
) is the embedding degree;
F
q
k
is efficient;
4. computation in
E
(
F
q
) and
F
q
k
can be represented compactly.
5. elements of
E
(
F
q
) and
Elliptic curves with these properties are called
pairing-friendly curves
. Note that the
conditions are incompatible: for the DLP in
F
q
k
to be hard it is necessary that
q
k
be large
(say, at least 3000 bits) to resist index calculus attacks like those in Chapter
15
, whereas
to represent elements of
F
q
k
compactly we would like
q
k
to be small. Luckily, we can use
techniques such as those in Chapter
6
to represent field elements relatively compactly.
There is a large literature on pairing-friendly elliptic curves, culminating in the “taxon-
omy” by Freeman, Scott and Teske [
194
]. We give two examples below.
=
Example 26.6.1
For
a
0
,
1 define
E
a
:
y
2
x
3
+
y
=
+
x
+
a
F
2
. Then
E
a
is supersingular and #
E
a
(
F
2
l
)
=
2
l
±
2
(
l
+
1)
/
2
+
over
1 when
l
is odd. Some
of these integers have large prime divisors, for example 2
241
−
2
121
+
1isprime.The
embedding degree can be shown to be 4 in general; this follows since
(2
l
2
(
l
+
1)
/
2
1)(2
l
2
(
l
+
1)
/
2
2
2
l
(2
4
l
+
+
−
+
1)
=
+
1
|
−
1)
.
Example 26.6.2
(Barreto-Naehrig curves [
28
]) Consider the polynomials
36
x
4
36
x
3
24
x
2
6
x
2
p
(
x
)
=
+
+
+
6
x
+
1
and
t
(
x
)
=
+
1
(26.9)
[
x
]. Note that
t
(
x
)
2
3(6
x
2
1)
2
, that
r
(
x
)
in
Z
−
4
p
(
x
)
=−
+
4
x
+
=
p
(
x
)
+
1
−
t
(
x
)is
(
p
(
x
)
12
irreducible over
Q
and that
r
(
x
)
|
−
1). Suppose
x
0
∈ Z
is such that
p
=
p
(
x
0
)is
prime and
r
r
(
x
0
) is prime (or is the product of a small integer with a large prime). Then
the embedding degree
k
(
p,r
) is a divisor of 12 (and is typically equal to 12). Furthermore,
one can easily construct an elliptic curve
E/
=
F
p
such that #
E
(
F
p
)
=
r
; one of the 6 twists
of
y
2
x
3
=
+
1 will suffice. Note that
p
≡
1(mod3)and
E
is an ordinary elliptic curve.
