Paper 2004/084

Evaluating elliptic curve based KEMs in the light of pairings

David Galindo, Sebastia Martin, and Jorge L. Villar


Several efforts have been made recently to put forward a set of cryptographic primitives for public key encryption, suitable to be standardized. In two of them (in the first place the NESSIE european evaluation project, already finished, and in the second place the standardisation bodies ISO/IEC), the methodology by Victor Shoup for hybrid encryption, known as {\em Key Encapsulation Method-Data Encapsulation Mechanism} (KEM-DEM), has been accepted. In this work we re-evaluate the elliptic curve based KEMs studied to become standards, which are called ACE-KEM, ECIES-KEM and PSEC-KEM. Their security is based on different assumptions related to the elliptic curve discrete logarithm (ECDL) problem on a random elliptic curve. First of all, we fix some inexact results claimed in the previous literature. As a consequence, the performance features of PSEC-KEM are dramatically affected. In second place, we analyse both their security properties and performance when elliptic curves with computable bilinear maps ({\em pairing curves} for short) are used. It turns out that these KEMs present a very tight security reduction to the same problem, namely the ECDH problem on such curves; moreover, one can even relate their security to the ECDL problem in certain curves with a small security loss. It is also argued that ECIES-KEM arises as the best option among these KEMs when pairing curves are used. This is remarkable, since NESSIE did not include ECIES-KEM over a random curve in its portfolio of recommended cryptographic primitives. It is concluded that for medium security level applications, which is likely the case for many embedded systems (e.g. smart cards), implementing these KEMs over pairing curves should be considered a very reasonable option.

Note: Revised version

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
public-key cryptographykey encapsulation mechanismspairingsstandardizationsmart cards.
Contact author(s)
dgalindo @ mat upc es
2004-06-11: revised
2004-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Galindo and Sebastia Martin and Jorge L.  Villar},
      title = {Evaluating elliptic curve based {KEMs} in the light of pairings},
      howpublished = {Cryptology ePrint Archive, Paper 2004/084},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.