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.Category / Keywords: elliptic curve cryptography Date: received 18 Feb 2009, last revised 26 Sep 2010 Contact author: S Galbraith at math auckland ac nz Available format(s): PDF | BibTeX Citation Note: Revised version of the paper with additional author. Version: 20100927:023335 (All versions of this report) Short URL: ia.cr/2009/086 Discussion forum: Show discussion | Start new discussion