Algebraic Curves and Cryptography
6-7th of December 2007
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.
Hotel zum Bäumle,
Hotel am Rathaus,
Hotel Ulmer Spatz,
Hotel Ulmer Stuben
Please note the new location!
|03.00pm-04.00pm (He18, Room E20)
||A p-adic quasi-quadratic point counting algorithm
|04.15pm-05.15pm (He18, Room 220)
||Hyperelliptic cryptosystems: from theory to practice
|09.00am-10.00am (He18, Room 120)
||p-adic deformation and the computation of zeta functions
|10.30am-11.30am (He18, Room 120)
||Index Calculus for plane curves of low degree
|11.30am-12.30pm (He18, Room 120)
||On Serre's problem for genus 3 curves
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.