ECC 2014, Chennai

The 14th Elliptic Curve Cryptography workshop was held last week at the Institute of Mathematical Sciences in Chennai, India. Of the five ECC workshops I’ve attended, this one had by far the best food (sorry, France). But it also had some good talks:

Razvan Barbulescu gave a nice talk on his now-famous quasi-polynomial algorithm for discrete logarithms in small-characteristic finite fields (his Eurocrypt 2014 paper with Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé). Razvan does a very good job of making this stuff accessible, and it’s always nice to hear the word GIPS-year in a talk (try saying it aloud to yourself).

Jens Zumbrägel spoke about computing discrete logarithms in the sorts of fields associated with pairings on supersingular binary curves, at what was formerly supposed to be the 128-bit security level (this was a Crypto 2014 paper with Thorsten Kleinjung and Rob Granger). Their project computed one discrete logarithm, and gives an estimated time for completing another one; this is another substantial nail in the coffin of small characteristic curves and pairings.

Ruben Niederhagen gave a really nice talk about the history (and practical exploitation of) the standardized backdoor in the DualEC random number generator, which was detailed in his USENIX 2014 paper with Stephen Checkaway, Matthew Fredrikson, Matthew Green, Tanja Lange, Thomas Ristenpart, Daniel J. Bernstein, Jake Maskiewicz, and Hovav Shacham.

Guénaël Renault gave a nicely detailed presentation on a technique which exploits torsion points and torsion structures to speed up index calculus on elliptic curves. The details are in a joint paper with Jean-Charles Faugère, Louise Huot, and Pierrick Gaudry.

Huseyin Hisil spoke about a fast implementation of endomorphism-accelerated scalar multiplication designed to implement Diffie-Hellman at the 128-bit security level (this is the subject of a joint paper with Craig Costello and myself, which was presented at Eurocrypt 2014). He also gave some tips for incomplete reduction techniques (in Intel assembly) for arithmetic modulo (pseudo-)Mersenne primes.

Elisa Gorla explained her joint work with Maike Massierer on index calculus in trace-zero subvarieties of elliptic curves defined over subfields. If you have a curve E over \mathbb{F}_p, then for every extension \mathbb{F}_{p^n}/\mathbb{F}_p you have a trace map E(\mathbb{F}_{p^n}) \to E(\mathbb{F}_p), mapping P to the sum of its p-power conjugates, and this map has a kernel T_n. This talk was about solving DLP instances via index calculus in that subgroup. The trace zero variety has been out of fashion in cryptography for some time now, but it’s still fun (for a certain value of fun) and instructive to play with; there is a lot more detail on this in Maike Massierer’s thesis.

Emmanuel Thomé spoke about his Igusa class polynomial computations (with Andreas Enge). Their results, using complex approximations and Borcherds means, essentially complete the approach set out in Regis Dupont’s thesis.

Yuval Yarom spoke about his CHES 2014 paper with Naomi Benger (who’s now a meteorologist!), Joop van der Pol, and Nigel Smart: they got some really nice side channel results using the Flush+Load attack on OpenSSL ECDSA signatures on the bitcoin curve.

Craig Costello spoke about curve parameter standardization in general, covering curve arithmetic and the huge number of choices to be made, and Microsoft’s NUMS curves in particular (which are described in his joint work with Joppe Bos, Patrick Longa , and Michael Naehrig). The NUMS curves are Microsoft’s contribution to the current debate on new, post-BULLRUN curve standards for ECC; you can download their library implementing these curves here.

The disembodied voice of Eric Wustrow presented a nice empirical survey of how ECC is currently deployed on the internet (his body, which had had visa problems, was asleep on another continent). This was a summary of his Financial Crypto 2014 work with Nadia Heninger, Joppe Bos, Alex Halderman, and Jonathan Moore.

Damien Robert reported on his recent joint work with David Lubicz, on computing pairings on abelian varieties. This talk was relatively technical, even by Damien’s standards (at one point he said it was time to move away from the abstract and get on to some concrete stuff: “Let A be a principally polarized abelian variety…”) But if you’re not afraid of duality, then you’ll find some good stuff in their paper that really could be used in concrete, fast implementations.

Erich Wenger spoke about his new record ECDLP computation (with Paul Wolfger, presented at SAC 2014): a 113-bit binary koblitz curve DLP instance. They have actually done it. They used basic parallelized Pollard rho, without negation maps and other frills, on a cluster of borrowed FPGAs (apparently with a lo-fi cooling system consisting of a couple of desk fans). If they had had access to all 18 of the FPGAs all of the time, then the computation would have taken 24 days—but then buying 18 of your own FPGAs to dedicate to the same kind of project amounts to about 45KUSD (the desk fans are much cheaper, I suppose). The actual budget for their project was 20USD worth of chocolate. Erich gave a series of estimations in terms of dollar and day costs, etc., for bigger challenge curves: he thinks think that if they had a billion USD and 190K days, then they could solve ECC2-163. Though I think that if they had a billion USD then they would probably do something else first. Possibly buying a lot more chocolate.

As is traditional at ECC workshops, there were some talks on cryptographic results from outside the domain. This time around, Mridul Nandi gave a survey talk on authenticated encryption, and Palash Sarkar gave a talk on symmetric broadcast encryption techniques.

Next year’s ECC workshop will be held in Bordeaux, France. I think most people expect that they will have by far the best wine for an ECC; let’s hope they can keep up the good talks, too.

–Ben Smith

Posted in Uncategorized | Leave a comment

Day Two of ANTS 2014

The Eleventh Algorithmic Number Theory Symposium took place in rainy GyeongJu, Korea on August 6-11, 2014. The proceedings are available online in the open access LMS Journal of Computation and Mathematics.

The first day contained a number of excellent lectures, but none direct relevant to elliptic curve cryptography. Unfortunately one talk was not given (and another talk was given by a substitute speaker).

Day two of the conference contained all the papers about the discrete logarithm problem.

The morning began with Antoine Joux‘s invited lecture “The discrete logarithm problem in small characteristic finite fields”. The talk began with a general survey of generic DLP algorithms and index calculus methods. He then moved on to discuss the recent work for the DLP in \mathbb{F}_{p^k} for small p and large k. First he explained the general approach, going back to Joux-Lercier (EUROCRYPT 2006) for the “medium-prime case”, of choosing two polynomials f_1(X) and f_2(X) in \mathbb{F}_p[X] of degrees d_1, d_2 respectively, such that f_1( f_2(X)) - X has an irreducible factor of degree k. One then uses a certain diagram of rings to develop an algorithm relying on some heuristics. Antoine explained a case where the heuristics badly fail, and noted that this leads to the greatly improved algorithms in small characteristic.

He then introduced a new and simplified approach to the algorithm, which avoids extending the field (previous approaches took a quadratic or cubic extension for the coefficients of the “homographies”). We explain this approach now.

We are interested in the DLP in \mathbb{F}_{q^k}^*. Let I(X) \in \mathbb{F}_q[X] be an irreducible polynomial of degree k that divides h_1(X^q)X - h_0(X^q), where \deg( h_1(X)), \deg( h_0(X) ) \leq H. Write \mathbb{F}_{q^k} = \mathbb{F}_q[\theta] where \theta is a roots of I(X). The key equation is (1) X^q - X = \prod_{\alpha \in \mathbb{F}_q} (X - \alpha). Choose integer D and set factor base to be polynomials over \mathbb{F}_q in variable \theta of degree \leq D. Let A, B also be polynomials over \mathbb{F}_q in variable \theta of degree \leq D. Substituting A(\theta)/B(\theta) into equation (1) (this is the alternative to using homographies) and doing standard algebra gives B(\theta) \prod_{\alpha \in \mathbb{F}_q} (A(\theta) - \alpha B(\theta) ) = B(\theta) A( h_0(\theta)/h_1(\theta) ) - A(\theta) B(  h_0(\theta)/h_1(\theta) ). The LHS of the equation splits over the factor base. Antoine introduces new notation [ A, B]_D so that the RHS of the equation is [A, B]_D(\theta)/ h_1(\theta)^D. If the numerator of the RHS splits over the factor base then we have a relation. He gives several properties of the polynomial/symbol [ A, B]_D. He then argues that D = 3 is the smallest choice for D for which one can expect to compute enough relations this way. He concludes that the running time of the first stage of the algorithm (to compute the discrete logarithm of everything in the factor base with respect to some single element in the factor base) is O( q^7 ) field operations in \mathbb{F}_q.
The remainder of his talk surveyed four descent strategies and explained how they are all combined to give the full algorithm.

The next talk was “The discrete logarithm problem for exponents of bounded height” presented by Sam Scott (joint work with Simon Blackburn). The paper is about the DLP instance: Given (g,h,n) to find integers 1 \leq a, b < n such that g^a = h^b, when n is much smaller than the order of g. This problem arises when one tries to trace transactions made using a proposed protocol by EMV (Mastercard/Visa) for card payments. (The standard attempts to make such transactions un-traceable in the sense that it is hard for an eavesdropper to "link" two different transactions made using the same card). The algorithmic content is to use the Gaudry-Schost algorithm for this problem, to get a low-storage algorithm that performs O( n ) group operations. The EMV standard proposed n=32, but this has been increased in response to the attack in this paper. Nevertheless, it is interesting that next-generation card payments will be protected by 256-bit elliptic curve cryptography.

Third talk of the session was "Constructing Abelian Surfaces for Cryptography via Rosenhain Invariants" by Kristin Lauter (joint work with Craig Costello, Alyson Deines-Schartz and Tonghai Yang). The paper is about constructing genus 2 curves using the CM method. Almost all previous work has used Igusa invariants and hence Mestre’s algorithm. The paper notes that using Rosenhain invariants is much simpler, and that the penalty that the class polynomials have higher degree is not necessarily a major problem in practice. Kristin also talked about how this method can give Kummer surface equations with relatively small constants, and expressed her philosophy that number theorists should be more engaged in applied subjects like cryptography, not only because the applications are important but also that these subjects can be a rich source of interesting theoretical questions.

Next was “Hyper-and-elliptic-curve cryptography” by Dan Bernstein. Dan, the sweet gentle soul that he is, gave an emotional appeal on behalf of a polar bear named “Fluffy” that we should try to use less energy by using more efficient crypto. This led to a discussion of Kummer surfaces and Edwards curves. The mathematical content was an explanation of a construction due to Scholten of genus 2 curves whose Jacobians are isogenous to the Weil restriction of Edwards curves. Dan explained how one can construct examples where the Kummer surface of the genus 2 Jacobian has an equation with small coefficients, and how one can efficiently pass between Edwards curve and Kummer surface representations of the same group. He was warmly thanked (globally) on behalf of Fluffy.

After lunch, Christophe Petit spoke about “Finding Roots in \mathbb{F}_{p^n} with the Successive Resultants Algorithm”. This is a new approach to factoring polynomials over finite fields of small characteristic. It does not provide a major speed-up for present applications, but is being suggested in the hope that it can lead to a new approach to finding solutions of a special form to multivariate polynomial equations.

Next Qi Cheng spoke on “Traps to the BGJT-Algorithm for Discrete Logarithms” (joint work with Daqing Wan and Jincheng Zhuang). The paper aims to reduce the number of heuristics in the quasi-polynomial-time algorithm for the DLP in finite fields of small characteristic. Note that there are several avenues to approach these isses, for example as discussed in Rob Granger’s talk at the Ascona DLP workshop.

Cecile Pierrot presented “The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields” (joint work with Razvan Barbulescu). This takes ideas of Coppersmith and Matyukhin for the number field sieve and applies them to a more general class of finite fields. These ideas lead to complexity improvements for the DLP in finite fields.

In the evening there was a poster session, followed by a “business meeting” that decided that ANTS 2016 should take place in (Bordeaux or Kaiserslautern) but failed to give a full solution to the problem.

The conference continues, but the talks are mainly on topics unrelated to elliptic curve cryptography. On Monday there will be a talk by David Kohel on the paper “On the quaternion l-isogeny path problem” with Kristin Lauter, Christophe Petit and Jean-Pierre Tignol. This paper is relevant to isogenies on supersingular elliptic curves and the Charles-Goren-Lauter hash function.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

CRYPTO and ANTS accepted papers

The list of accepted papers for ANTS 2014 is online. The conference contains several papers of interest to researchers in ECC:

  • Simon R. Blackburn and Sam Scott “The discrete logarithm problem for exponents of bounded height”. This paper gives a nice result relevant for the EMV Key Establishment Protocol.
  • Qi Cheng, Daqing Wan and Jincheng “Zhuang Traps to the BGJT-Algorithm for Discrete Logarithms”. This paper is about DLP in finite fields of small characteristic.
  • Razvan Barbulescu and Cecile Pierrot “The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields”. This is also about finite field DLP.
  • Daniel J. Bernstein and Tanja Lange “Hyper-and-elliptic-curve cryptography”. This is about efficient cryptosystems that use both elliptic and hyperelliptic curves to represent the same group.
  • There are also three papers about ideals in quaternion algebras and supersingular elliptic curves.

Similarly, the (partial) list of accepted papers to CRYPTO 2014 is up. The program is very large: 55 papers or more. The conference includes:

  • Robert Granger, Thorsten Kleinjung and Jens Zumbragel “Breaking `128-bit Secure’ Supersingular Binary Curves (or how to solve discrete logarithms in GF( 2^{4*1223} ) and GF( 2^{12*367} )”.
  • Masayuki Abe, Jens Groth, Miyako Ohkubo and Mehdi Tibouchi “Structure-Preserving Signatures from Type II Pairings”.
  • Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer and Madars Virza “Scalable Zero Knowledge via Cycles of Elliptic Curves”.
  • Gottfried Herold, Julia Hesse, Dennis Hofheinz, Carla Rafols Salvador and Andy Rupp “Polynomial Spaces: A New Framework for Composite-to-Prime-Order Transformations”.
  • As well, there are interesting papers about Multi-linear maps, Lattices, Indistinguishability Obfuscation, etc.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

DLP workshop Ascona. Second and final part.

I now summarise the remaining three days of the DLP workshop in Ascona.  I will focus on the talks of most relevance to elliptic curve cryptography.

Day 3

Joppe Bos: Elliptic and hyperelliptic curves: a practical security analysis

It is known (Gallant-Lambert-Vanstone, Wiener-Zuccherato) that if G is a finite abelian group with an efficiently computable and small group of automorphisms H, then one can do Pollard rho on the set of orbits of G under H. If H has m elements then one would hope the algorithm is sped-up by a factor \sqrt{m}. However, there are obstructions to achieving this speed-up in practice (such as additional multiplications involved in computing the orbit). The talk discussed these obstructions and gave some theoretical upper-bounds on the speedup for various popular elliptic and genus 2 curves. This allows detailed comparison of security levels of these curves. This joint work with Costello and Miele was published at PKC 2014.

Marco Streng: An unsolved Diffie-Hellman problem over the rationals

Marco gave a wonderful survey talk about Hilbert’s 10th problem. It is now famous that there is no algorithm to decide solubility of Diophantine equations over \mathbb{Z}. But the question over \mathbb{Q} is still open. More precisely, the question of whether \mathbb{Z} is a Diophantine subset of \mathbb{Q} (can \mathbb{Z} be modelled over \mathbb{Q}?) is open. Mazur’s conjecture (finitely many components of topological closure over \mathbb{R} of algebraic varieties over \mathbb{Q}) would imply \mathbb{Z} is not Diophantine. But if there exists an elliptic curve E over \mathbb{Q} with rank 1 and E( \mathbb{Q} ) = \langle P \rangle such that the set \{ (aP, bP, abP ) : a, b \in \mathbb{Z} \} is Diophantine, then it is a model for \mathbb{Z}. This is the “Diffie-Hellman problem” of the title. If such a curve exists then it would follow that there is no algorithm to decide Diophantine equations over \mathbb{Q}.

Gaetan Bisson: On polarized class groups of orders in quartic CM fields

Gaetan won the prize for the most institutional logos on his slides.

The rain stopped and the sun came out just in time for our boat trip to the Brissago Islands, a tour of the gardens, and dinner.

Day 4

Cecile Pierrot: Discrete logarithms in medium and large characteristic finite fields

The idea of the multiple number field sieve (MNFS) goes back to Coppersmith for factoring and Matyukhin for the DLP in finite fields. This new work gives a nice polynomial selection idea that leads to an improved algorithm. The algorithm works with V > 2 number fields, and a relation results from smooth values in any pair of them.

Maike Massierer: Index calculus in the trace zero variety

Let E be an elliptic curve over \mathbb{F}_p and consider the group E( \mathbb{F}_{p^n} ) for n > 1. The trace zero subgroup was defined in Elisa Gorla’s talk. The idea is to use summation polynomials in E( \mathbb{F}_{q^n} ) to solve the ECLP in the trace zero subgroup, by writing random points in the trace zero group as a sum of n-1 points. The current work does not exploit symmetries and so it is unclear whether the approach is faster in practice than doing the computation using symmetrized summation polynomials, and sums of n points, in the full group. The paper on this work, joint with Gorla, is eprint 2014/318.

Antoine Joux: Discrete logarithms in small characteristic finite fields (through the ages)

Antoine, using the blackboard, gave a gentle historical summary of the function field sieve for finite field discrete logarithms in small characteristic. He showed the evolution of ideas that has culminated in the new quasi-polynomial-time algorithm, while simultaneously trying to demolish the lecture room.

Thorsten Kleinjung: On a remark of Robert Granger

Thorsten, in another blackboard talk, presented some theoretical results about certain technical issues regarding recent algorithms for the DLP in finite fields of small characteristic.

Alina Dudeanu: Cyclic isogenies in genus 2

The talk used CM theory to compute isogenies of Jacobians of genus 2 curves with cyclic kernel of prime order \ell. Previous work was restricted to (\ell,\ell) isogenies (i.e., having non-cyclic kernel with \ell^2 elements).

Karl Rubin: ECDLP and Kolyvagin systems

Karl outlined a set of ideas (joint work with Alice Silverberg) that would allow to reduce the ECDLP (for arbitrary elliptic curves) from a cyclic group of order N to the DLP in two certain auxiliary finite fields \mathbb{F}_{\ell}^* where N \mid (\ell - 1) but \ell is not too large. The idea is based on Galois cohomology, Kolyvagin systems, local Tate pairings, a global reciprocity law, and various other things that are not fully clear to me. We are reassured that a certain key step in the process cannot currently be computed. But it will be very interesting to see how this topic evolves when others start to look into it.

Damien Robert: Pairings on abelian varieties and discrete logarithms

It is known that the Tate-Lichtenbaum pairing (as described by Frey and Rueck) is better than the Weil pairing for reducing the ECDLP from E( \mathbb{F}_q ) to \mathbb{F}_{q^k}. This is because the Weil pairing requires the full torsion to be computed, whereas the T-L pairing can be non-degenerate when computed over a smaller field. This benefit also holds for Jacobians of curves. Damien considers the case of general principally polarized abelian varieties. The Weil pairing is defined in this case, but not the Tate-Lichtenbaum pairing. He explains a pairing and how to compute it.

Day 5

Hendrik Lenstra: Finding roots of unity

The talk is about two problems in commutative algebra. I apologise to Hendrik for not summarising the talk in its full generality. Let A = \mathbb{Z}[x]/(f(x)) and F = \mathbb{Q}[x]/(f(x)) where f(x) is monic in \mathbb{Z}[x] (resp. \mathbb{Q}[x]) but not necessarily irreducible. One problem, a generalisation of the DLP in \mathbb{Q}^*, is: given b_1,\dots, b_t \in F^* to generate a \mathbb{Z}-basis for the kernel of the map (m_1, \dots, m_t) \in \mathbb{Z}^t \mapsto \prod_i b_i^{m_i}. The other problem is to compute a set of generators for the group of roots of unity in A.

In a beautifully presented blackboard talk, Hendrik sketched some of the ideas in commutative algebra that are used to design deterministic polynomial-time algorithms for these problems, and to prove their correctness. This was joint work with Guogiang Ge and Alice Silverberg (at different times).

At the end of the talk, the prize for best talk by a “junior researcher” was awarded to Vanessa Vitse.

Daniel Bernstein: Hyper-and-elliptic-curve cryptography

Dan gave a speedy summary of several recent papers:

  • Daniel J. Bernstein, Mike Hamburg, Anna Krasnova and Tanja Lange. Elligator: elliptic-curve points indistinguishable from uniform random strings. ACM Conference on Computer and Communications Security 2013.
  • Daniel J. Bernstein and Tanja Lange. Non-uniform cracks in the concrete: The power of free precomputation. ASIACRYPT 2013.
  • Daniel J. Bernstein, Chitchanok Chuengsatiansup and Tanja Lange, Peter Schwabe. Kummer strikes back: new DH speed records. eprint.

Then he moved on to some new results relating to the title of the talk. The idea is to have suitable hyperelliptic curves over \mathbb{F}_{p} whose Jacobian J is isogenous to an elliptic curve E( \mathbb{F}_{p^2} ). As is known, such constructions enable fast point counting. But Dan takes things further by noting that one can then use either group J( \mathbb{F}_p ) or E( \mathbb{F}_{p^2} ) and switch representations to exploit wherever the group operations are fastest. It is important that switching representations is fast, and that both groups J and E are secure and admit very efficient implementations. For someone who flies around the world so much, Dan showed admirable concern for the environment. The details of this work will appear at the ANTS conference in a joint paper with Tanja Lange. ANTS will be in Korea, which means another long flight for Dan, so he will need to find even more ways to save energy.

Benjamin Smith: Discrete logarithms on low genus hyperelliptic curves

Ben surveyed some geometric ideas behind the DLP on curves of genus 2 and 3, including issues of isogenies from hyperelliptic genus 3 curves to smooth plane quartics. He spoke about some recent theoretical work by Boyer.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

DLP workshop, Ascona

DLP workshop Ascona, May 5-9, 2014

The conference is taking place at the Monte Verita conference center, overlooking Lake Maggiore and the wonderful mountain scenery. The location is a former utopian community that practised strict vegetarianism and nudism. The conference meals are still somewhat vegetarian, but fortunately the participants are wearing clothes.

Day 1

Pierrick Gaudry: Yet another variant for DLP in the upper medium-prime case

The talk was about index calculus algorithms for the DLP in \mathbb{F}_{p^n}^*. The focus was the “upper medium prime” case, which is when p = L_{p^n}( 2/3, c ). This is the boundary point where the number field sieve stops being the best method and one needs to consider true “medium prime” versions of the algorithm. It is known that one can achieve subexponential complexity L_{p^n}( 1/3, c ) in this case, where c \le (128/9)^{1/3}. But the goal is to get smaller c in this case (e.g., c = (64/9)^{1/3}). Some nice pictures were shown, that convinced everyone that it is a non-trivial problem to understand what is going on.

Rob Granger: Resisting and eliminating smoothness heuristics

Rob talked about the DLP in finite fields of small characteristic and summarised some of his recent joint-papers and computational records on the topic (already mentioned in this blog post). The main theme of the talk was that smoothness heuristics are no longer required to analyse these algorithms, which is quite surprising when one considers the history of index calculus algorithms. He also presented a new descent argument which is easily explained with a cute picture.

Jens Zumbraegel: Computing discrete logarithms

This talk followed on from Rob’s talk, giving more details of the practical issues that arise in practical computations of record-breaking finite field discrete logarithm computations. It was argued that the supersingular elliptic curve over \mathbb{F}_{2^{1223}} with embedding degree 4 can be broken in around 2^{59} operations, much lower than the desired security level.

Steven Galbraith: Degustazione of the ECDLP

The talk surveyed Pohlig-Hellman, Baby-step-giant-step, Pollard rho and Kangaroo, and summation polynomials. This was reporting joint work (some unpublished) with various people: Wang and Zhang; Pollard and Ruprai; Gebregiyorgis.

Vanessa Vitse: Summation polynomials and symmetries for the ECDLP over extension fields

Vanessa spoke about the paper “Symmetrized summation polynomials: using small order torsion points to speed up elliptic curve index calculus” with Faugère, Huot, Joux and Renault to be presented next week at EUROCRYPT. The paper is about using symmetries on summation polynomials to obtain equations that are sparser and of lower degree, and hence easier to solve.

Claus Diem: On the DLP for non-hyperelliptic curves of a fixed genus

Claus presented joint work with his PhD student Sebastian Kochinke. He is extending his well-known work that gives an \tilde{O}( q ) algorithm for the DLP in the divisor class group of a plane quartic (genus 3) over \mathbb{F}_q. His speculation is that one can solve the DLP in the divisor class group of a non-hyperelliptic genus g curve in \tilde{O}( q^{2 - 2/(g-1)} ), but rigorously proving this is still open and depends on a number of deep problems in algebraic geometry. The surprising conclusion of the talk was experimental results suggesting that the DLP for non-hyperelliptic genus 4 and 5 curves has the same complexity in practice.

Day 2

Elisa Gorla: Efficient representations of the trace-zero subgroup

If E is an elliptic curve over \mathbb{F}_q then the trace zero subgroup of E( \mathbb{F}_{q^n} ) is the set of points P such that P + \sigma(P) + \cdots + \sigma^{n-1}(P) = 0 where \sigma is the q-power Frobenius map. A natural problem is to represent elements of this set using (n-1) coordinates in \mathbb{F}_q. Elisa reported joint work with Maike Massierer about ways to achieve this compression and also get efficient decompression. The main focus is compressing elements of the set of orbits under Frobenius of elements in the trace zero subgroup (i.e., the analogue of XTR). She gave nice geometric methods that work in greater generality than previous techniques.

David Kohel: On the quaternion l-isogeny path problem

David gave the first blackboard lecture of the workshop. He spoke about a joint paper with Petit, Lauter and Tignol about finding \ell-power elements in left O-ideals in a quaternion algebra. This problem is the algebraic analogue of finding a path in the \ell-isogeny graph from a fixed (special) supersingular elliptic curve E_0 to an arbitrary supersingular elliptic curve. Hence, it is related to inverting the Charles-Goren-Lauter hash function.

Ronald van Luijk: Explicit equations for Jacobians of curves of genus 2 and 2-coverings

The talk was about equations for jacobians of elliptic curves and genyus 2 curves, and certain representations of addition by points of small order. There were nice diagrams, but no immediate cryptographic relevance.

Florian Hess: Computing zeta functions of abelian covers

An abelian cover is a curve X over a finite field k with a rational map to a curve C such that the field extension k(X) / k(C) is Galois with abelian Galois group. Florian gave a method to compute the zeta function of X using the representation of the zeta function as a product of L-series. The L-series are in turn computed by a “brute-force” method. A live Magma demonstration computed the zeta function of a genus 881 curve over \mathbb{F}_3 in around 14 seconds.

Christophe Petit: The successive resultant algorithm and connection to ECDLP over binary fields

Christophe presented some ideas for a new algorithm for factoring polynomials in p(x) \in \mathbb{F}_{p^n}[x]. The idea is to use a tower of \mathbb{F}_p-vector spaces and to project roots of p(x) down through this tower. The hope is that the ideas can be adapted to the case of multivariate polynomials, but this is still unclear. Such a result would have implications to index calculus algorithms. The paper will appear at the ANTS 2014 in Korea.

Pierre-Jean Spaenlehauer: Groebner bases and bilinear systems

After Christophe claimed that everybody would probably rather forget about the technical difficulties of Groebner bases, Pierre-Jean stepped up to give a beautiful talk that made the whole thing look simple, and the analysis far from awful.

Tanja Lange: On the practical exploitability of Dual EC DRBG in TLS implementations

Tanja presented work of a group of 9 researchers on the notorious Dual elliptic curve random generator, as standardized by ANSI, ISO, and NIST. The talk was a ripping ride through the recent controversies including the Snowden files and the promotion of this pseudorandom generator by the RSA company in its BSAFE toolkit. The main focus was an explanation of how any agency with the “backdoor” could exploit this during the TLS protocol to recover significant useful information about a target. For full details visit projectbullrun.org.

The conference continues for the next 3 days, and further information will be put on this blog.

– Steven Galbraith, with help from David Kohel, Tanja Lange, Florian Hess, Ben Smith and Christophe Petit (in the bar)

Posted in Uncategorized | Leave a comment

ECC 2014, Chennai, India, October 8–10.

The 2014 conference on Elliptic Curve Cryptography will be held in Chennai in October. For more details visit the ECC conferences webpage.

While you visit this page you can find a further memorial article about Scott Vanstone, and a link to a video of Scott’s acceptance speech from when he was presented a special award at the ECC2010 conference for “seminal contributions to research, development, standardization and commercialization of elliptic curve cryptography”. The speech recalls the history of his interest in cryptography and of the company Certicom. It is worth watching.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Scott Vanstone

Scott Vanstone died on March 2, 2014. Four of his close colleagues have written an obituary.

Scott did more than anyone else to raise the profile of Elliptic Curve Cryptography, and its adoption into real-world systems.  His impact on the development of this subject was enormous.

  — Steven Galbraith

Posted in Uncategorized | Leave a comment