Abstract
We investigate the discrete logarithm problem over jacobians of hyperelliptic curves suitable for public-key cryptosystems. We focus on the case when the definition field has small characteristic 2, 3, 5 and 7, then we present hyperelliptic cryptosystems that resist against all known attacks. We further implement our designed hyperelliptic cryptosystems over finite fields F2 n in software on Alpha and Pentium-II computers. Our results indicate that if we choose curves carefully, hyperelliptic cryptosystems do have practical performance.
Partially done while visiting in Columbia Univ. Computer Science Dept.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
L.M. Adleman, J. Demarrais and M. Huang, “A Subexponential Algorithm for Discrete Logarithm over the Rational Subgroup of the Jacobians of Large Genus Hyperelliptic Curves over Finite Fields„, Proc. of ANTS1, LNCS, vol. 877, Springer-Verlag, (1994), 28–40
J. Buhler and N. Koblitz, Joe Buhler and Neal Koblitz, “Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems,„, Bull. Austral. Math. Soc. (1998)
T. Beth and F. Scaefer, “Non supersingular elliptic curves for public key cryptosystems„, Advances in Cryptology-EUROCRYPT’ 91, Lecture Notes in Computer Science, 547, pp.316–327 (1991).
D.G. Cantor, “Computing in the Jacobian of a Hyperelliptic Curve„, Math. Comp, 48, No.177 (1987), 95–101
J. Chao, N. Matsuda, and S. Tsujii, “Efficient construction of secure hyperelliptic discrete logarithms„, Information and Communications Security, Springer-Verlag, LNCS 1334 (1997), 292–301.
J. Chao, K. Tanaka, and S. Tsujii, “Design of elliptic curves with controllable lower boundary of extension degree for reduction attacks„, Advances in Cryptology-Crypto’94, Springer-Verlag, (1994), 50–55.
G. Frey, “Aspects of DL-systems based on hyperelliptic curves„, Keynote Lecture in Waterloo-Workshop on Elliptic Curve Discrete Logarithm Problem, 4th of Nov. (1997).
G. Frey and H.G. Rück, “A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves„, Math. Comp, 62, No.206 (1994), 865–874
Robert Gallant, Robert Lambert and Scott Vanstone, “Improving the parallelized Pollard lambda search on binary anomalous„, A draft is available from http://grouper.ieee.org/groups/1363/contrib.html, (April, 1998)
N. Koblitz, “A Family of Jacobians Suitable for Discrete Log Cryptosystems„, Advances in Cryptology-Crypto’88, Springer-Verlag, (1990), 94–99
N. Koblitz, “Hyperelliptic Cryptosystems„, J.CRYPTOLOGY, 1 (1989), 139–150
N. Koblitz, “Algebraic Aspects of Cryptography„, Springer-Verlag, (1998)
A. Miyaji, T. Ono and H. Cohen, “Efficient Elliptic curve Exponentiation„, Information and Communications Security, Springer-Verlag, (1997), 282–290.
A.J. Menezes, T. Okamoto and S.A. Vanstone, “Reducing elliptic curve logarithm to logarithm in a finite field„, IEEE Trans. on IT, 39, (1993), 1639–1646
S.C. Pohlig and M.E. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance„, IEEE Trans. on IT, 24, (1978), 106–110
H.G. Rück, “On the discrete logarithms in the divisor class group of curves„, To appear in Math. Comp. (1997)
T. Satoh and K. Araki, “Fermat Quotients and the Polynomial Time Discrete Log Algorithm for Anomalous Elliptic Curves„, preprint, (1997)
I.A. Semaev, “Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p„, Math. Comp., Vol.76 (1998), 353–356.
N.P. Smart, “The Discrete Logarithm Problem on Elliptic Curves of Trace One„, preprint, (1997)
Y. Sakai, K. Sakurai And H. Ishizuka, “Secure hyperelliptic cryptosystems and their performance„, Pre-Proc. PKC’98 (1998)
H. Stichtenoth, “Algebraic Function Fields and Codes„, Springer-Verlag, (1993)
E.D. Win, A. Bosselaers, and S. Vandenberghe, “A Fase Software Implementation for Arithmetic Operations in GF(2n)„ Advances in Cryptology-Asiacrypt’96, Springer-Verlag, (1996), 65–76.
Michael Wiener And Robert Zuccherato, “Faster Attacks on Elliptic Curve Cryptosystems,“ A draft is available from http://grouper.ieee.org/groups/1363/contrib.html, (April, 1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sakai, Y., Sakurai, K. (1998). Design of Hyperelliptic Cryptosystems in Small Characteristic and a Software Implementation over F2 n . In: Ohta, K., Pei, D. (eds) Advances in Cryptology — ASIACRYPT’98. ASIACRYPT 1998. Lecture Notes in Computer Science, vol 1514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49649-1_8
Download citation
DOI: https://doi.org/10.1007/3-540-49649-1_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65109-3
Online ISBN: 978-3-540-49649-6
eBook Packages: Springer Book Archive