## 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)