Titles and abstracts:
- Daniel J. Bernstein (University of Illinois at Chicago, USA)
Algorithms for primes
This talk will consist of a series of light mini-talks
inspired by Atkin's papers on
recognizing primes (1982, "On a primality test of Solovay and Strassen";
1995, "Intelligent primality test offer"),
proving primes to be prime (1993, "Elliptic curves and primality proving"),
factoring integers into primes
(1993, "Finding suitable curves for the elliptic curve method of factorization"),
and enumerating primes (2004, "Prime sieves using binary quadratic forms").
- Bryan Birch (Oxford, UK)
A Tribute to Oliver Atkin
As a tribute to Oliver Atkin, I will be surveying his work; I will also be
including some biographical details. As that would be far too much to talk
about, I will be forced to be selective, and will mainly concentrate on work
he did in his earlier years, including a bit about what may have influenced
him to do that work, and what his work led to.
- Wouter Castryck (K.U.Leuven, Belgium)
The probability of primality of the order of a genus 2 curve Jacobian
In 2000, Galbraith and McKee conjectured a formula estimating the
probability of primality of the number of rational points on an
elliptic curve over a finite field. Their heuristic derivation was
based on an analytic class number formula counting bivariate quadratic
forms up to equivalence. We will give alternative heuristics in favor
of the conjecture, based on a random matrix model. This approach seems
better-suited for generalizing the conjecture to curves of higher
genus. We will then elaborate this in genus 2.
This is joint work with Hendrik Hubrechts and Alessandra Rigato.
- Melissa Chase (Microsoft Research, USA)
Pairing-based proof systems and applications to anonymous credentials
Pairing based cryptography has resulted in a number of breakthrough results,
including some major developments in the area of zero knowledge proof systems.
A zero knowledge proof system allows a party to prove that a statement is true
without revealing any other information. Zero knowledge proofs are used in
everything from identification protocols (allowing a party to prove that he is
who he claims to be) and encryption schemes with stronger security properties,
to securing protocols against malicious adversaries, and constructing privacy
preserving systems. It has been shown that zero knowledge proofs can be
constructed from a variety of number theoretic assumptions (or, more generally
from any trapdoor permutation); however most of these constructions are complex
and inefficient. In '06 Groth, Ostrovsky, an Sahai showed how to construct
proof systems based on pairings which have much more structure than traditional
constructions; this structure in turn has since been shown to result in proof
systems with greater efficiency, stronger security, and more functionality.
This talk will describe at a high level how pairings allows us to construct
zero knowledge proofs with more structure than traditional tools, and then
discuss some of the applications that take advantage of this structure,
focusing on applications to privacy and anonymity.
- Andreas Enge (INRIA Bordeaux - Sud-Ouest and IMB, France)
Class polynomials by Chinese remaindering
Polynomials generating ring class fields of imaginary-quadratic number fields
are the main ingredient for obtaining elliptic curves with prescribed complex
multiplication. In recent years, algorithms computing such class polynomials by
Chinese remaindering have been found which are faster (both in theory and
practice) than the classical complex analytic approach. I will give an overview
of the algorithms and concentrate on how the last stumbling block could be
overcome, the use of alternative class invariants that lead to smaller
polynomials.
- Junfeng Fan (K.U.Leuven, Belgium)
ECC on constrained devices
The embedded security community has been looking at the ECC
ever since it was introduced. Hardware designers are now challenged by
limited area (<15k Gates), low power budget (<100uw) and sophisticated
physical attacks. This talk will report the state-of-the-art ECC
implementations for ultra-constrained devices. We take a passive RFID
tag as our potential target. We will discuss the known techniques to
realize ECC on such kind of devices, and what are the challenges we face
now and in the near future.
- Gerhard Frey (Institute for Experimental Mathematics, Germany)
Elliptic Curves: Facts, Conjectures and Applications
Elliptic curves E can be given by plane projective cubic
curves and so seem
to be very simple objects. A first hint for more structure is that there is
an algebraic addition law for the rational points. In fact, there is a natural
isomorphism of E with its Jacobian variety, and so E
is at the same time
a curve of low degree and an abelian variety of smallest possible dimension.
This is the reason for a very rich and deep theory behind making elliptic
curves to ideal objects for both theoretical and experimental investigations,
always with a strong algorithmic aspect. As outcome we find an abundance
of key conjectures of arithmetic geometry inspired (and even proven) by
elliptic curves.
It will be the purpose of the talk to explain some of these conjectures and
results and, as important and rather astonishing side effect, state why these
properties of elliptic curves make them to a most efficient and secure tool for
public key crypto systems based on discrete logarithms.
- Shafi Goldwasser (MIT, USA and Weizmann Institute of Science, Israel)
Past and Present: Primes and Cryptography
The talk will be composed of two parts:
(1) We will present an open problem in primality testing (yes - they still
exist)
and (2) we will describe some current trends in designing public key
encryption schemes (designing
schemes which are circular secure, resistant to leakage about secret keys,
and
secure even when auxiliary input is known about secret keys), with an eye
toward an elliptic
curve based crypto system with these stronger properties.
- Rob Granger (Claude Shannon Institute, Ireland)
On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
Recent work by Koblitz and Menezes has highlighted the
existence, in some cases, of apparent separations between the hardness of
breaking discrete logarithms in a particular group, and the hardness of
solving in that group problems to which the security of certain
cryptosystems are provably related. We consider one such problem in the
context of elliptic curves over extension fields, and report potential
weaknesses of the Galbraith-Lin-Scott curves from EUROCRYPT 2009, as well
as a practical attack on some legacy curves.
- Darrel Hankerson (Auburn University, USA)
Software implementation of pairings at the 128-bit security level
Security and efficiency issues for pairings derived from supersingular
curves are discussed, in particular for genus-2 curves.
Parallelization and new hardware features significantly accelerate
such pairings, and we examine the competitiveness against asymmetric
pairings. For the genus-2 case, we consider implications for certain
protocols when attempting to choose parameters favorable to speed.
This talk samples recent work with D. Aranha, S. Chatterjee,
J. López, and A. Menezes.
- David Harvey (Courant Institute of Mathematical Sciences, USA)
Counting points on projective hypersurfaces
I will discuss recent progress on a new algorithm for computing the Zeta
function of a projective hypersurface over a finite field.
- Huseyin Hisil (Turkey)
Faster formulas for elliptic curves
The talk is about the derivation of the addition law on an
arbitrary elliptic curve and efficiently adding points on this
elliptic curve using the derived addition law. The outcomes of this
work guarantee practical speedups in higher level operations which
depend on point additions. In particular, the contributions
immediately find applications in cryptology.
- Neal Koblitz (University of Washington, Seattle, USA)
My Last 24 Years in Crypto: A Few Good Judgments and Many Bad Ones
After describing some joint work with Menezes
in which isogenies are used to show that
conventional wisdom about parameter selection
might sometimes be wrong, I'll shift gears
and make some comments on how
easy it is to get things badly wrong in
cryptography. I'll illustrate by giving a
brief survey of some of the many misjudgments
I've made over the years.
- David Kohel (Institut de Mathématiques de Luminy, France)
Endomorphisms, isogeny graphs, and moduli
I will present a retrospective of aspects of my thesis, in
light of applications in the last 14 years since its birth.
In particular, I will focus on explicit isogenies, moduli of
elliptic curves and CM structure, the "local" Galois module
structures of l-torsion and l-isogeny graphs, and "global"
structure of action visa class groups and isogenies.
The focus will be directed principally towards ordinary
elliptic curves over finite fields, but I will discuss
briefly the supersingular case and generalizations to
higher dimension.
- Tanja Lange (Technische Universiteit Eindhoven, Netherlands)
Breaking ECC2K-130
ECC2K-130 is the smallest unsolved Certicom discrete-logarithm
challenge. Certicom originally stated that breaking ECC2K-130 was
"infeasible" and would require 2700000000 machine days.
This talk reports on an ongoing joint project by researchers from 12
different universities to break ECC2K-130. The project has increased our
knowledge of the mathematical speedups for attacking elliptic-curve cryptosystems, has led to a new representation for finite fields in
'optimal polynomial bases', and has led to a better understanding of the
randomness of pseudorandom walks used in Pollard's rho method. The
project has produced optimized implementations of a highly tuned
iteration function for different platforms ranging from standard CPUs to
customized FPGA clusters.
These optimizations have moved the ECC2K-130 computation to the range of
feasibility. The computation would finish in only two years using 1595
standard PCs, or 1231 PlayStation 3 game consoles, or 534 GTX 295
graphics cards, or 308 XC3S5000 FPGAs, or any combination of the above.
We are now actively performing the computations.
See our twitter page for
updates.
- Kristin Lauter (Microsoft Research, USA)
Computing genus 2 curves from invariants on the Hilbert moduli space
Joint work with Tonghai Yang (University of Wisconsin USA); he was originally scheduled to present this work.
We give a new method for generating genus 2 curves over a
finite field with a given number of points on the Jacobian of the
curve. We define two new invariants for genus 2 curves as values of
modular functions on the Hilbert moduli space and show how to compute
them. We relate them to the usual three Igusa invariants on the Siegel
moduli space and give an algorithm to construct curves using these new
invariants. Our approach simplifies the complex analytic method for
computing genus 2 curves for cryptography and reduces the amount of
computation required.
- Winnie Li (Penn State, USA and National Center for Theoretical Sciences, Taiwan)
Atkin-Swinnerton-Dyer congruences on noncongruence modular forms
The understanding for the arithmetic of modular forms for
noncongruence
subgroups pales when compared to that for congruence subgroups. In
large part,
this is due to the lack of effective Hecke operators. The first
pioneering work on
noncongruence modular forms was done by Atkin and Swinnerton-Dyer in
1971. Based
on a handful numerical data they gathered, Atkin and Swinnerton-Dyer
proposed p-adic
congruence relations, similar to the recursive relation satisfied by
Hecke eigenforms,
to be satisfied by a basis of a given space of noncongruence cusp
forms. In this talk
we shall survey subsequent developments and the current status of the
ASD congruences.
- Victor Miller (Institute for Defense Analyses, USA)
Elliptic Curves, Cryptography and Computation
Much of the research in number theory, like mathematics as a whole, has been inspired by hard problems which are easy to state. A famous
example is "Fermat's Last Theorem". Starting in the 1970's number theoretic
problems have been suggested as the basis for cryptosystems, such as RSA and
Diffie-Hellman. In 1985 Koblitz and Miller independently suggested that the
discrete logarithm problem on elliptic curves might be more secure than the
"conventional" discrete logarithm on multiplicative groups of finite
fields. Since then it has inspired a great deal of research in number theory and geometry in an attempt to understand its security.
I'll give a brief historical tour concerning the elliptic curve discrete logarithm problem, and the closely connected Weil Pairing algorithm.
- Peter Montgomery (Microsoft Research, USA)
ECM -- Then and Now
This presentation has two parts. The first half
discusses the major factorization algorithms when ECM was discovered
in 1985, stressing the similarities between ECM and P +- 1.
The second half describes the recent discoveries of six large Mersenne factors
using ECM on a network of PlayStations.
This is joint work with Joppe W. Bos, Thorsten Kleinjung, and Arjen K. Lenstra from EPFL.
- Francois Morain (LIX École Polytechnique, France)
Elliptic curves with complex multiplication: history and perspectives
The theory of complex multiplication on curves is very old and
rich, going back at least to Gauss. Since then, many authors have
been developing the theory, in parallel with quite a heavy load of
computations and formulas (by hand!). Soon after Schoof's 1985 major
article, reduction of curves with complex multiplication over finite
fields were used to prove the primality of special or general numbers,
and the corresponding algorithms are still in use today. As a result,
this led to the emergence of the so-called CM-method to build curves
with prescribed properties. The talk will present some parts of this
history, concentrating on explicit computations and applications of
the CM theory to some old and new problems.
- Michael Naehrig (Microsoft Research, USA)
Pairings on elliptic curves - parameter selection and efficient computation
This talk is about efficient pairing computation on elliptic curves.
I will discuss particularly implementation-friendly curves, the use of
the polynomial parameter representation to compute pairings on BN
curves, and reasons to use affine coordinates for pairings at high
security levels.
This contains joint work with P. Barreto, G. Pereira, M. Simplício Jr,
P. Schwabe, R. Niederhagen, K. Lauter, and P. Montgomery.
- Damien Robert (INRIA Bordeaux - Sud-Ouest, France)
Generalizing Vélu's formulas and some applications
Vélu's formulas allow to compute an isogeny between elliptic curves from
the coordinates of the points in the kernel. In this talk, I describe an
algorithm using theta functions to compute an isogeny from its kernel on
any abelian variety. I will give specific timings of a genus 2
implementation, and describe some applications.
This is a joint work with Romain Cosset and David Lubicz.
- Francisco Rodriguez-Henriquez (Centro de investigación y de Estudios Avanzados del I.P.N., Mexico)
Faster Implementation of Pairings
This talk gives an overview of the design of a fast hardware accelerator
and a software library for the computation of symmetric and asymmetric
cryptographic pairings. The first half of this talk is devoted to describe
the architecture of two hardware accelerators that compute the
ηT
pairing over F2m and
F3m. This accelerator
implements Miller's algorithm using a parallel pipelined Karatsuba
multiplier, and takes advantage of a dedicated coprocessor responsible for
computing the final exponentiation.
The second half discusses the design of fast software libraries for the
computation of both symmetric and asymmetric pairings. First, a brief
description of the design of a fast multi-core library for the
cryptographic Tate pairing over supersingular elliptic curves is given.
Then, the efficient computation of the optimal ate pairing on a
Barreto-Naehrig elliptic curve is explained in detail.
- Karl Rubin (University of California at Irvine, USA)
Selmer ranks of elliptic curves in families of quadratic twists
This talk will report on ongoing work with Barry Mazur that studies 2-Selmer
ranks in the family of all quadratic twists of a fixed elliptic curve over
a number field. Our goal is to compute the density of twists with a given
2-Selmer rank r, for every r. This has been done by
Heath-Brown, Swinnerton-Dyer, and Kane for elliptic curves over Q
with all 2-torsion rational. Our methods are different and work best for
curves with no rational points of order 2. So far we can prove under
certain hypotheses that E has "many" twists of every 2-Selmer
rank, but not that the set of such twists has positive density. In
this talk I will describe these results and the methods involved, and
discuss a basic question about algebraic number fields that arises in
trying to improve our results.
- Rene Schoof (Universita di Roma "Tor Vergata", Italy)
Counting points on elliptic curves over finite fields and beyond
- Alice Silverberg
(University of California at Irvine, USA)
On elliptic curves with an isogeny of degree 7
This talk is about joint work with Ralph Greenberg and Karl Rubin. Given a group
C of order 7 with a Galois action (in characteristic not 7), we construct the
family of all elliptic curves with a rational subgroup Galois-isomorphic to C.
As an application, we show that the images of 7-adic representations of
elliptic curves over Q with a rational subgroup of order 7 are as large as they
can be, with at most one exception (counted suitably). Whether the exception
occurs depends on whether a certain genus 12 curve with 6 "obvious" rational
points has any additional rational solutions. We use work of Poonen and
Schaefer along with Stoll's version of the method of Chabauty to show that the
curve has either 6 or 12 rational points.
- William Stein (University of Washington, Seattle, USA)
Elliptic Curves in Sage
Sage (http://sagemath.org) is the most feature rich general
purpose free open source software for computing with elliptic curves.
In this talk, I'll describe what Sage can compute about elliptic
curves and how it does some of these computation, then discuss what
Sage currently can't compute but should be able to (e.g., because
Magma can).
- Bianca Viray (Brown
University, USA)
Igusa class polynomials, embeddings of quartic CM fields, and arithmetic
intersection theory
Currently, one of the best ways of computing genus 2 curves that can be
used in cryptographic systems is via computation of Igusa class
polynomials. Unfortunately Igusa class polynomials (the genus 2
analogue of Hilbert class polynomials) can be difficult to compute,
mostly because recovering the coefficients from approximations requires
a bound on the denominators. We will sketch how the denominators can be
related both to the number of embeddings of quartic CM fields into
certain endomorphism rings and to a conjectural formula of Bruinier and
Yang for certain intersection numbers. We will present computations of
these three values for 13 different CM fields and, in the cases in which
the values are not what we might expect, we point to explanations for
the differences.
- Vanessa Vitse (Université de Versailles Saint-Quentin-en-Yvelines, France)
F4 traces and index calculus on elliptic curves over extension fields
Recently, Gaudry and Diem have proposed an index calculus
method for the resolution of the DLP on elliptic curves defined over
extension fields. In this talk, I will first present a variant of this
method that enables to decrease the asymptotic complexity of the DLP on E(Fqn)
for a large range of q and n, then introduce a second
improvement provided by the use of F4 traces for polynomial system
solving. Finally, I will give a practical example of our index
calculus variant to the oracle-assisted Static Diffie-Hellman Problem.
This is a joint work with Antoine Joux.
- Melanie Matchett Wood (American Institute of Mathematics, USA)
Composition Laws
The group laws on elliptic curves, Jacobians of
hyperelliptic curves, and ideal class groups of quadratic number
fields are all examples of group laws that can be computed explicitly
via composition on various types of binary quadratic forms. We will
discuss how these examples fit into a larger picture of class groups
of quadratic extensions of any base space or ring, which can all be
given explicitly by composition on generalized binary quadratic forms.
Further, we will discuss how this is the degree 2 piece of a larger
story, in which class groups of all cubic extensions and even some
degree n extensions (for n>3) can be given in terms of composition
laws on trilinear forms. For example, one can compute Jacobians of
trigonal curves via composition on certain trilinear forms.