2005 Conferences

ECC 2005


Speaker
Peter Beelen

Title
Lower Bounds for the Minimum Distance of an AG-Code

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

Speaker
Daniel J. Bernstein

Title
New Speed Records for Point Multiplication
Speaker
Claus Diem

Title
Index Calculus in Class Groups of Plane Curves of Small Degree

Abstract
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).
Speaker
Steven Galbraith

Title
Pairings on Hyperelliptic Curves

Abstract
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.
Speaker
Rob Gallant

Title
The Static Diffie-Hellman Problem

Abstract
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.
Speaker
Florian Hess

Title
Arithmetic on General Curves and Applications

Abstract
The talk surveys various algorithms for computing in the divisor class groups of general curves and discusses some applications.
Speaker
Lars R. Knudsen

Title
Cryptographic Hash Functions - Latest Developments
Speaker
Peter Landrock

Title
Practical Electronic Voting Schemes

Abstract
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!
Speaker
Kenneth G. Paterson

Title
Identity-Based Cryptography: Panacea or Pandemonium?

Abstract
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.
Speaker
Christophe Ritzenthaler

Title
p-adic Methods in Cryptography

Abstract
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 algorithms.
Speaker
Takakazu Satoh

Title
On Interpolation of Inverse Pairing Maps

Abstract
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.
Speaker
Martijn Stam

Title
Cyclotomic Subgroups in Cryptography

Abstract
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.
Speaker
Rainer Steinwandt

Title
Dedicated Hardware to Solve Sparse Systems of Linear Equations: State of the Art & Application to Integer Factoring

Abstract
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.
Speaker
Scott Vanstone

Title
Deployments of Elliptic Curve Cryptography

Abstract
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.
Speaker
Andre Weimerskirch

Title
Efficient and Secure ECC on Embedded Devices

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