2003 Conferences

ECC 2003

Speaker
Florian Hess

Title
The GHS attack revisited

Abstract
The talk explains a generalization of the basic construction of the GHS attack in characteristic two and some further relevant results. This generalization applies to essentially the square of the number of elliptic curves to which the previous construction could be applied. The resulting curves need on the other hand no longer be hyperelliptic. The combination with isogenies, practical implications and possible further extensions are then discussed.



Speaker
Hugo Krawczyk

Title
Design and analysis of authenticated Diffie-Hellman protocols

Abstract
The design and analysis of key-exchange protocols is a central theme in applied cryptography. Formalizing the security of these protocols and designing them right has proven to be non-trivial. In recent years we have developed a sound methodology for both the design and analysis of such protocols, and applied it to some important protocols. In this talk we will survey some of these results using authenticated Diffie-Hellman exchanges as the main example.

Speaker
Tanja Lange

Title
Efficient arithmetic on (hyper-)elliptic curves over finite fields

Abstract
The talk is concerned with arithmetic on elliptic and hyperelliptic curves. We show how fast the arithmetic can get by clever choices of the coordinates and present special kinds of curves which allow even faster arithmetic using the Frobenius endomorphism.

For elliptic curves this has been used to achieve fast arithmetic for the past years. However, so far arithmetic in the ideal class group of hyperelliptic curves was performed using Cantor's algorithm which needs several inversions per group operation.

Starting with the work of Harley and improved by Miyamoto, Doi, Matsuo, Chao, and Tsuji and by Takahashi efficient explicit formulae are at hand. Meanwhile inversion-free systems have been studied allowing even hardware implementations and depending on the system, hyperelliptic curves can even be faster than elliptic curves.

Curve-endomorphisms allow to obtain further speed-up. We briefly present Koblitz curves, the generalized GLV method, and trace zero subvarieties.

Speaker
Reynald Lercier

Title
Algorithmic aspects of Mestre's p-adic point counting ideas

Abstract
We describe in this talk an efficient p-adic counting point algorithm for ordinary hyperelliptic curves of small genus defined over finite fields of characteristic two. This algorithm derives from ideas due to Mestre. We begin with a quick overview of the bibliography related to this field of research. Then, having introduced the p-adic background needed, we describe a first algorithm based on AGM iterations with quasi quadratic time complexity to count points on elliptic curves. We extend this algorithm to Borchardt iterations in order to obtain an algorithm for curves of genus two. We finally explain how the generalization to the hyperelliptic case due to Mestre can be combined with a generalization of the machinery that we have developed for elliptic curves in order to get an algorithm with the same complexity. We illustrate our talk with some computations that we have performed in finite fields of huge size for hyperelliptic curves of genus one, two and three.

Speaker
Ben Lynn

Title
Applications of bilinear maps

Abstract
Pairing-based cryptography has become a very active research area. Many novel cryptosystems have been proposed, each one depending on properties of bilinear maps such as the Tate pairing. In this talk we will discuss how the bilinear maps are used in cryptography. We also investigate methods for constructing pairing-friendly elliptic curves, and outline various optimizations for the pairing. Lastly we will mention several open problems.

Speaker
William Martin

Title
High confidence software and systems, an NSA perspective

Abstract
This talk focuses on the strategy and research agenda developed and being implemented by the High Confidence Software and Systems group at the National Security Agency. As background this talk will highlight several interrelated trends in technology, system requirements, and economics that are creating a new environment that challenges the limits of traditional engineering approaches. Following this introduction our three research components, which outline a continuum of research and development from theory to tool development to experimental evaluation and validation on real-world problems, will be presented. During the course of this discussion, each of these three research components will be motivated through a detailed examination of a specific research project that is being pursued.

Speaker
Christof Paar

Title
Hyperelliptic curve cryptosystems for embedded applications

Abstract
The next generation of IT applications might include scenarios in which your PDA communicates with your refrigerator, which in turn talks to your milk bottle. An important aspect in such pervasive computing application is security. Even though the hardware of such nodes is very inhomogeneous, a common factor is that they tend to be constrained with respect to computation, power, and memory. This constitutes a dilemma if we want to provide computationally intensive public-key algorithms. Public-key schemes are attractive for providing strong security solutions in pervasive applications. For this reason, it is very interesting to investigate alternatives to established public-key algorithms with respect to their suitability for constrained processors.

This talk will first give an introduction to pervasive computing and its security needs. We will then talk about the new results in the area of hyperelliptic curve cryptosystems (HECC), with a strong focus on the suitability of HECC for embedded platforms. We will show that a careful choice of parameters can allow HECC with 32 bit operands, which allows a very compact implementation on embedded processors.

Speaker
John Proos

Title
Security in the presents of decryption failures

Abstract
There exists public-key encryption schemes, such as NTRU, which have the interesting property that occasionally properly created ciphertexts do not decrypt correctly. Such decryption failures have typically been viewed as simply a nuisance and not as a security risk. However, recent attacks against NTRU which exploit its decryption failures to recover user's secret keys have shown that besides being a nuisance decryption failures can also pose a serious security risk. Attacks based on decryption failures have even been successful in recovering secret keys for padded versions of NTRU which were claimed to be provably secure. The ability to attack these ``provably secure'' versions of NTRU stems from the fact that the traditional definitions of encryption schemes and security do not encompass schemes with decryption failures.

In this talk we will discuss the implications of decryption failures in the security analysis of encryption schemes. As an illustration of the effect of decryption failures we shall discuss the fault in the provable security results for NTRU, review the decryption failure based attacks on NTRU and discuss the proposed countermeasures to these attacks.

Speaker
Jean-Jacques Quisquater

Title
2 or 3 side-channels for ECC

Abstract


Speaker
Pankaj Rohatgi

Title
Power, EM and all that: Is your crypto device really secure?

Abstract
This talk will describe recent advances which significantly expand the scope of side-channel cryptanalysis. The first advance is the exploitation of leakages from electromagnetic (EM) emanations. The EM channel enables side-channel attacks to be mounted against a large class of cryptographic devices where the unfiltered power supply is inaccessible. Even for smart-cards, the EM channel is shown to provide information not readily available from the power side-channel. The second advance, known as template attacks, is a superior signal analysis technique which dramatically reduces the number of samples needed for a side-channel attack. This technique is especially useful in settings where only a single side-channel signal is available, e.g., an ephemeral key is used.

This is joint work with Dakshi Agrawal, Bruce Archambeault, Suresh Chari and Josyula R Rao.

Speaker
Victor Shoup

Title
Practical verifiable encryption and decryption of discrete logarithms

Abstract
This work addresses the problem of designing practical protocols for proving properties about encrypted data. To this end, it presents a variant of the new public key encryption of Cramer and Shoup based on Paillier's decision composite residuosity assumption, along with efficient protocols for verifiable encryption and decryption of discrete logarithms (and more generally, of representations with respect to multiple bases). This is the first verifiable encryption system that provides chosen ciphertext security and avoids inefficient cut-and-choose proofs. The presented protocols have numerous applications, including key escrow, optimistic fair exchange, publicly verifiable secret and signature sharing, universally composable commitments, group signatures, and confirmer signatures.

Speaker
Edlyn Teske

Title
Weak fields for ECC

Abstract
We demonstrate that some finite fields, including ${\mathbb F}_{2^{210}}$, are weak for elliptic curve cryptography in the sense that any instance of the elliptic curve discrete logarithm problem for \emph{any} elliptic curve over these fields can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We discuss the implications of our observations to elliptic curve cryptography, and list some open problems.

This is joint work with Alfred Menezes and Annegret Weng.

Speaker
Nicolas Theriault

Title
Index calculus attack for hyperelliptic curves of small genus

Abstract
We present a variation of the index calculus attack by Gaudry which can be used to solve the discrete logarithm problem in the Jacobian of hyperelliptic curves. The new algorithm has a running time which is better than the original index calculus attack and the Rho method (and other square-root algorithms) for curves of genus $ \ge 3 $. We also describe another improvement for curves of genus $ \ge 4 $ (slightly slower, but less dependent on memory space) initially mentioned by Harley and used in a number of papers, but never analyzed in detailed.

Speaker
Eran Tromer

Title
Hardware-based implementation of factoring algorithms

Abstract
As many cryptographic schemes rely on the hardness of integer factorization, exploration of the concrete costs of factoring large integers is of considerable interest. Most research has focused on PC-based implementations of factoring algorithms; these have successfully factored 530-bit integers, but practically cannot scale much further. This talk will present new alternative implementations of factoring algorithms, based on custom-built hardware devices that achieve considerable parallelism "for free". These designs feature an interplay between algorithmic and technological aspects: by devising algorithms that take advantage of certain tradeoffs in chip manufacturing technology, efficiency is increased by many orders of magnitude compared to previous proposals. For example, using the new devices it appears possible to break a 1024-bit RSA key in one year at a cost of about $10M (previous predictions were in the trillions of dollars).

Speaker
Annegret Weng

Title
Distribution of group orders of abelian varieties

Abstract
We consider the frequency of prime or almost prime (i.e., prime up to a small cofactor) group orders of elliptic curves and higher dimensional abelian varieties. We present a summary of previous work by Koblitz, Galbraith and McKee, Miri and Murty and new results.