Abstract
Elliptic (ECC) and hyperelliptic curve cryptosystems (HECC) have emerged as cryptosystems for small hand-held and mobile devices. Extensive research has been carried out for their secure and efficient implementation on these devices. These devices come with very low amount of resources, efficient memory management is an important issue in all such implementations. HECC arithmetic is now generally performed using so called explicit formulas. The main goal of these formulas is to reduce the number of finite field operations (multiplications and squarings). On the other hand, reducing the memory requirement is also important. To the best of our knowledge, the literature on HECC implementation does not seriously consider this aspect. This is the first work to obtain memory efficient versions of various explicit formulas appearing in the literature. In certain cases, we are also able to determine the minimum memory requirement and obtain a memory optimal implementation. We believe that these formulas will be extremely useful to designers of HECC. Our basic technique is essentially an exhaustive search with heuristic strategies for improving the run-time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cohen, H., Frey, G. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)
Bertoni, G., et al.: Hyperelliptic Curve Cryptosystem: What is the Best Parallel Hardware Architecture? In: Nedjah, N. (ed.) Embedded Cryptographic Hardware: Design and Security, Nova Science Publishers, New York (2004)
Cantor, D.G.: Computing in the Jacobian of a Hyperelliptic curve. Mathematics of Computation 48, 95–101 (1987)
A compendium of NP-optimization problems, http://www.nada.kth.se/~viggo/problemlist/compendium.html
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco (1979)
Gaudry, P., Harley, R.: Counting Points on Hyperelliptic Curves over Finite Fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 297–312. Springer, Heidelberg (2000)
Harley, R.: Fast Arithmetic on Genus 2 Curves (2000), available at http://cristal.inria.fr/~harley/hyper 2000
Klein, P., et al.: Approximation through multicommodity flow. In: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 726–737. IEEE Computer Society Press, Los Alamitos (1990)
Koblitz, N.: Hyperelliptic Cryptosystems. Journal of Cryptology 1, 139–150 (1989)
Lange, T.: Efficient Arithmetic on Genus 2 Curves over Finite Fields via Explicit Formulae. Cryptology ePrint Archive, Report 2002/121 (2002), http://eprint.iacr.org/
Lange, T.: Inversion-free Arithmetic on Genus 2 Hyperelliptic Curves. Cryptology ePrint Archive, Report 2002/147 (2002), http://eprint.iacr.org/
Lange, T.: Weighted Coordinates on Genus 2 Hyperelliptic Curves. Cryptology ePrint Archive, Report 2002/153 (2002), http://eprint.iacr.org/
Lange, T.: Formulae for Arithmetic on Genus 2 Hyperelliptic Curves. Applicable Algebra in Engineering, Communication and Computing 15(5), 295–328 (2005)
Lange, T., Stevens, M.: Efficient Doubling on Genus 2 Curves over Binary Fields. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 170–181. Springer, Heidelberg (2004)
Menezes, A., Wu, Y., Zuccherato, R.: An Elementary Introduction to Hyperelliptic Curves. Technical Report CORR 96-19, University of Waterloo, Canada. (1996), Available at http://www.cacr.math.uwaterloo.ca
Mishra, P.K., Pal, P., Sarkar, P.: Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Crytosystems. Cryptology ePrint Archive, Report 2006/204 (2006), http://eprint.iacr.org/2006/204
Mishra, P.K., Sarkar, P.: Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves (Extended Abstract). In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 91–111. Springer, Heidelberg (2003), Full version available at Cryptology ePrint Archive, Report 2003/180 http://eprint.iacr.org/
Pelzl, J., Wollinger, T., Paar, C.: High Performance Arithmetic for Hyperelliptic Curve Cryptosystems of Genus Two. In: International Conference on Information Technology: Coding and Computing - ITCC, Las Vegas, USA (2004)
Sethi, R.: Complete register allocation problems. SIAM Journal of Computing 4, 226–248 (1975)
Spallek, A.M.: Kurven vom Geschletch 2 und ihre Anwendung in Public-Key-Kryptosystemen. PhD Thesis, Universität Gesamthochschule, Essen (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Mishra, P.K., Pal, P., Sarkar, P. (2007). Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Cryptosystems. In: Dawson, E., Wong, D.S. (eds) Information Security Practice and Experience. ISPEC 2007. Lecture Notes in Computer Science, vol 4464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72163-5_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-72163-5_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72159-8
Online ISBN: 978-3-540-72163-5
eBook Packages: Computer ScienceComputer Science (R0)