Advances in Mathematics of Communications (AMC)

Relations between arithmetic geometry and public key cryptography

Pages: 281 - 305, Volume 4, Issue 2, May 2010      doi:10.3934/amc.2010.4.281

       Abstract        Full Text (293.4K)       Related Articles       

Gerhard Frey - Institute for Experimental Mathematics, University of Duisburg-Essen, Ellernstrasse 29, 45326 Essen, Germany (email)

Abstract: In the article we shall try to give an overview of the interplay between the design of public key cryptosystems and algorithmic arithmetic geometry. We begin in Section 2 with a very abstract setting and try to avoid all structures which are not necessary for protocols like Diffie-Hellman key exchange, ElGamal signature and pairing based cryptography (e.g. short signatures). As an unavoidable consequence of the generality the result is difficult to read and clumsy. But nevertheless it may be worthwhile because there are suggestions for systems which do not use the full strength of group structures (see Subsection 2.2.1) and it may motivate to look for alternatives to known group-based systems.
  But, of course, the main part of the article deals with the usual realization by discrete logarithms in groups, and the main source for cryptographically useful groups are divisor class groups.
  We describe advances concerning arithmetic in such groups attached to curves over finite fields including addition and point counting which have an immediate application to the construction of cryptosystems.
  For the security of these systems one has to make sure that the computation of the discrete logarithm is hard. We shall see how methods from arithmetic geometry narrow the range of candidates usable for cryptography considerably and leave only carefully chosen curves of genus $1$ and $2$ without flaw.
  A last section gives a short report on background and realization of bilinear structures on divisor class groups induced by duality theory of class field theory, the key concept here is the Lichtenbaum-Tate pairing.

Keywords:  Discrete logarithms, bilinear structures, divisor class groups, public key systems.
Mathematics Subject Classification:  11R65, 11R37, 11G20.

Received: July 2009;      Revised: November 2009;      Available Online: May 2010.