Point compression for Koblitz elliptic curves

Previous Article
The dual construction for arcs in projective Hjelmslev spaces
AMC Home
This Issue
Next Article

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

Point compression for Koblitz elliptic curves

Philip N. J. Eagle ^1, , Steven D. Galbraith ^2, and John B. Ong ^2,

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

Abstract
Related Papers

Elliptic curves over finite fields have applications in public key cryptography. A Koblitz curve is an elliptic curve $E$ over $\mathbb F$₂; the group $E(\mathbb F$_2ⁿ$)$ 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$_2ⁿ 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.

Keywords: Elliptic curve cryptography, point compression., Koblitz curves.

Mathematics Subject Classification: 94A60, 11T7.

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.
[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.
[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.
[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.
[5]	N. Koblitz, CM-curves with good cryptographic properties, in "CRYPTO '91'' (ed. J. Feigenbaum), Springer, (1992), 279-287.
[6]	R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' Cambridge, 1994.
[7]	V. S. Miller, Use of elliptic curves in cryptography, in "CRYPTO '85'' (ed. H.C. Williams), Springer, (1986), 417-426.
[8]	J. Pollard, Monte Carlo methods for index computation mod p, Math. Comput., 32 (1978), 918-924.
[9]	M. F. Schilling, The longest run of heads, College Math. J., 21 (1990), 196-207. doi: 10.2307/2686886.
[10]	G. Seroussi, Compact representation of elliptic curve points over $\mathbb F_{2^n}$, HP Labs Tech. Report HPL-98-94R1, September 1998.
[11]	J. A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Crypt., 19 (2000), 195-249. doi: 10.1023/A:1008306223194.
[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.
[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.

show all references

References:

[1]	I. F. Blake, G. Seroussi and N. P. Smart, "Elliptic Curves in Cryptography,'' Cambridge, 1999.
[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.
[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.
[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.
[5]	N. Koblitz, CM-curves with good cryptographic properties, in "CRYPTO '91'' (ed. J. Feigenbaum), Springer, (1992), 279-287.
[6]	R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' Cambridge, 1994.
[7]	V. S. Miller, Use of elliptic curves in cryptography, in "CRYPTO '85'' (ed. H.C. Williams), Springer, (1986), 417-426.
[8]	J. Pollard, Monte Carlo methods for index computation mod p, Math. Comput., 32 (1978), 918-924.
[9]	M. F. Schilling, The longest run of heads, College Math. J., 21 (1990), 196-207. doi: 10.2307/2686886.
[10]	G. Seroussi, Compact representation of elliptic curve points over $\mathbb F_{2^n}$, HP Labs Tech. Report HPL-98-94R1, September 1998.
[11]	J. A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Crypt., 19 (2000), 195-249. doi: 10.1023/A:1008306223194.
[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.
[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.

[1]	Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169
[2]	Marek Janasz, Piotr Pokora. On Seshadri constants and point-curve configurations. Electronic Research Archive, 2020, 28 (2) : 795-805. doi: 10.3934/era.2020040
[3]	Koray Karabina, Berkant Ustaoglu. Invalid-curve attacks on (hyper)elliptic curve cryptosystems. Advances in Mathematics of Communications, 2010, 4 (3) : 307-321. doi: 10.3934/amc.2010.4.307
[4]	Chuangqiang Hu, Shudi Yang. Multi-point codes from the GGS curves. Advances in Mathematics of Communications, 2020, 14 (2) : 279-299. doi: 10.3934/amc.2020020
[5]	Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong. Speeding up regular elliptic curve scalar multiplication without precomputation. Advances in Mathematics of Communications, 2020, 14 (4) : 703-726. doi: 10.3934/amc.2020090
[6]	Alice Silverberg. Some remarks on primality proving and elliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 427-436. doi: 10.3934/amc.2014.8.427
[7]	David L. Finn. Convexity of level curves for solutions to semilinear elliptic equations. Communications on Pure and Applied Analysis, 2008, 7 (6) : 1335-1343. doi: 10.3934/cpaa.2008.7.1335
[8]	Antonio Garcia. Transition tori near an elliptic-fixed point. Discrete and Continuous Dynamical Systems, 2000, 6 (2) : 381-392. doi: 10.3934/dcds.2000.6.381
[9]	Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101
[10]	Ravi Vakil and Aleksey Zinger. A natural smooth compactification of the space of elliptic curves in projective space. Electronic Research Announcements, 2007, 13: 53-59.
[11]	Guilin Ji, Changjian Liu. The cyclicity of a class of quadratic reversible centers defining elliptic curves. Discrete and Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021299
[12]	Stefano Galatolo. Orbit complexity and data compression. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477
[13]	Steven D. Galbraith, Ping Wang, Fangguo Zhang. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. Advances in Mathematics of Communications, 2017, 11 (3) : 453-469. doi: 10.3934/amc.2017038
[14]	Shao-Yuan Huang, Shin-Hwa Wang. On S-shaped bifurcation curves for a two-point boundary value problem arising in a theory of thermal explosion. Discrete and Continuous Dynamical Systems, 2015, 35 (10) : 4839-4858. doi: 10.3934/dcds.2015.35.4839
[15]	Rafail Krichevskii and Vladimir Potapov. Compression and restoration of square integrable functions. Electronic Research Announcements, 1996, 2: 42-49.
[16]	Matthias Ngwa, Ephraim Agyingi. A mathematical model of the compression of a spinal disc. Mathematical Biosciences & Engineering, 2011, 8 (4) : 1061-1083. doi: 10.3934/mbe.2011.8.1061
[17]	Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[18]	Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[19]	Ananta Acharya, R. Shivaji, Nalin Fonseka. $ \Sigma $-shaped bifurcation curves for classes of elliptic systems. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022067
[20]	Frank Trujillo. Uniqueness properties of the KAM curve. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5165-5182. doi: 10.3934/dcds.2021072

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Philip N. J. Eagle Steven D. Galbraith John B. Ong
on Google Scholar
Philip N. J. Eagle Steven D. Galbraith John B. Ong

[Back to Top]