Invited speakers

• Diego Aranha: Software implementation of pairings (slides)

  Pairings have been receiving significant research interest as a building block for cryptographers, but their efficiency can be critical for the real-world deployment of their powerful applications. In this talk, we describe several recent developments for accelerating serial and parallel implementations of cryptographic pairings in the asymmetric setting: lazy reduction in extension fields, faster compressed squaring in cyclotomic subgroups, notes on curve selection at higher security levels and how to split a pairing computation among multiple processor cores. We also summarize the current situation with symmetric pairings. This is joint work with K. Karabina, P. Longa, C. Gebotys, J. López, D. Hankerson, A. Menezes, E. Knapp, F. Rodríguez-Henríquez, L. Fuentes-Castañeda, J.-L. Beuchat, J. Detrey and N. Estibals.

• Gaetan Bisson: Computing endomorphism rings of abelian varieties (slides)

  Endomorphism rings of abelian varieties play a crucial role in the complex multiplication method for constructing varieties with a prescribed number of points. This talk will be concerned with the inverse problem: that of computing the endomorphism ring structure of a given abelian variety.
  We will explain how to solve this problem in subexponential time, by exploiting the relationship between isogenies of a given variety and the ideal class group of its endomorphism ring. For elliptic curves, this is very efficient (joint work with Andrew V. Sutherland) and the complexity of this method can be bounded assuming solely the GRH. For higher-dimensional varieties, it requires additional heuristics and is significantly slower, but is nevertheless able to perform record endomorphism ring computations.

• Jean-Marc Couveignes: The geometry of flex tangents to a cubic curve and its parameterizations (slides)

  We show how the study of the geometry of the nine flex tangents to a plane projective cubic produces pseudo-parameterizations, including the ones given by Icart, Kammerer, Lercier, Renault and Farashahi, and infinitely many new ones. Ultimately, pseudo-parameterizations correspond to rational curves on a K3 surface associated with the cubic. A natural object to study then is the Néron-Severi lattice of this surface, and especially the classes of self-intersection $-2$.

• Claus Diem: On the discrete logarithm problem in elliptic curves (slides)

  At ECC 2004 in Bochum Pierrick Gaudry presented an algorithm for the solution of the discrete logarithm problem in elliptic curves over finite fields with a fixed extension degree. In his talk he mentioned a then recent heuristic claim of mine: There are sequences of (non-prime) finite fields over which the elliptic curve discrete logarithm problem can be solved in subexponential expected time. The next day, I gave an ad-hoc presentation of the algorithm and a brief heuristic analysis. The presentation started with two disclaimers: First, the claims are not proven and second, the algorithm is not practical.
  After seven years, I have now completed the proofs of the claims presented in 2004 (up to constants in the exponents). In the talk, I will give an overview over the algorithm and its analysis.

• Jean-Charles Faugère: Solving efficiently structured polynomial systems and Applications in Cryptology (slides)

  Solving polynomial equations is a fundamental problem; an important subproblem is to solve polynomial systems having some additional structures: symmetries (for instance when the associated algebraic variety is invariant under the action of some finite group) or multihomogeneous algebraic systems (each equation is homogeneous wrt a block of variables). One of the most efficient method to solve polynomial systems in finite fields is to compute Gröbner bases. Little is known about the theoretical and practical complexity of computing Gröbner bases of structured systems; in this talk we review several recent advances in this area.
  Surprisingly such structured systems occur frequently in Algebraic Cryptanalysis: for instance the MinRank problem which is at the heart of the security of many multivariate public key cryptosystems such as HFE or the McEliece cryptosystem whose security is based on the hardness of decoding general linear codes are strongly related to multihomogeneous polynomial systems.
  To illustrate this talk, I will consider the algorithm introduced by Gaudry during ECC 2004 to solve the DLP for elliptic curves defined over a non prime finite field F_q^n whose main step is related to polynomial system solving.
  More specifically, I will apply this algorithm to the case of Edwards curves, the well known family of elliptic curves that allow faster arithmetic as shown by Bernstein and Lange. We show how to take advantage of some symmetries of twisted Edwards curves to gain an exponential factor 2^{3(n-1)} when solving the underling polynomial systems. As a result, the Boolean complexity of solving the ECDLP for twisted Edwards curves defined over F_q^5 , with q \approx 2^{64} , is supposed to be 2^{177} operations using generic algorithms compared to a complexity of 2^{127} operations using Gröbner bases and symmetries.

• Craig Gentry: Toward Making Homomorphic Encryption Efficient

  Homomorphic encryption allows allow you to delegate the processing of your data or your query to a "worker" (e.g., the "cloud") without sacrificing your privacy. The worker can process your private data or private query even though it is encrypted, and send back to you the (encrypted) response that you were seeking, without learning anything significant.
  This talk will partly be a tutorial designed to give a taste of how homomorphic encryption schemes work, and why they have been so inefficient. Next, the talk will sketch some very recent results that dramatically improve efficiency and give us hope that homomorphic computation may one day be truly practical.

• David Jao: Isogenies in a quantum world (slides)

  We investigate the quantum computational complexity of finding isogenies between isogenous elliptic curves. In the case of ordinary elliptic curves, we present the first subexponential-time quantum algorithm for constructing an isogeny between two given isogenous curves of equal endomorphism ring. For supersingular elliptic curves, no subexponential time algorithm for constructing isogenies is known, even on quantum computers. Motivated by this observation, we propose the first public-key cryptosystem based on the conjectured difficulty of constructing isogenies over supersingular elliptic curves. We analyze the difficulty of the underlying (conjecturally) hard problem under classical and quantum computation, and give the fastest known algorithms in each setting. In addition, we present implementation results showing that our supersingular curve protocols are multiple orders of magnitude faster than previous isogeny-based public-key cryptosystems over ordinary curves. Joint work with A. Childs, L. de Feo, and V. Soukharev

• Reynald Lercier: Elliptic periods and applications. (slides)

  Kummer $R$-algebras, $R[x]/(x^d-\alpha)$, have shown to be useful in numerous algorithmic applications. We consider an alternative which turned out to be fertile: substitute one elliptic curve $E$ defined on $R$, having a section $T \in E(R)$ of exact order $d$. In this direction, we obtained results concerning the construction of normal bases for finite fields, the calculation of discrete logarithms in finite fields, the primality of integers, or the irreducibility of polynomials (joint work with J.-M. Couveignes, C. Dunand and T. Ezome).

• Allison Lewko: Instantiating the Dual System Encryption Methodology in Bilinear Groups (slides)

  In this talk, we will discuss the dual system encryption methodology introduced by Waters and some of its applications in pairing-based cryptography. We will focus on describing how the methodology is implemented in bilinear groups and surveying the resulting progress in functional encryption. This is joint work with Brent Waters.

• Patrick Longa: Elliptic Curve Cryptography at High Speeds (slides)

  This talk is about efficient elliptic curve computation in software. I will describe a thorough bottom-up optimization process (field, point and scalar arithmetic) to speed up the computation of elliptic curve point multiplication, especially targeting 64-bit platforms. This includes our implementations of the recently proposed Galbraith-Lin-Scott (GLS) curves over GF(p^2) exploiting endomorphisms through the 2-dimensional Gallant-Lambert-Vanstone (GLV) method, which led us to set a speed record in 2010. Moreover, I will discuss how to get a 4-dimensional GLV decomposition to enable the reduction to only a quarter of the number of doublings required for point multiplication on GLS curves with j-invariant 0. The corresponding implementation is presented as the new speed leader. This talk samples work with Zhi Hu and Maozhi Xu (Peking University), and Catherine Gebotys (University of Waterloo).

• Christiane Peters: Code-based cryptography (slides)

  Code-based cryptography easily beats RSA in terms of encryption and decryption speed. Code-based cryptography is even asymptotically faster than ECC. However, users are reluctant to use linear codes in public-key crypto because of bigger key sizes.
  This talk proposes alternative designs for code-based encryption schemes and discusses trade-offs between key size and security against generic and structural attacks. This talk also discusses the first exponential speedup in generic decoding since Stern's 1989 collision-decoding algorithm. This is joint work with Daniel J. Bernstein and Tanja Lange.

• Benjamin Smith: Point Counting on Genus 2 Curves with Real Multiplication (slides)

  We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Using our new algorithm, we can compute the zeta function of an explicit RM genus 2 curve over F_q in O~(log^5 q) bit operations (vs O~(log^8 q) bit operations for the classical algorithm). This, together with a number of other practical improvements, yields a dramatic speedup for cryptographic-sized Jacobians over prime fields, as well as some record-breaking calculations. (Joint work with D. Kohel and P. Gaudry.)

• Marco Streng: Smaller class invariants for constructing curves of genus 2 (slides)

  Elliptic curves with a given number of points can be constructed using the theory of complex multiplication. The idea is to construct a curve over a finite field by taking a special curve E in characteristic 0, and reducing it modulo a prime.
  Instead of writing down equations for such a characteristic-0 curve E, one actually only needs the minimal polynomial of its j-invariant, called a Hilbert class polynomial. The coefficients of these polynomials tend to be very large, so in practice, one replaces the j-invariant by alternative class invariants. Such smaller class invariants can be found and studied using an explicit version of Shimura's reciprocity law.
  Various constructions of curves of higher genus exist, but the coefficient sizes of class polynomials are even worse than those for elliptic curves. I will show how to find smaller class invariants using a higher-dimensional version of Shimura's reciprocity law.

• Ingrid Verbauwhede: The cost of cryptography in hardware (slides)

  In this presentation, the focus will be on the implementation aspects of cryptographic and security applications for embedded devices. Over the years, mathematically strong cryptographic algorithms and protocols have been created. The weak link has become the incorporation of these algorithms in small, embedded, power constrained devices. It requires both an efficient and a secure implementation. Implementations of cryptographic algorithms need to be efficient as they need to operate withing area or memory budget or energy and power budget. On top the implementations need to be physically secure. Most important are the so-called passive attacks, where devices are being monitored, i.e. eavesdrops, while performing normal operation. Countermeasures for these so-called side-channel attacks have an implementation cost that needs to be balanced with the overall design cost. These design methods will be illustrated with examples of secure secret key and public key implementations.

• Vanessa Vitse: Cover and Decomposition Attacks (slides)

  We present a new variant of cover and decomposition attacks on the elliptic curve discrete logarithm problem, that combines Weil descent and decomposition-based index calculus into a single discrete logarithm algorithm. This variant applies, at least theoretically, to all composite degree extension fields, and is particularly well-suited for curves defined over sextic extensions. We give real-size examples of discrete logarithm computations on seemingly secure curves over degree 6 extension fields. This is a joint work with A. Joux.

Rump session

There will be a Rump Session on Monday evening, chaired by Benjamin Smith, where participants can give short and entertaining presentations on recent results, work in progress, or make announcements of interest to attendees.

Please contact Benjamin Smith for details about submitting your contributions.