Point compression for Koblitz elliptic curves
Philip N. J. Eagle, Steven D. Galbraith⋆, John B. Ong · Advances in Mathematics of Communications · 2011
Elliptic curves over finite fields have applications in public key cryptography.A Koblitz curve is an elliptic curve $E$ over $\mathbb F$2; the group $E(\mathbb F$2n$)$ has convenient featuresfor efficient implementation of elliptic curve cryptography. Wiener and Zuccherato and Gallant, Lambert and Vanstone showed that one can accelerate the Pollard rho algorithmfor 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 basisrepresentation for $\mathbb F$2n is used. Our method is appropriate forapplications such as Diffie-Hellman key exchange or Elgamalencryption. We show that, with a low probability of failure, ourmethod gives the expected bandwidth for a given security level.