2001 Conferences

ECC 2001

Speaker
Dan Bernstein

Title
A software implementation of NIST P-224

Abstract
This is the second in a series of three talks on nistp224, an easy-to-use software library to perform compressed Diffie-Hellman key exchange on the NIST P-224 elliptic curve at record-setting speeds. In this talk, I'll focus on x86 processors such as the Pentium III; I'll explain in detail how nistp224 performs field multiplication and elliptic-curve multiplication. In the first talk, I explained how nistp224 computes square roots. In the third talk, at the MAGC meeting in Urbana, I'll focus on non-x86 processors such as the UltraSPARC.



Speaker
Dan Bleichenbacher

Title
On the generation of DSA one-time keys

Abstract
This talk analyzes the digital signature algorithm (DSA). For each signature a secret random one-time key kj has to be generated. The standard proposes a method for generating these one-time keys, which is biased.

I present a heuristic attack exploiting this bias. Given sufficiently many known signature it is possible to find the secret key significantly faster than with previously known algorithms. For example, the secret key can often be found given 222 signatures in time 264 and with memory 240. The complexity of the attack does not depend on the group size p.


Speaker
Daniel Brown

Title
A security analysis of the elliptic curve digital signature algorithm

Abstract
In January 2000, the National Institute of Standards & Technology (NIST) approved the Elliptic Curve Digital Signature Algorithm (ECDSA) for use by the U.S. Government through publication of the Federal Information Processing Standards document, FIPS 186-2. However, within the academic cryptographic community, no provable security analyses have been directed specifically at ECDSA - until now. We consider the security of ECDSA under a variety of assumptions, such as the collision-resistance of the Secure Hash Algorithm SHA-1 and the semi-generic group model of an elliptic curve group. We also consider a variety of adversarial goals, including existential forgery by an adaptive chosen-message attack.


Speaker
Gerhard Frey

Title
Algebraic-geometric discrete logarithms: An overview

Abstract
The main task of public key cryptography is to provide highly efficient tools to exchange keys, sign electronic messages, authenticate members of a network and, sometimes, encrypt and decrypt messages by using simple protocols with clear and easy to follow implementation rules based on secure crypto primitives. It has turned out during the last 15 years that the discrete logarithm (DL) in groups of prime order can be used for these purposes.

The systems used today are all constructed by arithmetical-geometrical methods as class groups of orders in number fields or function fields, and since these objects have been studied for 100 years and longer we can rely on a well understood mathematical background.

The purpose of this lecture is explain the relevant constructions and to show how arithmetic geometry can be used in constructive and destructive ways. Especially it will turn out that Jacobian varieties of projective curves of small positive genus play a distinguished role with respect to shortness of keys, security, performance and key generation. This will explain why elliptic curves over prime fields or over fields of small characteristic and prime absolute degree are a very good choice for designing DL-systems.


Speaker
Pierrick Gaudry

Title
Algorithms for point counting on elliptic and hyperelliptic curves

Abstract
Counting points is a tricky task when implementing an elliptic or hyperelliptic cryptosystem. Even though random curves are thought to be the most secure ones, particular curves for which the number of points comes for free are still widely used.

We will give a survey of the best methods known for point counting on random elliptic and hyperelliptic curves. These methods differ for curves defined over a prime field and curves in characteristic 2. We shall give an emphasis to the latter case, for which a lot of progress have been achieved recently, following Satoh's algorithm breakthrough.


Speaker
Darrel Hankerson

Title
Performance comparisons of elliptic curve systems in software

Abstract
Implementing elliptic curve cryptographic schemes involves many design decisions including underlying field (prime, Mersenne-like prime, characteristic two, optimal extension), curve (randomly selected, Koblitz, Gallant), memory usage, and implementation language (C or assembler). We present and compare the results of our software implementation of these various flavours of elliptic (and hyperelliptic) curve systems.


Speaker
Florian Hess

Title
An extension of the GHS Weil descent attack

Abstract
The GHS Weil descent attack maps an elliptic curve discrete logarithm problem in characteristic two to an equivalent discrete logarithm problem on a hyperelliptic curve over a smaller finite field. Under quite special conditions this later problem can be solved easier. In the talk we review the basic technique and present an extension which applies under less (but arguably still quite) special conditions. We also discuss some implications.


Speaker
Raymond Laflamme

Title
Quantum Computing

Abstract
Advances in computing are revolutionizing our world. Present day computers advance at a rapid pace toward the barrier defined by the laws of quantum physics. The quantum computation program short-circuits that constraint by exploiting the quantum laws to advantage rather than regarding them as obstacles. Quantum computer accepts any superposition of its inputs as an input, and processes the components simultaneously, performing a sophisticated interference experiment of classical inputs. This ``quantum parallelism'' allows one to explore exponentially many trial solutions with relatively modest means, and to select the correct one. This has a particularly dramatic effect on factoring of large integers, which is at the core of the present day encryption strategies (public key) used in diplomatic communication, and (increasingly) in business. As demonstrated approximately five years ago, quantum computers could yield the most commonly used encryption protocol obsolete. Since then, it was also realized that quantum computation can lead to breakthroughs elsewhere, including simulations of quantum systems, implementation of novel encryption strategies (quantum cryptography), as well as more mundane applications such as sorting. I will describe recent work done in quantum computation, in particular the discovery and implementation of methods to make quantum information robust against corruption, both in theory and experiments. I will end with speculations about the field.


Speaker
Alfred Menezes

Title
Cryptographic implications of Weil descent

Abstract
In 1998, Frey proposed using Weil descent as a means to reduce the discrete logarithm problem in elliptic curves over characteristic two finite fields to the logarithm problem in abelian varieties over smaller underlying fields where subexponential-time methods may be applicable. In 2000, Gaudry, Hess and Smart showed how Frey's methodology could be used to reduce the ECDLP to the discrete logarithm problem in the Jacobian of a hyperelliptic curve. This talk will provide an overview of the Weil descent methodology and discuss its implications to the security of elliptic curve systems.


Speaker
Tatsuaki Okamoto

Title
Generic conversions for constructing IND-CCA2 public-key encryption in the random oracle model

Abstract
Until a few years ago, the description of a cryptosystem, together with some heuristic arguments for security, were enough to convince and to make a scheme to be widely adopted. Formal semantic security and further non-malleability against active attacks were just seen as theoretical properties. However, after multiple cryptanalyses of international standards, provable security has been realized to be important and even became a basic requirement. Therefore, several practical cryptosystems with the formal security requirements in the strongest sense, IND-CCA2 (non-malleable/semantically secure against adaptively chosen-cipphertext attacks), have been proposed. In my talk, I will introduce several generic conversion methods from a weakly secure public-key encryption (PKE) primitive to an IND-CCA2 PKE scheme in the random oracle model (ROM). I will show some applications of these conversions to the ellitic curve (EC) ElGamal scheme. As another application, I will also mention RSA-REACT and its advantage over the RSA-OAEP families. In addition, I may talk about the relationship among computational, decisional, and gap (oracle) problems such as DH, decisional DH (DDH) and gap DH (GDH) problems.


Speaker
Alice Silverberg

Title
Elliptic curves: The state of the art

Abstract
This talk will give a survey of recent number-theoretical advances concerning elliptic curves. We will introduce some of the major open questions about elliptic curves from a number theorist's point of view, and discuss recent progress that has been made towards their solutions. The topics will include the Conjecture of Birch and Swinnerton-Dyer, and questions about distributions of ranks of elliptic curves.


Speaker
Brian Snow

Title
We need more assurance in security products

Abstract
Commercial Security Systems, especially those provided in software, need to meet higher assurance standards than other typical commercial products do. Reasons for this assertion will be given, and a discussion of various ways to achieve it. Particular attention will be paid to Systems Engineering Techniques, Operating Systems, Software Modules, Hardware features, Third Party Validation, and Legal Constraints.


Speaker
Jerome A. Solinas

Title
Some computational speedups and bandwith improvements for curves over prime fields

Abstract
We present some new efficiency improvements for elliptic scalar multiplication. We begin with an optimized version of Shamir's method of evaluating expressions of the form $aP+bQ$. Not only is this expression commonly required in the execution of public-key protocols on elliptic curves, but it also provides faster methods of ordinary scalar multiplication. We present some curves for which this speedup is optimized.

We also address the problem of minimizing the bandwidth required to specify the parameters for an elliptic curve. In particular, we present a family of curves whose parameter sets are ID-based. This enables the specification of parameters with little or no extra bandwidth. This family of curves is also well suited to the Shamir speedup.


Speaker
Annegret Weng

Title
The CM-method for hyperelliptic curves

Abstract
Determining the group order of the Fp-rational points of a hyperelliptic Jacobian is a non-trivial problem. In our talk we give a generalization of the CM-method to hyperelliptic curves. The main idea is the construction of a Jacobian with given endomorphism ring. We present cryptographically interesting examples for genus two and three.