- 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**F**_{2m}and**F**_{3m}. 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(*for a large range of**F**_{qn})*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.