ECC‎ > ‎

Hyper-ECC

HyperElliptic Curve Cryptosystems

References

*          Seigo Arita, Gaudry’s variant against Cab curves, pp. 1809-1814, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A, 9, September 2000.

*          Seigo Arita, Construction of secure Cab curves using modular curves, pp. 2930-2938, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E84-A, 11, November 2001.

*/o       N. Boston, T. C. Clancy, Y. Liow & J. E. Webster, Genus two hyperelliptic coprecessor, pp. 400-414, Lecture Notes in Computer Science, 2523, CHES 2002 – Workshop on Cryptographic Hardware and Embedded Systems, 13-15 August 2002, Redwood City, California, Burt S.  Kaliski, Jr., Çetin Kaya Koç & Christof Paar (editors), Springer, 2002.

*          David G. Cantor, Computing in the jacobian of a hyperelliptic curve, pp. 95-101,  Mathematics of Computation, 48, 177, January 1987.

*          Y. Choie, E. Jeong & E. Lee, Supersingular hyperelliptic curve of genus 2 over finite fields, preprint, 2002.

*/o       Mathieu Ciet, Jean-Jacques Quisquater & Francesco Sica, Analysis of the Gallant-Lambert-Vanstone method based on efficient endomorphism: elliptic and hyperelliptic curves, pp. ------, 9th Workshop on Selected Areas in Cryptography, SAC 2002, St. John’s, Newfoundland, Canada, 15-16 August 2002.

*          Jinhui Chao, Kazuto Matsuo & Shigeo Tsujii, Baby step giant step algorithms in point counting of hyperelliptic curves, pp. 1127-1134, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A, 5, May 2003.

*          Henri Darmon, Hyperelliptic curves, Hilbert modular forms and Fermat’s last theorem, preprint, 1997.

*          Jan Denef & Frederik Vercauteren, Extensions of Kedlaya’s algorithm to hyperelliptic curves in characteristic 2, 6th Workshop on Elliptic Curve Cryptography (ECC 2002), University of Essen, Essen, Germany, 23-25 September 2002.

*          L. Hernández Encinas, J. Muñoz Masqué 7 Alfred J. Menezes, Isomorphism classes of genus-2 hyperelliptic curves over finite fields, preprint.

*          Andreas Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Conference on the Mathematics of Public Key Cryptography, Andrew M. Odlyzko, Gary Walsh & Hugh C. Williams (editors), Fields Institute for Research in the Mathematical Sciences, Toronto, Canada, 12-17 June 1999.

*          Andreas Enge & Andreas Stein, Smooth ideals in hyperelliptic function fields, January 2000.

*          Gerhard Frey, Applications of arithmetical geometry to cryptography constructions, 5th International Conference on Finite Fields and Applications (Fq5), -----, 199x-2000.

*          E. Furukawa, M. Kawazoe & T. Takahashi, Counting points on the Jacobian variety of a hyperelliptic curve defined by y2 = x5 + ax over a prime field, preprint, 2002.

*          Steven D. Galbraith, Sachar Paulus & Nigel P. Smart, Arithmetic on superelliptic curves, Technical report HPL-1998-179, Hewlett-Packard Laboratories, October 1998.

*          Pierrick Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, pp. 19-34, Lecture Notes in Computer Science, 1807, Advances in Cryptology – Eurocrypt 2000, International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, Belgium, May 2000, Bart Preneel (editor), Springer-Verlag, 2000. Title of preprint: A variant of the Adleman-DeMarrais-Huang algorithm and its application to small genera, preprint.

*/o       Pierrick Gaudry & Nicolas Gürel, An extension of Kedlaya’s point-counting algorithm to superelliptic curves, pp. 480-494, Lecture Notes in Computer Science, 2248, Advances in Cryptology – Asiacrypt 2001, 7th International Conference on the Theory and Applications of Cryptology and Information Theory, Gold Coast, Australia, 9-13 December 2001, Colin Boyd (editor), Springer-Verlag, 2001.

*          Pierrick Gaudry & Robert Harley, Counting points on hyperelliptic curves over finite fields, pp. 313-332, Lecture Notes in Computer Science, 1838, Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden, Netherlands, 2-7 July 2000, Wieb Bosma (editor), 2000.

*          Pierrick Gaudry, Florian Hess & Nigel P. Smart, Constructive and destructive facets of Weil descent on elliptic curves, Technical report HPL-2000-10, Hewlett-Packard Laboratories, 17 January 2000.

*          Ryuichi Harasawa & Joe Suzuki, A fast jacobian group arithmetic schemes fro algebraic cruve cryptography, pp. 130-139, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E84-A, 1, January 2001.

*          Florian Hess, Gadiel Seroussi & Nigel Smart, Two topics in hyperelliptic cryptography, Technical report HPL-2000-118, Hewlett-Packard Laboratories, 19 September 2000.

*/o       Ishizuka Hirokazu, Yasuyuki Sakai & Kouichi Sakurai, Secure hyperelliptic cryptosystems and their peformance, pp. -----, Lecture Notes in Computer Science, 1431, 1st International Workshop on Practice and Theory in Public Key Cryptography – PKC ‘98, Yokohama, Kanagawa, Japan, 5-6 February 1998, Hideki Imai & Yuliang Zheng (editors), Springer-Verlag, 1998.

*          Toshiya Itoh, Kouichi Sakurai & Hiroki Shizuya, On the complexity of hyperelliptic discrete logarithm problem, pp. 337-351, Lecture Notes in Computer Science, 547, Advances in Cryptology – Eurocrypt ‘91, Workshop on the Theory and Applications of Cryptographic Techniques, Brighton, United Kingdom, April 1991, Donald W. Davies (editor), Springer-Verlag, 1991.

*          Michael J. Jacobson, Alfred J. Menezes & Andreas Stein, Solving elliptic curve discrete logatrithm problems using Weil descent, pp. 231-260, Journal of the Ramanujan Mathematical Society, 16, 2001; Technical report CORR 2001-31, Department of Combinatorics & Optimization, University of Waterloo, Ontario, Canada, 2001.

*          Michael J. Jacobson, Alfred J. Menezes & Andreas Stein, Hyperelliptic Curves and cryptography, Technical report CORR 2003-13, Department of Combinatorics & Optimization, University of Waterloo, Ontario, Canada, 2003.

*          Sangtae Jeong, Jongin Lim & Young-Ho Park, Speeding up point multiplication on hyperelliptic curves with efficiently-computable endomorphisms, pp. 197-208, Lecture Notes in Computer Science, 2332, Advances in Cryptology – Eurocrypt 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, the Netherlands, 28 April – 2 May 2002, Lars R. Knudsen (editor), Springer-Verlag, 2002.

*          Marc Joye, Introduction élémentaire à la théorie des courbes elliptiques, UCL Crypto Group Technical report CG-1995/1, Université Catholique de Louvain, 1995.

*          Naoki Kanayama, Koh-ichi Nagao & Shigenori Uchiyama, Generating secure genus two hyperelliptic curves using Elkies’s point counting algorithm, pp. 919-927, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A, 4, April 2003.

*          Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, 2001.

*          Neal Koblitz, Hyperelliptic cryptosystems, pp. 139-150, Journal of Cryptology, 1, 3, 1989.

*          Tanja Lange, Efficient arithmetic on hyperelliptic curves, Ph.D. Dissertation, 2001.

*          Tanja Lange, Weighted coordinates on genus 2 hyperelliptic curves, preprint, 2002.

*          Tanja Lange, Efficient arithmetic on genus 2 hyperelliptic cureves over finite fields via explicit formulae, preprint, 2002.

*          Alfred J. Menezes, Yi-Hong Wu & Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, Technical report CORR 96-19, Department of Combinatorics & Optimization, University of Waterloo, Ontario, Canada, 1996.

*/o       Koh-ichi Nagao, Improving group law algorithms for Jacobians of hyperelliptic curves, pp. -----, Lecture Notes in Computer Science, 1838, Algorithmic Number Theory, 4th International Symposium ANTS-IV, Leiden, Netherlands, 2-7 July 2000, Wieb Bosma (editor), 2000.

*          Tatsuaki Okamoto & Kouichi Sakurai, Efficient algorithms for the construction of hyperelliptic cryptosystems, pp. 267- 278, Lecture Notes in Computer Science, 576, Advances in Cryptology – Crypto ‘91, 11th Annual International Cryptology Conference, Santa Barbara, California, August 1991, Joan Feigenbaum (editor), Springer-Verlag, 1992.

*          Sachar Paulus & Hans-Georg Rück, Real and imaginary quadratic representations of hyperelliptic function fields, preprint.

*/o       Yasuyuki Sakai  & Kouichi Sakurai, Design of hyperelliptic cryptosystems in small characteristic and a software implementation over F(2n), pp. -----, Lecture Notes in Computer Science, 1514, Advances in Cryptology – Asiacrypt ‘98, International Conference on the Theory and Applications of Cryptology and Information Theory, Beijing, China, 18-22 October 1998, Kazuo Ohta & Dingyi Pei (editors), Springer-Verlag, 1999.

*          Yasuyuki Sakai  & Kouichi Sakurai, On the practical performance of hyperelliptic curve cryptosystems in software implementation, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A, 4, April 2000.

*          Hiroki Shizuya, Zero-knowledge interactive proofs for hyper- and elliptic-discrete logarithm problems, preprint.

*          Nigel P. Smart, On the performance of hyperelliptic cryptosystems, pp. -----, Lecture Notes in Computer Science, 1592, Advances in Cryptology – Eurocrypt ‘99, International Conference on the Theory and Applications of Cryptographic Techniques, Prague, Czech Republic, 2-6 May 1999, Jacques Stern (editor), Springer-Verlag, 1999. Also: Technical report HPL-1998-162, Hewlett-Packard Laboratories, September 1998.

*          Nigel P. Smart, experiments using an analogue of number field sieve algorithm to solve the discrete logarithm problem in the Jacobians of hyperelliptic curves, Technical report HPL-1997-130, Hewlett-Packard Laboratories, October 1997.

*          Andreas Stein, Sharp upper bounds for arithmetics in hyperelliptic function fields, July 1999.

*          Andreas Stein & Eddyn Teske, Explicit bounds and heuristics on class numbers in hyperelliptic function fields, July 1999.

*          Frederik Vercauteren, Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2, pp. 369-384, Lecture Notes in Computer Science, 2442, Advances in Cryptology – Crypto 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, August 2002, Moti Yung (editor), Springer-Verlag, 2002.

*          Emil J. Volcheck, Addition in the Jacobian of a curve over a finite field, Oberwolbach conference, Computational Number Theory, 28 May – 3 June 1995.

*/o       Yumin Wang, Fangguo Zhang & Futai Zhang, Fast scalar multplication on the Jacobian of a family of hyperelliptic curves, pp. 74-83, Lecture Notes in Computer Science, 2229, 3rd International Conference on Information and Communications Security, ICICS 2001, Xian, China, 13-16 November 2001, Tatsuaki Okamoto, Sihan Qing & Jianying Zhou (editors), Springer, 2001.

*          Thomas Wollinger, Computer architectures for cryptosystems based on hyperelliptic curves, Master Thesis, ECE Department, Worcester Polytechnic Institute, Worcester, Christof Paar (advisor), 2001.

 

Theory

            A hyperelliptic curve C over a field K is defined by the equation of the form

y2 + h(x) = f(x),

where h(x) is a polynomial of degree £ g, that is called the genus of C, and f(x) is a monic polynomial of degree n = 2g + 1 and both polynomials are defined over the field K. As for elliptic curves, the equation of C is required to have no singular point.

Example: The polynomial h(x) can be chosen to be 1 or even 0.

y2 + y = xn + axn–1 + … + 1 or y2 = xn + axn–1 + … + 1.

            If f(x) is a cubic polynomial, n = 3, then the hyperelliptic curve reduces to an elliptic curve, whose genus g = 1.

            The jacobian J(C, GF(2m)) will play the same role of the group of points on an elliptic curve. It is also either cyclic, or the direct sum of two cyclic groups of order n1 and n2, where n2|n1. An element of a jacobian is called a “divisor” (or more precisely, an equivalence class of divisors.)

 

The HECDLP

            The Hyperelliptic Curve Discrete Logarithm Problem is also defined in a familiar way on the jacobian of C.

            Given a hyperelliptic curve C over a finite field Fq, and two divisors D and T in the jacobian J(C, Fq), the problem is to find an integer m such that T = mD. (Or in terms of the equivalence, T and mD are linearly equivalent T ~ mD.)

 

            The elliptic curve cryptosystems such as Diffie-Hellman, Massey-Omura and ElGamal... can be adapted using HECDLP. They are called hyperelliptic curve cryptosystems.

            The major advantage of using hyperelliptic curves in HECDLP in comparison with ECDLP consists of a considerably smaller underlying finite field where all basic computations are done, for approximately the same size of the group where the DLP is defined.  On the other hand, it may be the structure of hyperelliptic curves of high genus g that could make them more feasible than hyperelliptic curves of low g, or eventually, elliptic curves. A few hyperelliptic curve cryptosystems are proposed in literature, but their practical security is not yet carefully examined.

 

 

Comments