2004 Conferences
ECC 2004
Speaker
Roberto Avanzi
Title
The State of HEC Efficient Implementation
Abstract
Recently there has been tremendous progress in bringing the
performance of hyperelliptic curves close to that of elliptic curves.
In particular, research groups in Bochum and Essen improved the
explicit formulae for curves of low genus, in both even and odd
characteristic. This, together with specific arithmetic implementation
techniques, now shows that hyperelliptic curves can be considered as a
viable alternative to elliptic curves in real world applications. We
give a survey of these and related results, on both commodity personal
computers and embedded architectures, outlining some of the remaining
outstanding issues.
Speaker
Paulo Barreto
Title
The Well-Tempered Pairing
Abstract
Efficiently computable, non-degenerate bilinear maps (called pairings) have proven an invaluable tool for constructing a large and ever growing family of cryptosystems with novel and interesting properties. In this talk we review existing algorithms for efficient pairing computation from the point of view of both processing and storage requirements. In particular, we show how the choice of the actual pairing can lead to schemes with quite distinct properties; this suggests the possibility of tailoring the pairing to the intended application.
Speaker
Pierrick Gaudry
Title
Discrete Logarithm in Elliptic Curves Over Extension Fields of Small Degree
Abstract
We propose an algorithm for computing discrete logarithms in elliptic curves defined over finite fields of the form GF(pn), with n at least 3. Our strategy is based on a Weil restriction. The main difference with previous attacks is that we do not work with the Jacobian of a possibly complicated curve; we use an index calculus computation that works in any abelian variety.
As a result, we obtain an algorithm that runs asymptotically faster than Pollard's Rho method for any n greater than 2. The most interesting cases are n=3 and n=4, since for larger n the constants involved are so huge that the crossover point is far beyond any realistic situation.
Speaker
Ming-Deh Huang and Wayne Raskind
Title
Global Methods for Discrete Logarithm Problems
Abstract
We describe a global method for the discrete logarithm problem for the multiplicative group and for elliptic curves over finite fields. As is well known, index calculus methods are fairly successful in the case of the multiplicative group, but less so for elliptic curves. Our method is based on the construction of appropriate global Galois cohomology classes. This unified approach helps "explain" the difference in the success of index calculus in these two situations.
Speaker
Marc Joye
Title
Secure Implementation of Elliptic Curve Cryptography
Abstract
This talks surveys different techniques aiming at protecting implementations of elliptic curve cryptosystems. In particular, we review efficient ways to prevent side-channel leakage and fault attacks.
Speaker
Norbert Lütkenhaus
Title
Quantum Key Distribution - Chances and Restrictions
Abstract
Quantum key distribution is a method to provide a continuous stream of secret key bits with the security guaranteed by fundamental laws of nature. This method has some practical limitations: it needs some (short) initial secret key to kick-start the process, it is currently limited in the range of operations, and a suitable network structure has to be developed, since the basic idea is tied to point-to-point connections.
In this talk I will outline the basic principles and clarify the nature of the security claim. Then I will give a brief account of the current status of actual implementation of quantum key distribution.
Speaker
Alexander May
Title
New RSA Vulnerabilities Using Coppersmith's Method
Abstract
In 1996, Don Coppersmith proposed a method for finding small solutions of polynomial equations. This method in turn is based on the famous LLL lattice reduction algorithm of Lenstra, Lenstra and Lovasz. The talk gives a brief introduction to Coppersmith's method and shows new applications for the RSA cryptosystem:
- Partial Key Exposure Attacks on RSA: Assume an attacker succeeds to obtain a fraction of the bits of the secret key d. How many of the bits does he need in order to find the entire secret key? With the help of Coppersmith's method, one can construct polynomial time algorithms that find the entire key using only a fraction of the secret key bits, provided that the public key e is not too large.
- A Generalized Wiener Attack: In 1990, Wiener showed that small RSA secret keys d < N0.25 yield the factorization of the RSA-modulus N in polynomial time. Using Coppersmith's method, one can extend this attack to secret keys of the form d=d1/d2 modulo phi(N) with small d1 and d2.
- Computing d vs. Factoring: One can show that the problem of computing the RSA secret key is deterministic polynomial time equivalent to the problem of factoring the RSA-modulus N.
Speaker
Kim Nguyen
Title
Cryptography & Travel Documents
Abstract
The talk will deal with the introduction of contactless chip technology into MRTDs (Machine readable travel documents).
It will describe some aspects of the ongoing specification process with respect to:
- interoperable data exchange
- security mechanism
- the data stored on the MRTD was not changed
- the data stored on the MRTD cannot be read out without proper authorization.
Speaker
Matt Robshaw
Title
The Advanced Encryption Standard: A Four Year Anniversary
Abstract
Rijndael was chosen as the Advanced Encryption Standard on October 2, 2000. In this presentation we consider the state of the art in the analysis of this innovative cipher.
Speaker
Werner Schindler
Title
Optimizing the Efficiency of Side-Channel Attacks with Advanced Stochastical Methods
Abstract
In a side-channel attack the attacker guesses the secret key portion by portion where his decisions are based upon measurements of the running time, the power consumption or the electromagnetic radiation of the attacked device. The correctness of the particular guesses cannot be verified (at least not with certainty) until all parts of the key have been guessed. If the verification of the whole key guess (e.g. by checking a digital signature) fails this does not provide the positions of the wrong guesses.
In `real life' the number of measurements is usually limited, or it may be costly to perform a large number of measurements. From the attacker's point of view it is desirable to minimize the error probabilities for the guesses of the particular key parts (for a given collection of measurements) or vice versa, to minimize the number of measurements that is necessary for a successful attack. If the previous guesses have an impact on the guessing rule for the present key part it is also desirable to have criteria with which their correctness can be verified with reasonable probability.
In order to achieve these goals the side-channel information should be exploited in an optimal manner. Many papers on side-channel attacks have been published that present ingenious ideas but lack of sound mathematical methods. As a consequence, only a fraction of the given side-channel information is used, which in turn lowers the efficiency of these attacks. Moreover, it may be difficult to rate their risk potential and the effectivity of the proposed countermeasures.
In the last years the efficiency of a number of well-known attacks could be increased considerably (up to the factor 50) with advanced stochastical methods. Moreover, some attacks could be generalized, and new attacks were detected due to the better understanding of the situation. In particular, the concept of statistical decision theory and stochastical processes turned out to be very fruitful. The talk explains the mathematical concept at various examples.
Speaker
Jasper Scholten
Title
Cover Attacks on Trace-Zero Groups
Abstract
Let C be a curve of genus g, defined over a finite field Fq. Consider the group of points on the Jacobian that are defined over an extension field, JC(Fqn). The trace-zero group is the subgroup consisting of points for which the sum of all Fqn/Fq-conjugates is zero. These groups can be used in cryptography. Advantages are easy point counting, and efficient arithmetic. In this talk we discuss an attack on some of these groups, for the cases (g,n) = (2,3), (1,5), or (1,7). The idea is to find a suitable curve X defined over Fq that admits a map to C. Then the DLP on the trace-zero group can be transferred to a DLP on JX(Fq), where index calculus techniques can be applied. For our search of suitable X we use Galois theory for curves.
Speaker
Hovav Shacham
Title
A New Life for Group Signatures
Abstract
Group signatures, introduced by Chaum and van Heyst, provide anonymity for signers. Any member of the group can sign messages, but the resulting signature keeps the identity of the signer secret. In some systems there is a third party that can undo the signature anonymity (trace) using a special trapdoor.
Within the last two years, three developments have given a new life to group signatures: a new, simple security model; real-world applications; and new short and efficient constructions.
The new security model, introduced by Bellare et al. at Eurocrypt 2003, reduces group signature security to three properties: correctness, full-anonymity, and full-traceability.
New applications for group signatures include the trusted computing initiative (TCPA) and vehicle safety ad-hoc networks (DSRC). In each case, group signatures provide privacy guarantees for tamper-resistant embedded devices.
We describe a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. Security of our group signature is based on the Strong Diffie-Hellman assumption and a new assumption in bilinear groups called the Decision Linear assumption. We prove security of our system, in the random oracle model, using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi.
(joint work with Dan Boneh and Xavier Boyen)
Speaker
Igor Shparlinski
Title
Pseudorandom Points on Elliptic Curves
Abstract
We give a survey of recent results on the distribution and other properties of various sequences of points on elliptic curves which have been recommended as sources of pseudorandom points on elliptic curves. We also discuss an associated issue on various lower bounds on the orders of points on elliptic curves.
Joint work with (mainly): Florian Hess (U. of Bristol), Tanja Lange (U. of Bochum), and Florian Luca (UNAM).
Speaker
Nigel Smart
Title
The Link Between ECDHP and ECDLP Revisited
Abstract
In this talk, we will re-examine the reduction of Maurer and Wolf of the discrete logarithm problem to the Diffie-Hellman problem. We shall give a precise estimate for the number of operations required in the reduction, and then use this to estimate the exact security of the elliptic curve variant of the Diffie-Hellman protocol for various elliptic curves defined in standards.
Speaker
Thomas Wollinger
Title
Hardware Implementation of Hyperelliptic Curve Cryptosystems
Abstract
Encryption schemes are used in a variety of different applications to ensure security services. The implementation of this cryptographic primitives are therefore very application dependent. The Hyperelliptic curve cryptosystem is one of the cryptographic primitives that was lately given a lot of attention due to the short operand size compared to other algorithms.
In the first part of the talk we are going to discuss general issues of hardware implementations of cryptographic algorithms, like parallelism on different levels and clock rate. Afterwards, we are going to introduce three different design options implementing a genus-2 hyperelliptic curve coprocessor using affine coordinates. The three different implementations rang from high speed to moderate area. Our hardware implementation is one of the few using explicit group operation for HECC.
