Cryptography Reference
In-Depth Information
Perhaps the most important of these reasons is to try to provide an appreciation for
the particular aspects of elliptic curve cryptography that give it an advantage over
other kinds of cryptography in many specific situations. Another important reason
is that some cryptographic schemes such as the pairing-based Boneh-Franklin IBE
scheme studied in Chap.
10
—and, similarly, other pairing-based schemes—can only,
as far as we know, be implemented in the elliptic curve setting due to the fact that it
is only in this context where suitable pairings have been found. Finally, the specific
study of these groups is also necessary, if one wants to implement elliptic curve-
based schemes, in order to be able to select appropriate parameters—for example,
the elliptic curves to be used—and also to develop the specific algorithms involved.
The main reason that led Koblitz and Miller to suggest elliptic curve groups for
cryptographic use was that it seemed unlikely that the index calculus method could be
adapted to solve the DLP on an elliptic curve group. As we have seen, index calculus
is the most efficient algorithm known to solve hard instances of the DLP and it
works in the multiplicative groups of finite fields by exploiting some of their specific
properties, in particular, the existence of sufficient 'smooth' elements that factor as
products of 'small' elements and which, depending on the context, can be integers
that are a product of small primes (the 'factor base primes') or polynomials whose
irreducible factors all have low degree. In contrast with this situation, in elliptic curve
groups it seems that there is no adequate notion of 'smallness' that provides sufficient
elements to be used as a 'factor base', leaving generic algorithms as the only option to
solve the DLP on some of these groups. Generic DLP algorithms are, as we have seen,
of fully exponential complexity—in contrast with the subexponential complexity of
index calculus—and this gives elliptic curve groups the important practical advantage
of requiring substantially smaller parameters, in comparison with other settings, for
the same cryptographic strength. For example, it has been estimated that a 4096-bit
RSAmodulus offers the same level of security as 313 bits in an elliptic curve scheme.
Before going into the specifics of elliptic curves, a few remarks about the scope
of this chapter and the reasons why this subject was not integrated within our earlier
treatment of other groups are perhaps in order. The main reason for this separate
treatment is that this material is more advanced, from a mathematical point of view,
than the rest of the subjects treated in the topic. For this reason, this chapter aims
only to give a basic understanding of elliptic curves and of the way they are used
in cryptography. In doing so we will skip the more advanced aspects and we will
try to keep the presentation as simple as possible. Even taking this into account, it
is possible that there are some minor details in our presentation that are not fully
covered by the mathematical prerequisites stated in the Introduction or the contents
of the previous chapters but, in that case, the reader should not worry much about
it and go on anyway, as these details will hopefully not hinder understanding of
the cryptographic applications. We will give more specific references below but, for
now, we just mention that two excellent advanced topics on the subject—which also
have some coverage of the cryptographic applications—are those by Silverman [181]
and Washington [197]. For more detailed treatments of the cryptographic aspects of
elliptic curves, we refer to [97], a practice-oriented reference intended as a guide for
