October 18, 2010 – October 22, 2010

ECC 2010

  • Daniel J. Bernstein (opens in new tab) (University of Illinois at Chicago, USA)
    Algorithms for primes
    (opens in new tab)    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 (opens in new tab) (Oxford, UK)
    A Tribute to Oliver Atkin
    (opens in new tab)    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 (opens in new tab) (K.U.Leuven, Belgium)
    The probability of primality of the order of a genus 2 curve Jacobian
    (opens in new tab)    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 (opens in new tab) (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 (opens in new tab) (INRIA Bordeaux – Sud-Ouest and IMB, France)
    Class polynomials by Chinese remaindering
    (opens in new tab)    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 (opens in new tab) (K.U.Leuven, Belgium)
    ECC on constrained devices
    (opens in new tab)    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 stateof-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 (opens in new tab) (Institute for Experimental Mathematics, Germany)
    Elliptic Curves: Facts, Conjectures and Applications
    (opens in new tab)    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 (opens in new tab) (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.
  • Huseyin Hisil (opens in new tab) (Turkey)
    Faster formulas for elliptic curves
    (opens in new tab)    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.
  • David Kohel (opens in new tab) (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 (opens in new tab) (Technische Universiteit Eindhoven, Netherlands)
    Breaking ECC2K (opens in new tab)– (opens in new tab)130
    (opens in new tab)    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 (opens in new tab) for updates.
  • Kristin Lauter (opens in new tab) (Microsoft Research, USA)
    Computing genus 2 curves from invariants on the Hilbert moduli space (opens in new tab) Joint work with Tonghai Yang (opens in new tab) (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.
  • Victor Miller (opens in new tab) (Institute for Defense Analyses, USA)
    Elliptic Curves, Cryptography and Computation
    (opens in new tab)    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.
  • Francois Morain (opens in new tab) (LIX École Polytechnique, France)
    Elliptic curves with complex multiplication: history and perspectives
    (opens in new tab)    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.
  • Damien Robert (opens in new tab) (INRIA Bordeaux – Sud-Ouest, France)
    Generalizing Vélu’s formulas and some applications
    (opens in new tab)    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 (opens in new tab)– (opens in new tab)Henriquez (opens in new tab) (Centro de investigación y de Estudios Avanzados del I.P.N., Mexico)
    Faster Implementation of Pairings
    (opens in new tab)    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 multicore 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 (opens in new tab) (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 2torsion 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 (opens in new tab) (Universita di Roma “Tor Vergata”, Italy)
    Counting points on elliptic curves over finite fields and beyond (opens in new tab)
  • Alice Silverberg (opens in new tab) (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 (opens in new tab) (University of Washington, Seattle, USA)
    Elliptic Curves in Sage
    (opens in new tab)    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 (opens in new tab) (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. Joint work with H. Grundman, J. Johnson-Leung, K. Lauter, A. Salerno, E. Wittenborn
  • Vanessa Vitse (opens in new tab) (Université de Versailles Saint-Quentin-en-Yvelines, France)
    F4 traces and index calculus on elliptic curves over extension fields
    (opens in new tab)    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 (opens in new tab) (American Institute of Mathematics, USA)
    Composition Laws
    (opens in new tab)    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.