Note: The titles and abstracts of the plenary speakers at the 2nd Midwest Arithmetical Geometry in Cryptography (MAGC) workshop (November 17-19) are given below. For more information, see main page.

Gerhard Frey

Institut für Experimentelle Mathematik, Essen, Germany

1) Discrete logarithms and algebraic realizations
This lecture gives an introduction to the use of cyclic groups in public key cryptography, generic attacks like baby-step/giant-step or Pollard-Rho and, motivated by the classical DL in the multiplicative group and by elliptic curves, the approach to use "group schemes" like abelian varieties (without precise definitions of course).

2) Computing in ideal classes of polynomial orders and especially quadratic orders (corresponding to elliptic and hyperelliptic curves)
Abelian varieties are specialized to Jacobians and hence to divisor class groups of function fields. Some methods to compute their order are mentioned (ref. to Morain's lecture) and then the relation to ideal class groups of orders in the function fields is explained. Explicit examples will be hyperelliptic function fields as generalizations of elliptic fields.

3) The role of the Frobenius automorphism in cryptography
The Tate pairing is explained (down to earth) and some applications (like to the Diffie-Hellman decision problem) are given. The (affine) restriction of scalars is defined and consequences for the security of DL-systems based on elliptic curves not defined over prime fields are given.

Alfred Menezes

Certicom Corp. and Centre for Applied Cryptographic Research, University of Waterloo, Canada

1) Introduction to elliptic curve cryptography.
This lecture will summarize the background mathematics needed for elliptic curve cryptography. We will then provide a historical overview of elliptic curve cryptography, and discuss recent progress in its standardization, commercial acceptance, and deployment.

2) Discrete logarithm cryptographic protocols.
The notion of provable security is reviewed. We then discuss how the assumed intractability of the discrete logarithm problem can be used to devise protocols for encryption, signatures and key agreement that can be *proven* to meet their cryptographic goals.

3) Efficient implementation of elliptic curve cryptography.
This lecture will provide an overview of several issues that arise in the efficient software implementation of elliptic curve cryptography. The focus will be on the finite fields and elliptic curves in FIPS 186-2 that are recently recommended for US Federal Government use.

François Morain

Laboratoire d'Informatique de l'École Polytechnique, France

1) Basics on point counting algorithms: Shanks's baby steps/giant steps algorithms; using collisions a` la Pollard; introduction to Schoof's algorithm for elliptic curves.

2) Schoof's algorithm for elliptic curves, and the ideas of Elkies-Atkin; isogeny computations (Couveignes, Lercier); Satoh's algorithm. Possible extensions to genus 2.

3) Discrete logarithm computation: Shanks again, collisions; smooth divisors, index calculus and Gaudry's approach for small genus and its links with Weil descent.

Tanja Lange

Institut für Experimentelle Mathematik, Essen, Germany

Fast arithmetic on hyperelliptic Koblitz curves.
Abstract: The Koblitz or subfield curves offer a large variety of groups suitable for cryptography. We show how to derive a fast group operation by using the Frobenius automorphism and give evidence that there are many groups obtainable having almost prime order.

Kumar Murty

University of Toronto

An application of sieve methods to elliptic curves
Abstract: Given an elliptic curve E over the rationals which has no torsion, Koblitz has conjectured that the number of primes p less than x for which the group of points E(F_p) is of prime order is asymptotic to C_E x/(log x)^2 for some constant C_E depending only on E. Assuming the GRH, we show that for some constant c > 0, there are more than cx/(log x)^2 primes p less than x for which E(F_p) has at most 16 prime divisors. This is joint work with Ali Miri.

Joachim Rosenthal

University of Notre Dame

Using Low Density Parity Check Codes in the McEliece Cryptosystem.
This is joint work with Chris Monico and Amin Shokrollahi. Abstract: We propose a new flavor of McEliece's cryptosystem that uses a Low Density Parity Check Code (LDPCC) in place of the usual Goppa code. Using a LDPCC allows for larger block lengths and the possibility of a combined error correction/encryption protocol.

Rich Schroeppel

Sandia National Labs and University of Arizona

Elliptic Curve Point Halving Wins Big.
Abstract: A new operation on elliptic curve points, Halving, leads to substantial performance improvements in elliptic curve cryptography.

Alice Silverberg

MSRI and Ohio State University

Ranks of elliptic curves in families of quadratic twists
Abstract: The rank of an elliptic curve is a measure of the number of solutions of the cubic equation that defines the curve. We will give an overview of questions about ranks of elliptic curves, and will discuss some density results relating to the search for elliptic curves of large rank.

Additional Talks This Week

Tanja Lange

Speeding up the arithmetic on hyperelliptic Koblitz curves via Frobenius
Abstract: We introduce a special class of hyperelliptic curves called Koblitz curves. These are curves over a finite field Fqn, q small prime power, which are already defined over Fq. These curves turn out to be a large source of groups suitable for cryptography. The main operation in for example the Diffie-Hellman key-exchange is the computation of m times a group element. One of the big advantages of these curves is that they allow to speed up this step. We explain how the Frobenius automorphism is used and give details on the involved algorithms. For the performance of the algorithms we establish bounds and give numerical evidence for them. Furthermore we provide several examples of suitable curves.

Kumar Murty

The least prime in a conjugacy class
Abstract: Given an arithmetic progression, a classical problem in number theory is to estimate the size of the smallest prime in that progression. In this talk, we consider the generalization of this problem to estimating the size of the smallest prime which has a prescribed splitting type in an extension field. After discussing known and conjectured bounds, we consider applications to elliptic curves.