# American Institute of Mathematical Sciences

February  2011, 5(1): 1-10. doi: 10.3934/amc.2011.5.1

## Point compression for Koblitz elliptic curves

 1 Information Security Group, Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom 2 Mathematics Department, The University of Auckland, Private Bag 92019 Auckland 1142, New Zealand, New Zealand

Received  February 2009 Revised  September 2010 Published  February 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 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 $\mathbb F$2n 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.
Citation: Philip N. J. Eagle, Steven D. Galbraith, John B. Ong. Point compression for Koblitz elliptic curves. Advances in Mathematics of Communications, 2011, 5 (1) : 1-10. doi: 10.3934/amc.2011.5.1
##### References:
 [1] I. F. Blake, G. Seroussi and N. P. Smart, "Elliptic Curves in Cryptography,'' Cambridge, 1999.  Google Scholar [2] R. P. Gallant, R. Lambert and S. A. Vanstone, Improving the parallelized pollard Lambda search on binary anomalous curves, Math. Comput., 69 (2000), 1699-1705. doi: 10.1090/S0025-5718-99-01119-9.  Google Scholar [3] P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptology, 15 (2002), 19-46. doi: 10.1007/s00145-001-0011-x.  Google Scholar [4] B. King, A point compression method for elliptic curves defined over $GF(2^n)$, in "PKC 2004'' (eds. F. Bao, R.H. Deng and J. Zhou), Springer, (2004), 333-345.  Google Scholar [5] N. Koblitz, CM-curves with good cryptographic properties, in "CRYPTO '91'' (ed. J. Feigenbaum), Springer, (1992), 279-287.  Google Scholar [6] R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' Cambridge, 1994.  Google Scholar [7] V. S. Miller, Use of elliptic curves in cryptography, in "CRYPTO '85'' (ed. H.C. Williams), Springer, (1986), 417-426.  Google Scholar [8] J. Pollard, Monte Carlo methods for index computation mod p, Math. Comput., 32 (1978), 918-924.  Google Scholar [9] M. F. Schilling, The longest run of heads, College Math. J., 21 (1990), 196-207. doi: 10.2307/2686886.  Google Scholar [10] G. Seroussi, Compact representation of elliptic curve points over $\mathbb F_{2^n}$, HP Labs Tech. Report HPL-98-94R1, September 1998. Google Scholar [11] J. A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Crypt., 19 (2000), 195-249. doi: 10.1023/A:1008306223194.  Google Scholar [12] P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Crypt., 12 (1999), 1-28. doi: 10.1007/PL00003816.  Google Scholar [13] M. J. Wiener and R. J. Zuccherato, Faster Attacks on Elliptic Curve Cryptosystems, in "SAC 1998'' (eds. S.E. Tavares and H. Meijer), Springer, (1999), 190-200.  Google Scholar

show all references

##### References:
 [1] I. F. Blake, G. Seroussi and N. P. Smart, "Elliptic Curves in Cryptography,'' Cambridge, 1999.  Google Scholar [2] R. P. Gallant, R. Lambert and S. A. Vanstone, Improving the parallelized pollard Lambda search on binary anomalous curves, Math. Comput., 69 (2000), 1699-1705. doi: 10.1090/S0025-5718-99-01119-9.  Google Scholar [3] P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptology, 15 (2002), 19-46. doi: 10.1007/s00145-001-0011-x.  Google Scholar [4] B. King, A point compression method for elliptic curves defined over $GF(2^n)$, in "PKC 2004'' (eds. F. Bao, R.H. Deng and J. Zhou), Springer, (2004), 333-345.  Google Scholar [5] N. Koblitz, CM-curves with good cryptographic properties, in "CRYPTO '91'' (ed. J. Feigenbaum), Springer, (1992), 279-287.  Google Scholar [6] R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' Cambridge, 1994.  Google Scholar [7] V. S. Miller, Use of elliptic curves in cryptography, in "CRYPTO '85'' (ed. H.C. Williams), Springer, (1986), 417-426.  Google Scholar [8] J. Pollard, Monte Carlo methods for index computation mod p, Math. Comput., 32 (1978), 918-924.  Google Scholar [9] M. F. Schilling, The longest run of heads, College Math. J., 21 (1990), 196-207. doi: 10.2307/2686886.  Google Scholar [10] G. Seroussi, Compact representation of elliptic curve points over $\mathbb F_{2^n}$, HP Labs Tech. Report HPL-98-94R1, September 1998. Google Scholar [11] J. A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Crypt., 19 (2000), 195-249. doi: 10.1023/A:1008306223194.  Google Scholar [12] P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Crypt., 12 (1999), 1-28. doi: 10.1007/PL00003816.  Google Scholar [13] M. J. Wiener and R. J. Zuccherato, Faster Attacks on Elliptic Curve Cryptosystems, in "SAC 1998'' (eds. S.E. Tavares and H. Meijer), Springer, (1999), 190-200.  Google Scholar

2020 Impact Factor: 0.935