Pairing-Friendly Elliptic Curves
P
P
Theory
For a pairing-based cryptographic system to be secure, the
discrete logarithm problems
in the group
E
(F
q
) of F
q
-
rational points on
E and in the multiplicative group
F
×
q
k
must both be computationally infeasible. The best known
discrete logarithm algorithm on elliptic curves is the par-
allelized Pollard rho algorithm, which has running time
O
(
√
r
), where
r is the size of the largest prime-order
subgroup of
E
(F
q
). On the other hand, the best algorithm
for discrete logarithm computation in finite fields is the
index calculus attack
, which has running time subexpo-
nential in the field size. Thus, to achieve the same level of
security in both groups, the size
q
k
of the extension field
must be significantly larger than
r.
Table
lists ranges for
r and
q
k
(
q prime) and
k to match commonly desired lev-
els of security. Two different ranges of
k are given for each
level, depending on the
ρ-value ρ
= log
q/ log
r, which
measures the base field size relative to the size of the prime-
order subgroup of the curve. In general, curves with small
ρ-values are desirable in order to speed up arithmetic on
the elliptic curve. At times, though, a larger
ρ-value is
acceptable for the sake of fast pairing evaluations; in par-
ticular, at the -bit security level, a
k
= curve with -bit
prime subgroup order defined over a -bit finite field rep-
resents an efficient setup for some choices of curves and
protocols.
