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

This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to DLP workshop Ascona. Second and final part.

  1. Felix Fontein says:

    Thanks a lot for the summary!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s