Invited speakers

• Daniel J Bernstein: NIST P-256 has a cube-root ECDL algorithm

  Don't panic. Finding the algorithm is a vastly larger computation than running the algorithm. This distinction is critical for applied cryptography but absent from the standard security definitions in the literature. I will present algorithms illustrating this gap, and will discuss strategies for fixing the definitions. This is joint work with Tanja Lange. http://eprint.iacr.org/2012/458.

• Billy Bob Brumley: Software-based side-channel attacks

  Remote timing attacks. Data cache-timing attacks. Instruction cache-timing attacks. Bug attacks. These side-channel methods all pose a threat to cryptographic software. Case in point: A vulnerability of each aforementioned type affected OpenSSL over the past three years. This talk examines the results and techniques developed to mount these attacks.

• Craig Costello: Efficient pairing computation at the 192-bit and 256-bit security levels

  This talk will give an overview of efficient methods of pairing computation at high-security levels. From the most popular families of pairing-friendly curves that best target these levels, we will discuss how to find and use the curves that are particularly implementation-friendly. This contains joint work with Kristin Lauter and Michael Naehrig.

• Jérémie Detrey: Implementation of pairings over supersingular curves

  After being the center of attention in pairing-based cryptography for quite some time in the 2000s, supersingular curves have now stepped down in favor of families of ordinary curves, such as the BN or BLS ones, much better suited to the currently recommended levels of security.

  However, supersingular curves still retain some unique advantages over ordinary ones. First, from a cryptographic point of view, they allow for Type-1 (i.e., symmetric) pairings, which are still required by some protocols. Second, from an implementation point of view, they have some nice arithmetic properties which can be exploited to speed up the pairing computation, especially in the case of curves defined over binary or ternary fields, for which low-area yet efficient arithmetic coprocessors can be designed.

  Consequently, implementing pairings over supersingular curves is still relevant, but it requires a particularly careful balancing act between security and performance in order to keep them on par with ordinary curves. After a brief remainder on pairings and the basic algorithms to compute them, this talk will thus focus on some recent implementation techniques proposed to address this issue, such as base fields of composite extention degree, or pairings over genus-2 supersingular curves.

• Agustín Domínguez-Oviedo: On Fault-based Attacks and Countermeasures for Elliptic Curve Cryptosystems

  For some applications, elliptic curve cryptography (ECC) is an attractive choice because it achieves the same level of security with a much smaller key size in comparison with other schemes such as those that are based on integer factorization or discrete logarithm. Unfortunately, cryptosystems including those based on elliptic curves have been subject to attacks. For example, fault-based attacks have been shown to be a real threat in today's cryptographic implementations. In this talk, we consider fault-based attacks and countermeasures for ECC. We will show a fault-based attack against the Montgomery ladder elliptic curve scalar multiplication (ECSM) algorithm. For security reasons, especially to provide resistance against fault-based attacks, it is very important to verify the correctness of computations in ECC applications. We deal with protections to fault attacks against ECSM at two levels: module and algorithm. For protections at the module level, where the underlying scalar multiplication algorithm is not changed, a number of schemes and hardware structures are presented based on re-computation or parallel computation. For protections at the algorithm level, we use the concepts of point verification (PV) and coherency check (CC).

• Junfeng Fan: Faster pairing hardware accelerators

  When using pairing-based cryptographic protocols, efficient implementations are required on various platforms. For instance, a web server that supports hundreds of thousands of connections per second needs high-throughput pairing coprocessors. On the hand, mobile devices such as smart phones or RFID tags can only deploy low-area implementations. In this talk, we will discuss how to design high performance pairing processors on modern FPGA. We will focus on optimal pairings defined over BN curves. We show how to efficiently parallelize modular operations using Residue Number System (RNS). In this talk, we will also discuss how to reduce the area of a pairing processor such that it fits constrained devices.

• Steven Galbraith: Applications of random walks to ECC

  The Pollard rho algorithm is the best method for solving the elliptic curve discrete logarithm problem, and it has been used in all ECDLP record computations. One of the most important features of the algorithm is that it allows problems to be distributed over a large network of computers. The algorithm exploits pseudorandom walks and there is a large (and continually growing) literature on its analysis in both theoretical and practical situations. I will briefly mention some of this recent work.

  There are also some less well-known algorithms that use pseudorandom walks and that have applications in ECC. The Pollard kangaroo method is appropriate for the discrete logarithm problem in an interval: Given g, h and N such that h = g^a with 0 <= a < N < order(g), to compute a. There is also an algorithm due to Gaudry and Schost that is appropriate for some related variants of the discrete logarithm problem. I will present recent work of Pollard, Ruprai and myself on these algorithms.

  Finally, pseudorandom walks can be used in algorithms to find an isogeny between two elliptic curves. In the supersingular case, such algorithms are relevant to finding collisions in the Charles-Goren-Lauter hashfunction. I will briefly mention some work of Stolbunov and myself on this problem in the ordinary case, and also some work of Zhao and myself on this problem in the supersingular case.

• David Gruenewald: Computing isogeny graphs in genus 2 using CM lattices

  The structure of isogeny graphs of elliptic curves is well understood and can be used to compute endomorphism rings in genus 1. A natural question to ask is: to what extent can isogeny graphs in genus 2 assist with endomorphism ring computations of Jacobians of hyperelliptic curves? Motivated by this question, in this talk we describe a method to compute isogenies between polarized CM lattices. Using this we can compute the graph structure of (l,l)-isogeny graphs of genus 2 Jacobians over finite fields. We stress the words graph structure here, for we cannot determine absolute invariants of these objects in characteristic p (in characteristic 0 we can find complex value approximations). One positive aspect of this approach though is that computing endomorphism rings requires very little effort. We shall present some genus 2 isogeny graph examples which illustrate the difference in structure and complexity compared with the tamer isogeny volcanoes found in genus 1. Generalizations of the method will also be discussed.

• Takuya Hayashi: Breaking pairing-based cryptosystems using η_T pairing over GF(3⁹⁷)

  In this talk, we report our experimental results of breaking pairing-based cryptosystems using η_T pairing over GF(3⁹⁷). To break the cryptosystems, we solved discrete logarithm problems in GF(3^6•97), whose cardinality is 923 bits, using the function field sieve. The computation required about 148.2 days on 252 CPU cores. This is a joint work with Naoyuki Shinohara, Takeshi Shimoyama, and Tsuyoshi Takagi.

• Sorina Ionica: Endomorphism rings of genus 2 jacobians

  Algorithms for computing the endomorphism ring of a small dimension abelian variety rely on the exploration of the isogeny graph. Using Galois cohomology, we relate the endomorphismring structure to certain properties of the ell-Tate pairing, such as non-degeneracy on subgroups of the ell-torsion giving kernels of isogenies of principally polarized abelian varieties in the ell-isogeny graph. In genus 2, we derive an efficient method to check whether the jacobian has locally maximal endomorphism ring at ell. We also present an algorithm to compute horizontal ell-isogenies starting from a jacobian with maximal endomorphism ring.

• Neal Koblitz: Non-uniformity

  First I will recount the story of a recent dispute over non-uniform arguments in security proofs. Then I will describe how this controversy relates to some results, claims, and open questions connected to elliptic curve factorization and to the ECDLP.

• Christophe Petit: On the complexity of index calculus algorithms for ECDLP over composite fields

  The elliptic curve discrete logarithm problem (ECDLP) is commonly believed to be much harder than its finite field counterpart, resulting in smaller cryptography key sizes. In this talk, we review recent results suggesting that ECDLP is not as hard as previously expected in the case of composite fields.

  We first recall how Semaev's summation polynomials can be used to build index calculus algorithms for elliptic curves over composite fields. These ideas due to Pierrick Gaudry and Claus Diem reduce ECDLP over composite fields to the resolution of polynomial systems of equations over the base field.

  We then argue that the particular structure of these systems makes them much easier to solve than generic systems of equations. In fact, the systems involved here can be seen as natural extensions of the well-known HFE systems, and many theoretical arguments and experimental results from HFE literature can be generalized to these systems as well.

  Finally, we consider the application of this heuristic analysis to a particular ECDLP index calculus algorithm due to Claus Diem. As a main consequence, we provide evidence that ECDLP can be solved in heuristic subexponential time over composite fields. We conclude the talk with concrete complexity estimates for binary curves.

  The talk is based on joint work with Jean-Charles Faugère, Ludovic Perret, Jean-Jacques Quisquater and Guénaël Renault.

• Yumi Sakemi: Project Report on Solving Discrete Logarithm Problems with Auxiliary Input

  At the beginning of 2000's, bilinear map pairings were introduced to establish efficient cryptographic schemes with new functions, whose security rely on the infeasibility of newly proposed mathematical problems such as BDHP, and l-BDHEP. In 2006, as a generalization of these problems, Prof. Cheon defined a discrete logarithm problem with auxiliary input (DLPwAI). This is a problem to find x from G, xG, x^d G in an additive cyclic group generated by an element G of prime order r, and a positive integer d satisfying d|(r -1). Prof. Cheon also proposed a novel algorithm for solving DLPwAI (Cheon's algorithm). For estimating the impact on cryptographic schemes by Cheon's algorithm, we have started to solve some DLPs with AI with small parameters, and now, solving the problem on a pairing-friendly elliptic curve of up to 160-bit order have been succeeded. This talk shows our experimental results of Cheon's algorithm especially for a 160-bit elliptic curve case. Implications of our experiments on cryptographic schemes are also shown.

• Peter Schwabe: Constructive and destructive implementations of elliptic curve arithmetic

  The most common question to ask about the speed of elliptic-curve software is How fast can we do variable-base-point single-scalar multiplication?. In this talk I will show that for most cryptographic and cryptanalytic computations this is the wrong question to ask. For cryptographic software involving computations on secret data we need constant-time behaviour to prevent timing attacks. This additional requirement demands for changes on all algorithmic levels, from high-level scalar multiplication to low-level assembly optimizations. Cryptanalytic computations do not come with this requirement but they are typically highly parallel and can much more easily make use of parallel computing hardware than cryptographic applications. In my talk I will consider examples of elliptic-curve Diffie-Hellman key exchange, elliptic-curve signature generation and verification, and Pollard's rho algorithm. For each of these examples I will describe the requirements on fast and secure software and the state-of-the art algorithms and optimization techniques to meet these requirements.

• Alice Silverberg: Deterministic elliptic curve primality proving for special sequences

  In joint work with Alexander Abatzoglou, Andrew Sutherland, and Angela Wong, we obtain necessary and sufficient conditions for primality of integers in certain sequences, and we give a fast deterministic primality proving algorithm for such integers, using elliptic curves with complex multiplication. We use this algorithm to efficiently search for very large primes. We prove the primality of several integers with more than 100,000 decimal digits, the largest of which has more than a million bits in its binary representation, and obtain the largest proven prime N for which no significant partial factorization of N-1 or N+1 is known. Our work fits in a framework laid out by D. V. Chudnovsky and G. V. Chudnovsky in a 1986 paper, and extends techniques recently employed by B. Gross and by R. Denomme and G. Savin.

• Andrew Sutherland: On the evaluation of modular polynomials

  Isogenies play a key role in many computations related to elliptic curves. A standard method for computing isogenies relies on the modular polynomial Φ_N(X,Y): given an elliptic curve E and a prime N, the j-invariants of the elliptic curves that are N-isogenous to E are precisely the roots of the univariate polynomial φ_N(Y) = Φ_N(j(E),Y), where j(E) is the j-invariant of E. But as N grows, computing φ_N(Y) by evaluating Φ_N(X,Y) at X=j(E) becomes impractical due to the large size of Φ_N.

  I will present a new method to compute φ_N(Y) that does not assume that Φ_N(X,Y) is known, and has a space complexity that is approximately proportional to the size of φ_N, which is smaller than Φ_N by a factor of N. This reduction in space complexity has enabled several record-setting computations, and has practical applications relevant to elliptic curve cryptography.