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.
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.
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.
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.
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.
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.
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.
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.
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.
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.