**HyperElliptic
Curve Cryptosystems**

**References**

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

* Seigo
Arita, Construction of secure *C*_{ab}
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. ------, 9^{th}
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, 6^{th} 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, 5^{th}
International Conference on Finite Fields and Applications (*Fq*5), -----,
199*x*-2000.

* E.
Furukawa, M. Kawazoe & T. Takahashi, Counting points on the Jacobian
variety of a hyperelliptic curve defined by *y*^{2} = *x*^{5} + *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, 7^{th} 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, 4^{th} 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, 1^{st} 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, 4^{th} 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, 11^{th} 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*(2^{n}),
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, 22^{nd}
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, 3^{rd} 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

*y*^{2} + *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* = 2*g* + 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.

*y*^{2}
+ *y* = *x*^{n} + *ax*^{n}^{–1} + … + 1 or *y*^{2} = *x*^{n} + *ax*^{n}^{–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*(2^{m}))
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 *n*_{1}
and *n*_{2}, where *n*_{2}|*n*_{1}. 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 F*_{q},*
and two divisors D and T in the jacobian J*(*C*, *F*_{q}),*
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.