Class polynomials for abelian surfaces (joint work with Emmanuel Thomé)

The complex multiplication method is well-known for elliptic curves, where it may be used to construct curves used in primality proofs or to implement crytosystems, in particular pairing-based ones. A similar approach is possible for abelian surfaces, that are Jacobians of genus 2 curves, with considerable number theoretic complications. I describe an algorithm using complex floating point approximations with an asymptotically optimal running time, that is, quasi-linear in the size of the class polynomials produced as output. Our implementation has been used to carry out parallelised record computations and I present experimental data.

The arithmetic of elliptic curves, namely operations of addition and scalar multiplication, can be described in terms of finite dimensional space of global sections of line bundles on $E \times E$ and $E$, respectively, determined by a given projective embedding. This reduces the algorithmic study of their evaluation to operations on finite dimensional vector spaces. We show how to determine and classify efficiently computable polynomial maps (addition laws) defining the
addition morphism as a rational map and globally defining a morphism of scalar multiplication.

A logarithm of length k is a bijection f from {1,2,…,k} to Z/kZ satisfying the condition f(ab) = f(a) + f(b) whenever a, b, and ab all lie in the set {1,2,…,k}. Logarithms can be used to construct lattice tilings of n-dimensional space by semi-crosses. They also arise in group theory, number theory, and coding theory. A logarithm of length k exists whenever either k+1 or 2k+1 is a prime, coming from a discrete logarithm map in the multiplicative group of a finite prime field. But other logarithms exist too, and this talk will provide an update on what little is known about these ‘extra’ logarithms.

I will explain a new approach to MPC based on Fully Homomorphic Encryption, which is practical and enables various different possible applications. The talk will assume no prior knowledge of either MPC, FHE or even cryptography. But I will explain the main workings behind the new protocol and demonstrate the resulting system in a practical scenario.

This talk will present the current state of the art of lattice-based digital signatures. I will discuss the currently most-practical construction of such a scheme and discuss the mathematical issues involved in its optimization. I will also give some intuition on how one should select the parameters in an "optimal" way so as to be secure against the currently-best attacks.

This talk is partly based on the paper "Lattice Signatures and Bimodal Gaussians" which is joint work with Leo Ducas, Alain Durmus, and Tancrede Lepoint that will be appearing at Crypto 2013.