Paper 2009/086

Point Compression for Koblitz Elliptic Curves

P. N. J. Eagle, Steven D. Galbraith, and John Ong

Abstract

Elliptic curves over finite fields have applications in public key cryptography. A Koblitz curve is an elliptic curve $E$ over $\F_2$; the group $E( \Ftn )$ has convenient features for efficient implementation of elliptic curve cryptography. Wiener and Zuccherato and Gallant, Lambert and Vanstone showed that one can accelerate the Pollard rho algorithm for the discrete logarithm problem on Koblitz curves. This implies that when using Koblitz curves, one has a lower security per bit than when using general elliptic curves defined over the same field. Hence for a fixed security level, systems using Koblitz curves require slightly more bandwidth. We present a method to reduce this bandwidth when a normal basis representation for $\Ftn$ is used. Our method is appropriate for applications such as Diffie-Hellman key exchange or Elgamal encryption. We show that, with a low probability of failure, our method gives the expected bandwidth for a given security level.

Note: Revised version of the paper with additional author.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptography
Contact author(s)
S Galbraith @ math auckland ac nz
History
2010-09-27: last of 2 revisions
2009-02-24: received
See all versions
Short URL
https://ia.cr/2009/086
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/086,
      author = {P.  N.  J.  Eagle and Steven D.  Galbraith and John Ong},
      title = {Point Compression for Koblitz Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2009/086},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/086}},
      url = {https://eprint.iacr.org/2009/086}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.