2006 Conferences

ECC 2006


Speaker
Daniel J. Bernstein

Title
Elliptic vs. hyperelliptic, part 1

Abstract
Last year's speed records for Diffie-Hellman software were set with a Montgomery-form elliptic curve. Is it possible to achieve even better scalar-multiplication speeds with a Gaudry-form hyperelliptic curve? Exactly how fast is arithmetic modulo 2127-1, compared to arithmetic modulo 2255-19?

Speaker
Xavier Boyen

Title
Practical aspects of identity-based encryption.

Abstract
In this talk, I will discuss practical uses of pairing-based cryptography, and identity-based encryption in particular. The talk will cover a number of issues, ranging from basic security requirements and the threats being addressed, to the selection of efficient algorithms, their instantiation, parameterization, implementation, and deployment. Time-permitting, I will also review some recent algorithmic developments of interest.
Speaker
Reinier Bröker

Title
Constructing elliptic curves for cryptography

Abstract
We present an algorithm that easily constructs elliptic curves that can readily be used for cryptography, and we explain why it should be expected to do so.

The algorithm makes use of auxiliary polynomials, called class polynomials. The classical approach for computing these polynomials uses the modular j-function. We explain how to use ``smaller functions'' instead of j to gain a constant factor in the size of the coefficients of the polynomials. The factor gained depends on the function used. Using results on gonality of modular curves we give upper bounds on the factor that we can gain.
Speaker
Isabelle Déchène

Title
Generalized Jacobians: Natural candidates for DL-based cryptography

Abstract
Generalized Jacobians are natural candidates to use in discrete logarithm (DL) based cryptography. Indeed, the ElGamal, Elliptic and Hyperelliptic Curve Cryptosystems as well as XTR, LUC and CEILIDH can all be interpreted in terms of generalized Jacobians. However, usual Jacobians and algebraic tori are currently the only generalized Jacobians used in cryptography.

These observations thus motivate the study of the simplest nontrivial generalized Jacobians of an elliptic curve, since they are in fact semi-abelian varieties. In this talk, we will see that this family satisfies the four basic requirements for a group to be suitable for DL-based cryptography. Namely, that the group elements can be represented in a compact form, that the group operation can be performed efficiently, that the discrete logarithm problem is believed to be intractable, and that the group order can be efficiently computed. This thus shows the existence of a family of generalized Jacobians, which are neither Jacobians nor tori, that are applicable in cryptography.
Speaker
Claus Diem

Title
An index calculus algorithm for non-singular plane curves of high genus

Abstract
We present an index calculus algorithm for the discrete logarithm problem in degree 0 class groups of non-singular plane curves of high genus over finite fields. A heuristic analysis of the algorithm gives rise to the following heuristic result: Let us consider the discrete logarithm problem in degree 0 class groups of non-singular plane curves over a fixed finite field. Then "essentially all" instances of this DLP can be solved in an expected time of L[1/3 + \epsilon] for any \epsilon > 0.
Speaker
Andreas Enge

Title
An L(1/3+\epsilon) algorithm for the discrete logarithm problem in low degree curves

Abstract
Starting with the work by Adleman, DeMarrais and Huang more than ten years ago, it has been well-established that the discrete logarithm problem in Jacobians of curves of high genus over finite fields is easier to solve than in elliptic curves of the same size. Letting L(\alpha, c) = e^{(c + o (1)) (g \log q)^\alpha (\log (g \log q))^{1 - \alpha}} denote the subexponential function with respect to the curve genus g and the cardinality of the finite field q, the algorithms for computing discrete logarithms in high genus curves have a complexity of L(1/2,c). This is in contrast on one hand to elliptic curves, for which so far only exponential algorithms are known except for some rare special cases, but also to the computation of discrete logarithms in finite prime fields, for which the number field sieve yields a more efficient algorithm in L(1/3,c).

We present the first subexponential algorithm with an exponent \alpha < 1/2 to attack the discrete logarithm problem in a class of algebraic curves. The curves are characterised by their total degree being relatively low with respect to their genus. The algorithm has a complexity of L(1/3,c) for computing the group structure. The discrete logarithm problem itself is solved in time L(1/3 + \epsilon, 0).

This is joint work with Pierrick Gaudry.
Speaker
David Freeman

Title
Methods for constructing pairing-friendly elliptic curves

Abstract
The practicality of pairing-based cryptography depends on our ability to generate pairing-friendly elliptic curves with various embedding degrees. In this talk, we present and compare the known methods for constructing pairing-friendly elliptic curves of cryptographic size. We describe three general strategies for constructing such curves. One succeeds in producing curves of prime order, but with restricted embedding degree, while the other two produce curves with arbitrary embedding degree, but having a smaller prime-order subgroup.
Speaker
Tanja Lange

Title
Elliptic vs. hyperelliptic, part 2

Abstract
There's more to the world than software for large-characteristic scalar multiplication on particular curves. How fast are hyperelliptic curves in general? How fast are they in characteristic 2? How fast are they for pairings? When are hyperelliptic curves better than elliptic curves?
Speaker
Kristin Lauter

Title
Cryptographic hash functions from expander graphs

Abstract
In this talk we propose constructing provable collision resistant hash functions from expander graphs. As examples, we investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer's Ramanujan graphs, (the set of supersingular elliptic curves in characteristic p with l-isogenies, l a prime different from p), then collision resistance follows from the hardness of computing isogenies between supersingular elliptic curves. This is joint work with Denis Charles and Eyal Goren.
Speaker
Laurie Law

Title
Finding invalid signatures in pairing-based batches

Abstract
Batch verification techniques can speed up the process of verifying large sets of digital signatures. When a batch verification fails, it is often necessary to quickly identify the bad signatures in the batch. This talk will present improved techniques for identifying these invalid signatures that work particularly well with certain pairing-based signatures schemes.
Speaker
Dan Page

Title
Compilers in (elliptic curve) cryptography

Abstract
The increasing ubiquity of mobile computing devices has presented programmers with a problem. On one hand mobile devices are required to be as compact and low-power as possible; on the other hand they are increasingly required to perform complex computational tasks. This dichotomy is further complicated by the issue of (physical) security which represents a significant problem within many mobile applications. We present results from our initial work on using compiler techniques to assist programmers in this context. Specifically we look at automatic specialisation of field arithmetic, language level support for cryptography, and problems arising from dynamic compilation.
Speaker
Jan Pelzl

Title
Cost estimates for ECC attacks with special-purpose hardware

Abstract
The utilization of Elliptic Curves (EC) in cryptography is very promising because of their resistance against powerful index-calculus attacks. Providing a similar level of security as RSA, ECC allows for efficient implementation due to a significantly smaller bit size of the operands. It is widely accepted that the only feasible way to attack actual cryptosystems, if at all, is the application of dedicated hardware. In times of continuous technological improvements and increasing computing power, the question of the security of ECC against attacks based on special-purpose hardware arises.

This talk presents an overview of hardware-based attacks against (generic) ECC over binary and prime fields. An architecture and the corresponding FPGA implementation of an attack against ECC over prime fields will be discussed in detail. The multi-processing hardware architecture is based on the Pollard-Rho method which is, to our knowledge, currently the most efficient attack against ECC. With a proof-of-concept implementation on an FPGA, a fairly accurate estimate about the cost of a hardware-based attack against ECC with current bit lengths can be given.
Speaker
Oliver Schirokauer

Title
Extending the special number field sieve

Abstract
We define the weight of an integer N to be the smallest w such that N can be represented as $\sum_{i=1}^w \epsilon_i 2^{c_i}$, with $\epsilon_1, \ldots, \epsilon_w \in \{1,-1\}$. Since arithmetic modulo a prime of low weight is particularly efficient, it is tempting to use such primes in cryptographic protocols. In this talk, I will describe an extension of the special number field sieve which can be used to compute logarithms in finite fields having low-weight characteristic and will consider the security implications for systems which depend on the difficulty of this problem. In addition, I will briefly discuss an idea to speed up the method which may also be of use in the case that the characteristic is of the form f(c) where f has small coefficients and c is large.
Speaker
Michael Scott

Title
Implementing cryptographic pairings

Abstract
In this talk we attempt to review the state-of-the-art in pairing implementation. Starting with a basic Miller algorithm for the Tate pairing we show how to successively apply a series of optimizations and tricks to improve performance. We will concentrate on the case of non-supersingular prime characteristic elliptic curves, although many of the optimizations equally apply to the cases of supersingular elliptic and hyperelliptic curves. We also discuss optimal implementation of extension field arithmetic.
Speaker
Igor Shparlinski

Title
Distribution of elliptic curves for pairing-based cryptography

Abstract
We present some theoretic and heuristic estimates for the number of elliptic curves with low embedding which is essential for their applicability in pairing based cryptography. We also give estimates for the number of fields over which such curves may exist. The main ideas behind the proofs will be explained as well. Finally, we give a heuristic analysis of the so-called MNT algorithm and show that it produces a rather "thin" sequence of curves.
Speaker
Alice Silverberg

Title
Using primitive subgroups in cryptography

Abstract
We discuss a general mathematical framework for understanding cryptography over non-prime extension fields for multiplicative groups, elliptic curves, abelian varieties, and other commutative algebraic groups. In this framework, the primitive subgroups of the restriction of scalars can be viewed as twists of a power of the original group variety, or as tensor products of the variety with suitable modules over a commutative ring (see the recent preprint of Mazur, Rubin, and Silverberg). We express the characteristic polynomial of Frobenius acting on a primitive subgroup in terms of that of the original variety, and discuss possible implications for the problem of finding pairing-friendly abelian varieties.
Speaker
Nigel Smart

Title
ID-based key agreement

Abstract
I will discuss ID based key agreement protocols based on pairings. The discussion will focus on which protocols can be implemented in which situations, and what security gaurantees one has. It turns out that the choice of pairing parameters has a great influence on what can be achieved.
Speaker
Nicolas Thériault

Title
Towards an exact cost analysis of index-calculus algorithms

Abstract
When we talk about the security of elliptic curves, We often state that the best known generic attack takes $O(\sqrt{group order})$ group operations. What we really mean is that Pollard Rho has an expected running time of $\sqrt{\pi/2} \times \sqrt{group order}$ group operations (replacing $\sqrt{\pi/2}$ with $(\sqrt{\pi})/2$ if we take advantage of the involution). Even if we use the O-notation, we know the exact value of the constant multiple hidden in the O( ).

When it comes to the security of hyperelliptic curves and the various index calculus algorithms, we again have the O-notation, but this time it is much less clear what the constant multiple actually is. Could it be 1000, 7.23, or .002 ? Although the asymptotic form of the attack does not depend on the constant, the security impact is quite different. Can we really have a fair comparison between curves of different genus (or even between the different versions of index calculus) if we don't know the constant multiple hidden in the O( )?

In this talk, we will narrow in on the constant and show that we can obtain a fair comparison between elliptic and hyperelliptic curves of small genus.