An alternative to the well-known RSA-Cryptosystem is given by Elliptic Curve Cryptography. Elliptic Curve Cryptosystems provide the same level of security as RSA at a reduced cost of computational effort. This workshop is about the various aspects of algebraic curves of low genus, beyond elliptic curves, with regard to the application in Cryptography.

Supported by the Graduate School Mathematical Analysis of Evolution, Information and Complexity, the workshop is meant for graduate students. It is hosted by the Institute of Pure Mathematics of the University of Ulm.

Please give a note to the organizers I. Bouw and R. Carls in case that you want to participate. Graduate students of other universities are welcome to participate in this workshop. Unfortunately, we are not able to give financial support to PhD students from the outside.

Hotels: Hotel zum Bäumle, Münster Hotel, Hotel am Rathaus, Hotel Ulmer Spatz, Hotel Ulmer Stuben

---

Invited speakers:

• C. Diem, University of Leipzig
• P. Gaudry, LORIA Nancy
• R. Gerkmann, University of Mainz
• C. Ritzenthaler, Université de la Méditerranée Marseille

---

Program

Please note the new location! (Campus Map)

Thursday 12/06
02.30pm-03.00pm		Coffee
03.00pm-04.00pm (He18, Room E20)	R. Carls	A p-adic quasi-quadratic point counting algorithm
04.15pm-05.15pm (He18, Room 220)	P. Gaudry	Hyperelliptic cryptosystems: from theory to practice
05.15pm-05.45pm		Reception
Friday 12/07
09.00am-10.00am (He18, Room 120)	R. Gerkmann	p-adic deformation and the computation of zeta functions
10.00-10.30am		Coffee
10.30am-11.30am (He18, Room 120)	C. Diem	Index Calculus for plane curves of low degree
11.30am-12.30pm (He18, Room 120)	C. Ritzenthaler	On Serre's problem for genus 3 curves

Abstracts

R. Carls: A p-adic quasi-quadratic point counting algorithm

This talk is about joint work with D. Lubicz. We outline an algorithm for point counting on ordinary abelian varieties over finite fields of odd characteristic. The asymptotic time complexity of our algorithm is quadratic in the degree of the finite field. Our method forms a generalization of both, Satoh's p-adic algorithm for elliptic curves and Mestre's 2-adic arithmetic-geometric mean method.

C. Diem: Index Calculus für ebene Kurven kleinen Grades

Index Calculus ist eine Methode, diskrete Logarithmen in abelschen Gruppen zu berechnen. Ursprünglich wurde die Methode für multiplikative Gruppen endlicher Körper entwickelt. Schon lange ist bekannt, dass man die Methode auch für diskrete Logarithmen in Grad 0 Klassengruppen von Kurven über endlichen Körpern anwenden kann, vorausgesetzt, dass das Geschlecht nicht zu klein ist. Die grundlegende Idee von Index Calculus ist hierbei wie folgt: Seien a, b Elemente einer abelschen Gruppe G. Gesucht ist ein x in N mit x*a = b, falls so ein x existiert. Man fixiert nun eine so genannte "Faktorbasis" F in G und versucht, Linearkombinationen von a und b als Summen über F zu schreiben. Wenn man genügend viele Relationen hat, versucht man, die Elemente aus F zu eliminieren undeine Relation alpha a + beta b = 0 mit alpha, beta in Z zu finden. So eine Relation liefert dann mit etwas Glück ein gesuchtes x. In dem Vortrag stelle ich einen Index Calculus Algorithmus für Kurven über endlichen Körpern vor, der besonders effizient ist, wenn man ihn auf Kurven anwendet, die durch ebene Modelle kleinen Grades gegeben sind. Die Faktorbasis ist hierbei eine Teilmenge der rationalen Punkte der Kurve.

P. Gaudry: Hyperelliptic cryptosystems: from theory to practice

Public key cryptography was invented in the 70's. A decade later, elliptic curves were proposed for building cryptosystems and soon after hyperelliptic cryptosystems were introduced. Although elliptic cryptosystems are now widely used in real-life products, hyperelliptic ones have come to maturity only recently. In this talk, we will discuss the progress made in the past ten years to make hyperelliptic cryptosystems as efficient, easy to use, and reliable as their elliptic analogues.

R. Gerkmann: p-adic deformation and computation of zeta functions

Like the first one this talk also deals with the computation of zeta functions of varieties over finite fields of small characteristic. The following approach is due to A. Lauder: One embeds the variety into an algebraic family which contains a fibre whose zeta function can easily be computed. The connection between the two varieties is then established by a p-adic differential equation that can be solved numerically. If one reformulates Lauder's approach within the language of rigid cohomology, then results about "classical" (singular) cohomology of complex varieties become applicable. This leads to generalizations of this algorithm to large classes of varieties, e.g. toric hypersurfaces or complete intersections in projective space. In special situations various optimizations are imaginable. If for instance f : X --> P^1 is a Galois covering with Galois group G, then the cohomology of X decomposes into several components which correspond to the irreducible representations of G. This reduces the dimension of the linear differential equations that have to be solved. Whereas the construction of "simple" fibres might be a problem in the general case (one needs varieties with a large automorphism group), in this case there is an easy way: the "degeneration" into a singular curve.

C. Ritzenthaler: On Serre's problem for genus 3 curves

Let (A,a) be a principally polarized abelian variety defined over a finite field k. If (A,a) is the Jacobian of a hyperelliptic curve over the algebraic closure K then it is the Jacobian of a curve over k. But if (A,a) is the Jacobian ofa non hyperelliptic curve over K then either (A,a) is a Jacobian over k or its quadratic twist is. In order to decide which case appears, several strategies have been suggested for the genus 3 case. We will review them briefly and then suggest a new strategy based on geometrical constructions.