ECC 2004
SpeakerPaulo Barreto TitleThe Well-Tempered Pairing AbstractEfficiently 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. SpeakerPierrick Gaudry TitleDiscrete Logarithm in Elliptic Curves Over Extension Fields of Small Degree AbstractWe propose an algorithm for computing discrete logarithms in elliptic curves defined over finite fields of the form GF(p, with
^{n})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.
SpeakerMing-Deh Huang and Wayne Raskind TitleGlobal Methods for Discrete Logarithm Problems AbstractWe 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 TitleSecure Implementation of Elliptic Curve Cryptography AbstractThis 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. SpeakerNorbert Lütkenhaus TitleQuantum Key Distribution - Chances and Restrictions AbstractQuantum 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. SpeakerAlexander May TitleNew RSA Vulnerabilities Using Coppersmith's Method AbstractIn 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 < N*yield the factorization of the RSA-modulus^{0.25}*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*.
SpeakerKim Nguyen TitleCryptography & Travel Documents AbstractThe 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.
SpeakerMatt Robshaw TitleThe Advanced Encryption Standard: A Four Year Anniversary AbstractRijndael 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. SpeakerWerner Schindler TitleOptimizing the Efficiency of Side-Channel Attacks with Advanced Stochastical Methods AbstractIn 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. SpeakerJasper Scholten TitleCover Attacks on Trace-Zero Groups AbstractLet C be a curve of genus g, defined over a finite field
F. Consider the group of points on the Jacobian that
are defined over an extension field,
_{q}J. The trace-zero group
is the subgroup consisting of points for which the sum of all
_{C}(F_{qn})F-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 _{qn}/F_{q}(g,n) = (2,3), (1,5), or (1,7).
The idea is to find a suitable curve X defined over F
that admits a map to _{q}C. Then the DLP on the trace-zero group can be
transferred to a DLP on J, where index
calculus techniques can be applied. For our search of suitable _{X}(F_{q})X we use
Galois theory for curves.
SpeakerHovav Shacham TitleA New Life for Group Signatures AbstractGroup 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) SpeakerIgor Shparlinski TitlePseudorandom Points on Elliptic Curves AbstractWe 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). SpeakerNigel Smart TitleThe Link Between ECDHP and ECDLP Revisited AbstractIn 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. SpeakerThomas Wollinger TitleHardware Implementation of Hyperelliptic Curve Cryptosystems AbstractEncryption 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. |