Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T02:30:55.609Z Has data issue: false hasContentIssue false
  • English
  • Français

Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems

Published online by Cambridge University Press:  17 April 2009

Joe Buhler  and
Neal Koblitz
Joe Buhler
Affiliation:
Department of Mathematics, Reed College, Portland OR 97202-8199, United States of America e-mail: [email protected]
Neal Koblitz
Affiliation:
Department of Mathematics, Box 354350, University of Washington, Seattle WA 98195, United States of America e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Using the LLL-algorithm for finding short vectors in lattices, we show how to compute a Jacobi sum for the prime field Fp in Q(e2πi/n) in time O(log3p), where n is small and fixed, p is large, and p = 1 (mod n). This result is useful in the construction of hyperelliptic cryptosystems.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 58 , Issue 1 , August 1998 , pp. 147 - 154
Copyright
Copyright © Australian Mathematical Society 1998

References

[1]Adleman, L.M., DeMarrais, J. and Huang, M., ‘A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields’, in Algorithmic Number Theory, Lecture Notes Comput. Sci. 877 (Springer-Verlag, Berlin, Heidelberg, New York, 1994), pp. 28–40.CrossRefGoogle Scholar
[2]Buchmann, J. and Williams, H.C., ‘On principal ideal testing in algebraic number fields’, J. Symbolic Comput. 4 (1987), 11–19.Google Scholar
[3]Cohen, H., A course in computational algebraic number theory (Springer-Verlag, Berlin, Heidelberg, New York, 1993).CrossRefGoogle Scholar
[4]Prey, G. and Ruck, H., ‘A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves’, Math. Comp. 62 (1994), 865–874.Google Scholar
[5]Gauss, C.F., Werke (Zweiter Band, Göttingen, 1976).Google Scholar
[6]Ireland, K. and Rosen, M.I., A classical introduction to modern number theory, (2nd edition) (Springer-Verlag, Berlin, Heidelberg, New York, 1990).CrossRefGoogle Scholar
[7]Koblitz, N., ‘Hyperelliptic cryptosystems’, J. Cryptology 1 (1989), 139–150.CrossRefGoogle Scholar
[8]Lenstra, A.K., Lenstra, H.W. Jr, and Lovász, L., ‘Factoring polynomials with rational coefficients’, Math. Ann. 261 (1982), 515–534.CrossRefGoogle Scholar
[9]Lenstra, H.W. Jr, ‘Euclid's algorithm in cyclotomic fields’, J. London Math. Soc. 10 (1975), 457–465.CrossRefGoogle Scholar
[10]Menezes, A., Okamoto, T. and Vanstone, S.A., ‘Reducing elliptic curve logarithms to logarithms in a finite field’, IEEE Trans. Inform. Theory 39 (1993), 1639–1646.CrossRefGoogle Scholar
[11]Weil, A., ‘Numbers of solutions of equations in finite fields’, Bull. Amer. Math. Soc. 55 (1949), 497–508.CrossRefGoogle Scholar