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

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

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

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

## New discrete logarithm records, and the death of Type 1 pairings

In the last few days there have been several announcements of record-breaking discrete logarithm computations:

All these papers are using the algorithmic ideas introduced by Joux and others in 2013.

The third result listed above is a continuation of the sort of records previously announced, in particular, since 9234 = 18 * 513 and 513 = 2^9 + 1, it is again using “twisted Kummer” extensions over GF( 2^9 ). This result breaks by a large margin the previous world-record for finite field discrete logarithm computations. It is a great result.

However, the first two results are particularly interesting from the point of view of pairing-based cryptography. Both of the computations are for fields that very naturally arise in pairing-based cryptography using supersingular curves. Importantly, the “large prime” in the field size is not a power of 2 plus or minus 1. Hence these records have shown that the new algorithmic ideas can be applied to a wider range of fields than the previous computations might suggest. This gives evidence that all supersingular elliptic and hyperelliptic curves over moderately-sized fields of small characteristic are not secure for pairing-based cryptography.

One interesting consequence of these works is that “Type 1″ pairings are now essentially dead. Recall that Galbraith, Paterson and Smart “Pairings for cryptographers” (Discrete Applied Mathematics, 2008) introduced a classification of pairings into Type 1, Type 2 and Type 3 (there is also a Type 4, but it is rarely used). Type 3 pairings are usually the most efficient, but some authors have preferred Type 1 pairings as they are convenient in certain applications. Hence, there are a lot of cryptographic protocols in the literature that have been designed only for Type 1 pairings.

The main way to implement Type 1 pairings is to use supersingular curves. There are traditionally two choices:

1. using fields of characteristic 2 or 3;
2. using supersingular elliptic curves (embedding degree 2) over GF( p ) where p is at least a 500-bit prime (and, nowadays, probably at least a 1500-bit prime).

The first option was by far the most efficient, but the recent discrete logarithm algorithms and computational records mean it must now be considered insecure. Hence we are stuck with the relatively slow choice of elliptic curves over GF( p ). It means that Type 1 pairings will now be much much slower than Type 3 pairings. It would be better in future to design protocols that do not require Type 1 pairings.

One technical remark:  One can implement Type 1 pairings using ordinary elliptic curves over any field.  One works in a subgroup that is not an eigenspace for Frobenius, and uses the trace map as a “distortion map” to ensure a non-degenerate pairing.  However this approach is also extremely inconvenient: there is no compact representation for elliptic curve points, and the pairing computation is also slow.  So the claim that Type 1 pairings are dead remains true.

— Steven Galbraith

Posted in Uncategorized | 3 Comments

## Algorithmic Number Theory Conference, 2014

The call for papers is now available for the ANTS conference.

This year the proceedings will be published in the open access London Mathematical Society Journal of Computational Mathematics. The submission deadline is February 20.

– Steven Galbraith