Lower Bounds for the Minimum Distance of an AG-Code
Coding theory became important when the need arose to send information
over a noisy channel. This theory indicates how to add redundancy to a
message in such a way that (at least some) errors that occur during the
transmission, can be corrected afterwards. Nowadays coding theory has
many applications, for example in CD- and DVD-players, but also in
cryptography (e.g. the McEliece cryptosystem).
The codes C I will consider, can be described as a k-dimensional
linear subspace of Fn, with F a finite field.
A parameter that gives information about how many errors can be
corrected is the minimum distance d(C), which is the
minimal Hamming-weight of a non-zero codeword.
There are fruitful applications of algebraic geometry in coding theory
(like in the case of cryptography). The order bound gives an in general
very good lower bound for the minimum distance of the AG-codes (algebraic
geometry codes) that arise from this application. In my talk I will explain
the order bound and give a way to improve this bound. As an illustration,
I will indicate how a lower bound can be obtained for the minimum distance
of some codes coming from the Hermitian curve.
Daniel J. Bernstein
New Speed Records for Point Multiplication
Index Calculus in Class Groups of Plane Curves of Small Degree
We present a novel index calculus algorithm for the discrete logarithm
problem (DLP) in degree 0 class groups of curves over finite fields. A
heuristic analysis of our algorithm indicates that asymptotically for
varying q, "essentially all" instances of the DLP in degree
0 class groups of curves represented by plane models of a fixed degree
d over Fq can be solved in an expected time
of Õ(q2 -2/(d-2)).
A particular application is that heuristically, "essentially all"
instances of the DLP in degree 0 class groups of non-hyperelliptic curves
of genus 3 (represented by plane curves of degree 4) can be solved in an
expected time of Õ(q).
Pairings on Hyperelliptic Curves
I will give a survey of new results relating to pairings on curves in
cryptography. In particular, I will discuss some implementation
results on supersingular genus 2 curves which lead to cryptographic
protocols which are faster than comparable protocols for elliptic
curves. Much of this talk will be about joint work with Barreto, O
hEigeartaigh and Scott.
The Static Diffie-Hellman Problem
In this talk we describe an algorithm for finding the discrete
logarithm of an arbitrary group element Q. The algorithm requires
as input a function that solves a special case of the Diffie-Hellman
problem, called the static Diffie-Hellman problem for Q. Some
protocols and environments provide such a function to adversaries, in
which case the algorithm may be interpreted as an attack which finds a
private key. The algorithm can also be interpreted as a reduction
relating the hardness of computing discrete logarithms with the
hardness of solving Diffie-Hellman instances.
Arithmetic on General Curves and Applications
The talk surveys various algorithms for computing in the divisor class
groups of general curves and discusses some applications.
Lars R. Knudsen
Cryptographic Hash Functions - Latest Developments
Practical Electronic Voting Schemes
Cryptomathic have - together with the research group of Ivan Damgaard
at Aarhus University - been working on cost saving and practical yet
secure Electronic Voting Schemes since 2001. The presentation will
highlight the cryptographic features we have focused on as well as a
number of practical challenges. Electronic Voting offers quite intriguing
applications of cryptographic techniques, including homomorphic
encryption, where elliptic curves are particularly attractive and thus can
play a fundamental role in building effective solutions. It is however
important to choose the parameters right, as we need to be able to solve
the discrete log problem to exploit the homomorphic property!
Kenneth G. Paterson
Identity-Based Cryptography: Panacea or Pandemonium?
In this talk, we will examine some of the practical key management
problems that arise when using public key cryptography. We will then
discuss how these problems can be addressed by traditional,
certificate-based PKIs, and by identity-based and related
infrastructures. Along the way, we'll look at some of the applications
that have been proposed for identity-based cryptography.
p-adic Methods in Cryptography
We are going to show how p-adic (actually 2-adic) methods can be used
to construct cryptosystems based on curves in two ways : by fast point
counting in genus 1,2 and 3 or by CM-construction in genus 2. These
two different constructions are based on the Arithmetic-Geometric-Mean
On Interpolation of Inverse Pairing Maps
If we can construct an efficient algorithm for a group homomorphism
from a subgroup of the multiplicative group of a finite field to an
elliptic curve (an inverse pairing map), we can conclude that the
ECDLP for the curve is not easier than the finite field DLP. However,
in EuroCrypt 2001, E. Verheul proved that the existence of such
algorithm implies that both DLP and ECDLP are efficiently solved.
Since then, it is widely believed that there is no such efficient
algorithm. In my talk, I prove some non-vanishing theorems of
coefficients in interpolation of an inverse pairing map.
Cyclotomic Subgroups in Cryptography
In this talk we will discuss the cryptographic applications of
cyclotomic subgroups of finite fields. These subgroups can be regarded
as algebraic tori and are the basis of the cryptosystems LUC and
XTR. They also appear naturally in pairing-based cryptography, since
pairings typically map into the cyclotomic subgroup (and not the full
finite field). Recent advances (CEILIDH and beyond) concerning
compression of elements in cyclotomic subgroups are also discussed.
Dedicated Hardware to Solve Sparse Systems of Linear Equations: State
of the Art & Application to Integer Factoring
The talk surveys recent hardware designs proposed for solving sparse
systems of linear equations as occurring in NFS-based integer
factoring. The main focus is on a recent proposal of Geiselmann,
Shamir, Tromer and S. Based on current parameter estimates for the
NFS, it appears realistic that this design allows to handle the linear
algebra step of an NFS-based 1024 bit factorization.
For applying the proposed design to sparse systems of linear equations
over (small) ground fields different from GF(2) no
fundamental hurdles are expected. Hence applying such a dedicated
circuitry in contexts other than NFS-based integer factoring could be
an attractive option.
Deployments of Elliptic Curve Cryptography
ECC is being used to secure many applications in wireless
communications, classified government communications, digital rights
management, digital postal marks, and check clearing. In this talk we
will discuss the technical merits and advantages of using ECC in
selected applications that are being deployed in Canada and the US.
Efficient and Secure ECC on Embedded Devices
Today, there are more and more applications planned where security is an
enabler, in particular for low-cost 8 or 16-bit micro-controllers in the
consumer market. The cryptographic implementation must be efficient and
secure without raising the device's cost. It is well known that ECC is a
good match for such a scenario. We derive requirements for an ECC
implementation running on low-cost devices and show how to combine
efficiency with a secure implementations, e.g. to prevent side-channel
attacks. Furthermore, we give an overview of performance values.