Abstract
Frey and Rück gave a method to transform the discrete logarithm problem in the divisor class group of a curve over \( \mathbb{F}_q \) into a discrete logarithm problem in some finite field extension \( \mathbb{F}_{q^k } \) . The discrete logarithm problem can therefore be solved using index calculus algorithms as long as k is small.
In the elliptic curve case it was shown by Menezes, Okamoto and Vanstone that for supersingular curves one has k ⪯ 6. In this paper curves of higher genus are studied. Bounds on the possible values for k in the case of supersingular curves are given which imply that supersingular curves are weaker than the general case for cryptography. Ways to ensure that a curve is not supersingular are also discussed.
A constructive application of supersingular curves to cryptography is given, by generalising an identity-based cryptosystem due to Boneh and Franklin. The generalised scheme provides a significant reduction in bandwidth compared with the original scheme.
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
R. Balasubramanian and N. Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm., J. Cryptology, 11 no. 2 (1998) 141–145.
D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, in J. Kilian (ed.), Crypto 2001, Springer LNCS 2139 (2001) 213–229.
J. Buhler and N. Koblitz, Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems, Bull. Aust. Math. Soc., 58, No.1 (1998) 147–154.
D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp., 48 (1987) 95–101.
H. Cohen, A course in computational number theory, Springer GTM 138 (1993).
I. Duursma, P. Gaudry and F. Morain, Speeding up the discrete log computation on curves with automorphisms, in K. Y. Lam et al (eds.), Asiacrypt’ 99, Springer LNCS 1716, (1999) 103–121.
A. Enge, The extended Euclidean algorithm on polynomials and the computational efficiency of hyperelliptic cryptosystems, Designs, Codes and Cryptography, 23 (2001) 53–74.
G. Frey, 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.
G. Frey, M. Müller and H.-G. Rück, The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems, IEEE Trans. Inform. Theory, 45, no. 5 (1999) 1717–1719.
S. D. Galbraith, S. Paulus and N. P. Smart, Arithmetic on superelliptic curves, To appear in Math. Comp.
S. D. Galbraith, Supersingular curves in cryptography (full version), available from the author’s web pages.
P. Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, in B. Preneel (ed.), Eurocrypt 2000, Springer, LNCS 1807 (2000) 19–34.
R. Harley, Rump session talk, Eurocrypt 2001, (2001).
A. Joux, A one round protocol for tripartite Diffie-Hellman, in W. Bosma (ed.), ANTS-IV, Springer LNCS 1838 (2000) 385–393.
K. S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, preprint (2001).
N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1, no. 3 (1989) 139–150.
N. Koblitz, A family of jacobians suitable for discrete log cryptosystems, in S. Goldwasser (ed.), Crypto’ 88, Springer LNCS 403 (1990) 94–99.
N. Koblitz, An elliptic curve implementation of the finite field digital signature algorithm, in H. Krawczyk (ed.), Crypto’ 98, Springer LNCS 1462 (1998) 327–337.
S. Lang, Algebra, 3rd ed., Addison-Wesley, 1993.
K.-Z. Li and F. Oort, Moduli of supersingular abelian varieties, Springer LNM 1680 (1998).
Yu. I. Manin, The theory of commutative formal groups over fields of finite characteristic, Russ. Math. Surv., 18, No. 6 (1963) 1–83.
Yu. I. Manin, The Hasse-Witt matrix of an algebraic curve, Translations, II Ser., Am. Math. Soc., 45 (1965) 245–264.
A. J. Menezes, T. Okamoto and S. A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inf. Theory, 39, No. 5 (1993) 1639–1646.
F. Oort, Subvarieties of moduli spaces, Inv. Math., 24 (1970) 95–119.
H.-G. Rück, Abelsche varietäten niderer dimension über endlichen körpern, Habilitation Thesis, University of Essen (1990).
H.-G. Rück, On the discrete logarithm in the divisor class group of curves, Math. Comp., 68, No.226 (1999) 805–806.
Y. Sakai, K. Sakurai and H. Ishizuka, Secure hyperelliptic cryptosystems and their performance, in H. Imai et al. (eds.), Pkc’ 98, Springer LNCS 1431 (1998) 164–181.
A. Shamir, Identity-based cryptosystems and signature schemes, In G.R. Blakley and D. Chaum (eds.), Crypto’ 84, Springer LNCS 196 (1985) 47–53.
J. H. Silverman, The arithmetic of elliptic curves, Springer GTM 106, (1986).
N. Smart, On the performance of hyperelliptic cryptosystems, in J. Stern (ed.), Eurocrypt’ 99, Springer LNCS 1592 (1999) 165–175.
A. Stein and E. Teske, Explicit bounds and heuristics on class numbers in hyperelliptic function fields, To appear in Math. Comp., University of Waterloo technical report CORR 99-26 (1999).
H. Stichtenoth, Die Hasse-Witt-invariante eines kongruenzfunktionenkörpers, Arch. Math., 33, No. 4 (1980) 357–360.
H. Stichtenoth, Algebraic function fields and codes, Springer Universitext (1993).
H. Stichtenoth and C. Xing, On the structure of the divisor class group of a class of curves over finite fields, Arch. Math., Vol. 65 (1995) 141–150.
J. Tate, Classes d’isogénie de variétés abéliennes sur un corps fini (d’après T. Honda), Sém. Bourbaki, Exp. 352, Springer LNM 179 (1971) 95–110.
E. R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, in B. Pfitzmann (ed.), Eurocrypt 2001, Springer LNCS 2045 (2001) 195–210.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Galbraith, S.D. (2001). Supersingular Curves in Cryptography. In: Boyd, C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45682-1_29
Download citation
DOI: https://doi.org/10.1007/3-540-45682-1_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42987-6
Online ISBN: 978-3-540-45682-7
eBook Packages: Springer Book Archive