Cryptography Reference
In-Depth Information
potential attacks that are as yet unknown. This remark has to be qualified, however,
bearing inmind the fact that for some purposes such as IBcryptography, the additional
structure in the form of efficient pairings is a prerequisite for which elliptic curves of
low embedding degree are required and, in this context, even supersingular curves
are useful in some cases. Of course, even when subexponential methods are available
for the ECDLP, reasonable security can be attained by using appropriate key sizes.
The idea that additional structure on elliptic curves is dangerous leads us not only
to discard those classes of curves for which an efficient reduction for the ECDLP is
known but, in the view of many cryptographers, to altogether discard all curves built
in some special way. For example, some curves are built by the complex multiplication
method [181, 197] which makes it easier to count the number of points. Although
no special weaknesses for these curves have been found so far, the conservative
approach is not to use them. This leaves us with randomly selected curves which
can also be checked for vulnerability to known reductions and eventually discarded.
In practice such checks might not even be necessary because the probability that an
attack such as the MOV or FR-reduction is applicable to a randomly chosen curve is
negligible. An alternative to this approach is to use precomputed curves which have
been approved by some trusted third party. For example, one might consider some
of the 15 NIST recommended curves appearing in [75], one of which is the curve
P-256 that we have used in several of our examples.
In view of the greater difficulty of the ECDLP in comparison with the DLP in
the multiplicative groups of finite fields and also in comparison with the integer
factorization problem, elliptic curve cryptography has the important advantage of
requiring smaller key sizes than traditional cryptographic schemes, such as Elgamal
or RSA, for a given security level. This is especially important when cryptographic
schemes are implemented in computationally constrained environments such as,
for example, smart cards. Even if this is not the case, the difference in parameter
sizes makes elliptic curve cryptography much more efficient than, say, DL-based
cryptography over the multiplicative groups of finite fields.
There have been various studies that compare the relative difficulty of the main
problems used in cryptography to try to obtain estimates of the key sizes that should be
used for the schemes based on these problems in order to attain a given security level.
Several of these estimates, produced by different bodies and researchers, are collected
in the web page [30] by Giry, which allows many comparisons between them. In the
following table we summarize the estimated equivalent sizes corresponding to an
ECDLP in an elliptic curve group with 256-bit order. The sizes are in bits and, for
example, the sizes on the 'Asymmetric' column correspond to asymmetric keys and
refer either to the size of an RSA modulus or to the size of a multiplicative group
of a finite field where a DL-based scheme is implemented. The item 'Symmetric'
corresponds to the size of a symmetric encryption scheme such as AES and is 128
bits in most cases, just one-half of the output size of a hash function with the same
security level. In the first column, the name of the body or the person that produced the
estimate is given, and the last column gives an estimation of the year until which the
key and group sizes on the corresponding row are thought to offer sufficient security.
Search WWH ::




Custom Search