Two new papers on the ECDLP in characteristic 2

At the recent Eurocrypt conference there was a paper on the possibility of index calculus in elliptic curves over arbitrary finite fields of characteristic two. The paper is: Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields by Jean-Charles Faugère, Ludovic Perret, Christophe Petit and Guénael Renault.

The algorithm in the paper is based on the idea of a decomposition based index calculus attack. A heuristic analysis presented in the paper gives a (heuristic) upper bound for the running time of the algorithm which is still worse than the running time for a brute force attack (and therefore in particular worse than the time for the rho-method). The paper is however still interesting: First, experimentally, the algorithm seems to perform much better and second, the paper does contain an interesting observation. Will will come to this below.

In addition to this paper, a related paper has recently been uploaded on the IACR archive: On Polynomial Systems Arising from a Weil Descent by Christophe Petit and Jean-Jacques Quisquater. In this work, it is claimed that with a closely related algorithm one can solve the DLP in elliptic curves over F_2ⁿ, n any natural number in an expected time of exp(O(n^{(2/3) log(n)})). If correct the expected running time would therefore be subexponential in n. This would be a major breakthrough of course.

In this post, I want to evaluate the two papers. For this, and also because it has not been done yet in this entry, I am first going to give some background on the idea of decomposition based index calculus algorithms.

Some background

To put the new works into perspective, I now give some information on the historical background of the approach.

It can justifiably be said that it all started with a talk by Gerhard Frey at the ECC conference of 1998. At this conference, he first pointed out the following:

Let K|k be an extension of finite fields of degree n, and let E be an elliptic curve over K. Then we can associate to E/K an n-dimensional variety W over k with the following interesting properties:

- There is a canonical group isomorphism between E(K) and W(k).

- W has a “geometric group law”, that is a group law defined by polynomials.

- W can be embedded in projective space.

- Regarded as a variety over K, W splits into a product of elliptic curves one of which is E itself. (This is however not true over k!)

By the way: A variety which can be embedded in projective space and which has a geometric group law is called an abelian variety, so W is an abelian variety. It is called the Weil restriction of E with respect to K|k.

If one starts with an elliptic curve given by an explicit affine equation, one can easily obtain a system of affine equations which define an affine part of W. The essential idea is to “expand the equations” over k. This process of “expansion” works for any field finite field extension K|k and any variety over K. I describe it here by an example which is slightly easier to state:

Let us consider the hyperbola H given by the equation x² – y² -1 = i over the complex numbers, where i² = -1. We want to perform the expansion with respect to the extension C|R. We “expand” the variables: x = x₁ + i x₂ and y = y₁ + i y₁, where the new variables only take real values. Then the defining equation is equivalent to:

(x₁ + i x₂)² – (y₁ + i y₂)² = i.

This is equivalent to the system of equations

x₁² – x₁² – y₁² + y₁² = 0 , 2₁x₂ – 2y₁ y₁ = 1.

So, if we define W as the variety over R given by these equations, we obviously have a bijection between H(C), the solutions to the original equation over C, with W(R), the solutions of the system of equations over R.

The very general observation by Frey was: Given that the Weil restriction of an elliptic curve is a higher-dimensional variety, one might use some geometric construction to attack the DLP in the elliptic curve. Concretely he proposed: Find a curve on the Weil restriction, map the DLP to the degree 0 divisor class group of the curve and solve it there by index calculus methods.

A requirement in order that this idea can be carried out is that one finds in an explicit way a curve of rather low genus as otherwise the index calculus method cannot be applied successfully. This lead to the so-called GHS attack, where G stands for Pierrick Gaudry, H for Florian Hess and S for Nigel Smart. They focused on elliptic curves over F_2ⁿ. For some parameters, for example for some elliptic curves n=127 they indeed found curves of very low genus on the Weil restriction. This was a major breakthrough.

One aspect of their approach is of interest here: They found the curves by intersecting the Weil restriction with hyperplanes. Briefly, this intersection V can be described as follows: Instead of expanding the x- and y-coordinate of points on the elliptic curve, one just expands the y-coordinates. One then has one variable for the x-coordinates and n variables for the y-coordinates. Like this, one obtains a 1-dimensional variety V in the Weil restriction whose points correspond to the points in E whose x-coordinate lies in k or is ∞.

Now, this intersection might contain several “components”. The really interesting curves can be found if the intersection splits into very many components and if one of the components is defined over k, the small field. However, for many (more accurately: for most) natural numbers n there are not enough components, the genera of the curves are two high. Moreover it turns out that in odd characteristic the situation is even worse, and here the obvious variant of the GHS attack clearly fails if n is prime and at least 11. An interesting aspect of the GHS attack and its obvious variants is that it can be formulated without even mentioning the Weil restriction: One just needs function fields in one variable.

The next step of the development was initiated by a paper by Igor Semaev: Summation polynomials and the discrete logarithm problem on elliptic curves, uploaded to the IACR server in 2004. Semaev presents some ideas for index calculus in elliptic curves over prime fields. If these will ever lead to an interesting result is a wide open problem. They highlighted however that it might be possible to apply an index calculus algorithm in elliptic curves themselves.

And this lead to a work by Pierrick Gaudry: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. The main idea is here: Let’s use the set of points of E with x-coordinate in k as a factor base. Note that this set corresponds to the points in V(k) as defined above. Then one can generate relations by solving systems of equations over k. To obtain these systems, one can use the so-called summations polynomials which were also introduced by Semaev. These polynomials indicate if n points on an elliptic curve add up to zero. Just as in the construction of the Weil restriction, one expands such a summation polynomial, obtaining a system of non-linear polynomial equations over k. And then one solves this system, for example with a Gröbner base method. The complexity to solve such a system can be described as “horrible” for growing “n”. (It is exponential in n and quickly becomes infeasible in practice.) However, for constant n the complexity is polynomial in the field size, thus very good (from an asymptotic point of view). As described, one can solve the DLP in elliptic curves over F_qⁿ with fixed n in an expected time of O(q²) with this method. By decreasing the factor base, one can obtain an even better expected running time.

I have also made some contributions here. I realized this: Let us consider the DLP in elliptic curves over F_qⁿ, and let us grow q and n at the same time. Then solving the systems of equations, even though “horrible”, might still lead to a subexponential expected running time. I have two works on this: On the discrete logarithm problem in elliptic curves and its successor On the discrete logarithm problem in elliptic curves II. In the first work, I use exactly the factor base described above. In the second work, I increase the factor base. I prove with a corresponding algorithm that under some restriction on q and n, one can obtain a subexponential expected running time. The best expected running time I obtain is for a · (log(q))^1/2 ≤ n ≤ b · log(q)^1/2 for some constants a,b >0. For this range of q and n, the expected running time is exp(O(log(qⁿ))^2/3).

The new works

After this historical excursion I now come to the new papers. Both works are closely related to my article “On the discrete logarithm problem in elliptic curve II”.

In the two works, the factor base is now defined by an n’-dimensional variety, where n’ is between 1 and n. One sets m to be about n/n’, and for a given point P, which is a given combination of the input elements, one searches for a relation of the form P₁ + … + P _m = P with P_i in the factor base.

By the structure of the systems of equations, one can expect that one can solve one system in a time of exp(O(mn)) · log(q)^O(1). (A rigorous variant of this statement is employed in my works.) The two papers we are concerned with here deal with the DLP in elliptic curves in characteristic 2. So, here one wants to solve systems over F₂. Now for a system in n variables x₁, …, x_n over F₂, one also has the “field equations” x_i² = x_i. These can be inserted into the system. Another description of the same observation is: We want to solve a system of equations over a boolean ring instead of a polynomial ring. The big question is now this:

What happens to the complexity if we insert the field equations?

One answer to this question was given in Bardet, Faugere, Salvy, Yang in Asymptotic Behavior of the Degree of Regularity of Semi-Regular Polynomial Systems (MEGA 2005). On the basis of some heuristic arguments it is argued in this paper that for “most systems”, the complexity drops, but it does not drop in a dramatic way.

Now, the new papers give some indication that for the particular systems employed here the drop is more dramatic. Let us first discuss the paper presented at Eurocrypt: As said the analysis is heuristic, but the authors were very careful to make no unfounded claims. There is a parameter, α in the paper, and one has n’ =^α, m=n^1-α. The system solving relies on a dedicated method for the particular systems.

In the heuristic analysis it is assumed that α ≥ 1/2. The analysis then indicates that independently of α the complexity to solve one system with the given method is upper bounded by 2^{ω/2 · n}, where ω is the constant for the linear algebra. This heuristic upper bound for the complexity just to solve one system of equations is worse than the complexity for a brute force attack on the DLP. In fact, it is even worse than the time needed to solve one system by brute force. This is clearly disappointing. On the other hand the result holds independent of α. And clearly, it is much better than the bound exp(O(mn)) which holds without any assumption. And it is important to note that it is, well, an upper bound.

The total expected running time is then minimized if the factor base is minimized, and this is the case for α = 1/2. The total expected running time is then 2^{(ω/2 +o(1)) · n}. Of course, this is not yet a major breakthrough to the ECDLP in characteristic 2. In fact, it is not even a minor breakthrough. But nonetheless the paper is interesting and might lead to further developments.

In the second paper a more bold assumption is made. On the basis of this assumption, the subexponential expected running time indicated in the beginning is obtained. The assumption can be stated as follows: Usually, in the application of Gröbner base algorithms like F₄ employed with a “normal” strategy (“normal” is a technical term here, it means that one always considers the S-polynomials of smallest degree), one sees the following: If the degree drops during the computation for the first time, the highest degree is not much higher than this degree. This observation clearly holds for most randomly generated systems, and there are strong heuristic arguments why it should hold for such systems.

Now, in this paper it is observed that one has a degree drop almost immediately, so if one makes the indicated assumption, one obtains a very favorable expected running time. The big question is here of course if the assumption does hold for the special systems used here. Experiments are reported which assert that the assumption is correct. It is however very difficult to conduct experiments, and therefore the parameters are quite small in the experiments. All in all it is not clear whether the assumption holds. It might hold or it might not. Maybe it fails but a weaker statement holds. This is all very unclear at the present time.

Conclusion

In conclusion, we have here interesting works on the ECDLP in characteristic 2 (and possibly also in other small characteristic). Both works show that the field of solving systems of equations over small fields is of great relevance for the security of elliptic curve cryptography over such fields. And both works indicate that the particular systems obtained by the summation polynomials might be easier so solve than “random” systems.

Further progress might come from applying different and maybe more dedicated algorithms to the particular systems.

Even if some of the heuristic assumptions can be removed or at least supported by stronger arguments, there is still the question of applicability. My personal opinion is that it should be really hard to make the ideas of the two papers practical. Clearly there is no immediate threat to ECC in small characteristic.

So there is still a lot of work to be done here. Of course this is a buzzword. But still, it’s true – as always of course.

- Claus Diem

What on earth is “index calculus”?

If you are not an expert on mathematical aspects of public key cryptography you might wonder: What on earth is this method called “index calculus”? In fact, when I started my doctorate, I heard people speaking about that from time to time, and I had no clue what the method was all about. I thought that a method with such a strange name must be very, very complicated.

With this entry, I want to convince you that it is not really very complicated at all, and even its name makes sense.

The name

So, let’s start with the name. All kind of things are called “index” in mathematics, and given that we compute in groups here, it is natural to assume that “index” refers to the index of a subgroup in a group here. That’s what I thought for quite some time at least.

Well, it’s not so. In fact, “index” is the original term for “discrete logarithm” in the “classical” setting.

In the Disquisitiones Arithmeticae by Carl Friedrich Gauss from 1801, the following definition can be found.

Let p be a prime, let B be a primitive root modulo p, and let A be some natural number prime to p. Then any non-negative integer e with B^e congruent to A modulo p is called index of A modulo p with respect to the basis B.

He then says that all indices of one number (with respect to a fixed modulus and base) are congruent to each other modulo p-1, and that these indices are going to be regarded as equivalent.

Let us call always call the smallest non-negative integer satisfying the definition the index, and let us denote the index by ind_BA. Analogously to the usual logarithm, we have ind_BA₁ + ind_BA₂ ≡ ind_B(A₁ + A₂) modulo p-1.

The index played an important role in explicit computations in the 19^th century. And just as one used tables of logarithms, one used tables of indices or discrete logarithms in the modern terminology. Clearly, such a table can be restricted to indices of numbers below the modulus p.

The definition of an index be generalized for all numbers modulo which there exists a primitive root. These are the numbers 1,2,4,p^k and 2p^k for a prime p and a natural number k. A book consisting of such tables was published in 1839 by Carl Gustav Jacob Jacobi: the Canon Arithmeticus. It contains tables of indices modulo all prime powers below 1000. Let us mention how the tables were computed: First, for each index, the corresponding number was computed, by iteration. Then this table was “inverted” to obtain the table of indices. (By the way: Jacobi published the book, but the computations were done by many people. I once read or heard that some of the computations were done by Dirichlet’s wife, for example.)

We have thus clarified what the first part of the term “index calculus” means. And the second part? Does it have anything to do with “calculus”? Well, no. Here “calculus” is used in the original meaning of algorithmic method. So, it’s an algorithmic method to compute indices. But it’s not just any method but a particular approach.

The basic ideas

To motivate the approach, we make some observations on tables of indices. For these observations, please consider for the moment the “old” times where people made concrete computations by hand and printed tables.

The basic question is this: Let a particular prime p and a primitive root be fixed. Does one then really need a full table of indices modulo p?

The answer is “no”, provided one is willing to perform some computations if one is given a particular natural number and is asked for the index.

Namely:

1. Let’s assume that we can factor quickly any number below p. This is clearly the case for much larger numbers than 1000, which was the bound in the tables by Jacobi. Then we only need the indices of primes below p.

2. It suffices to have a sufficiently large table of indices of prime numbers below a particular bound. For this, let’s assume we have a table of indices below a bound S, and let A be an arbitrary number prime to p whose index we want to determine. We now consider C = A · Bⁱ mod p for i=1,2 … until we have found a number which splits into primes below the bound S. Then we can look up the indices of the primes involved in the factorization of C and compute the index it. The index of A is then ind_BC -i. So, to determine the index of A we compute A · Bⁱ mod p until this slits “over the table”. (By the way: Here and in the following I use “mod” as an operator, like is done in programming languages.)

Nowadays one employs two terms here: The bound S is called the smoothness bound, the set of primes below S is called the factor base and a number which splits into primes below S (that is, over the factor base), is called S-smooth of simply smooth.

Given this approach, one now is faced with the task to produce a table of all indices for a particular modulus and base below some bound. One way to perform this computation is to compute all indices as done by Jacobi and to only print a partial table. But is there a more efficient method?

Indeed there is, and it is based on relation generation and linear algebra. The basic idea is as follows:

Let’s say the factor base consists of the primes P₁ … P_n.

We now consider powers of B modulo p.

Say we have Bⁱ mod p = P₁^r₁ … P_n^r_n. (This is called a “relation”.)

Then we have this “relation of indices”: i ≡ r₁ ind_B P₁ + … + r_n ind_B P_n modulo p-1.

If we now have at least n such relations, we might try to determine the unknown indices by a linear algebra computation modulo p-1. Note here that this a bit more complicated than usual in linear algebra because p-1 is not a prime (except if p=3 of course but then question to determine a table of indices is not too complicated …).

So, this is the “index calculus” method in a classical description. Below I am going to present a slightly different method for the task to compute just one index, not a table of indices.

Now a bit of history: As far as I know, the method is due to Maurice Kraitchik. It appeared in one of his books Théorie des Nombres from 1922. Kraitchik liked to do explicit computations, and his books are written from that perspective. He demonstrates the method with an example. Interestingly, he even used the method of “large prime” variation. Here, one allows up to one prime larger than the smoothness bound in each relation. If one has two relations with the same large prime, one subtracts them and obtains a relation over the factor base.

In the 1968 Alfred Edward Western and Jeffrey Charles Percy Miller published tables of indices computed with the relation generation and linear algebra method. For quite some time, the index calculus method was then incorrectly attributed to Western and Miller or (by Miller) to Western. The term “index calculus” is due to Andrew Odlyzko. (He writes: “We will refer to it as the index-calculus algorithm.”) It is also interesting to note that the method is much older than the ρ-method or the baby-step-giant-step method.

Possible generalizations and a variant

One can say that up to now, we wanted compute discrete logarithms in the groups F_p^*. In principle, one can substitute this group by any finite group. We fix a particular class of explicitly given finite groups.

The discrete logarithm problem for the given class of groups is then: Given a group G from the fixed class and a,b in G with a in the group generated by b, compute e with b^e = a.

Particular classes of groups of interest are:

- F_p^*, p prime,

- F_q^*, q a prime power,

- E(F_q) for an elliptic curve E over F_q,

- The degree 0 divisor class group of a smooth, projective curve over a finite field (or — what is the same — of a function field in one variable) over a finite field.

We restrict ourselves to abelian groups and now write the group law additively. As said, the input is a group G and a,b in G with a in the group generated by b.

A variant of the index calculus method as described above to compute just the desired discrete logarithm (rather than a table of indices) is as follows:

“Direct” index calculus

1. Compute the group order N := #G.

2. Fix a so-called “factor base” F = {p_1, p_2, …}, which is a subset of G.

3. Compute more than #F so-called “relations” ∑_j r_ij p_j = α_i a + β_i b. Store these in a “relation matrix” R = ((r_ij)).

4. Compute a non-trivial vector γ over Z/nZ with γ R = 0.

One now has ∑_i γ_i α_i a + ∑_i γ_i β_i b = 0. Thus if ∑_i γ_i α_i is invertible in Z/NZ, one has a = – (∑_i γ_i β_i) / (∑_i γ_i α_i) b.

Then problem is then solved.

To my information, this approach is due to Pierrick Gaudry, and it first appeared in his work on index calculus in the class groups of hyperelliptic curves. Needless to say, an application of this method depends on several subalgorithms. For example, for the “classical” application in F_p^*, one can choose the factor base as the set of primes below a bound S, the so-called “smoothness bound”. Then one can generate relations by choosing α_i and β_i uniformly randomly modulo p-1 and by performing trial division with factor base elements. Note here that for computations in the group F_p^*, the addition in the algorithm has to be substituted by multiplication in this group.

The complexity theoretic perspective

Since about the 1960′s, an additional focus on computational problems has emerged: Rather than being interested in explicit computations, one is now also interested in proven results on asymptotic running times. It seems to be extremely hard to obtain any interesting proven upper bounds with deterministic algorithms. But for randomized algorithms, one can obtain nice results. These results can be stated in two ways which are in fact equivalent. The first way is: One states that one has a Las Vegas algorithm which operates in a given time. Here the output is always correct but the algorithm might fail with a probability of up to 1/2. Or one states an upper bound on the expected running time of the algorithm. Note here that “expected running time” refers only to the internal randomization of the algorithm. There is no averaging on the input set.

A classical theorem is:

With a randomized algorithm, the classical discrete logarithm problem can be solved in an expected time of exp((√2 + o(1)) · (log(p) · log log(p))^1/2).

This result, of course based on the index calculus method, is due to Carl Pomerance. It can also be found in a work by Enge and Gaudry in which they give a general framework for index calculus algorithms. The algorithm by Pommerance is based on the original index calculus method whereas the algorithm by Enge and Gaudry is essentially based on the “direct” approach presented above. In both works, the algorithms are slightly more complicated in order that a proven upper bound on the expected running time can be achieved.

In their general framework, Enge and Gaudry assume that one has an explicit homomorphism from a free abelian mononoid to the group, like for example the homomorphism from the natural numbers prime to to F_p^*. (The natural numbers are a free abelian monoid on the prime numbers.) Just as prime numbers are natural numbers and not elements of F_p^*, the factor base elements are then generators of the free abelian monoid. This general framework can then for example also be applied to computations of discrete logarithms in multiplicative groups of finite fields of small characteristic and to degree 0 divisor class groups of complete, non-singular curves of not too small genus over finite fields. In the former case, one substitutes prime numbers with irreducible polynomials and in the latter case one substitutes them with prime divisors.

In contrast to the general framework by Enge and Gaudry, in the “direct approach” presented above the factor base elements are group elements. This variant is useful for applications of the index calculus method to elliptic curves over extension fields. This will be the content of my next entry.

— Claus Diem

ECC conferences

The 2012 ECC conference will be held in Queretaro, Mexico on October 28-31.  More details about this event, and all the other ECC conferences in the past, can be found at http://www.eccworkshop.org/

The Eurocrypt 2012 paper of Joux and Vitse

Antoine Joux and Vanessa Vitse have updated their paper “Cover and Decomposition Index Calculus on Elliptic Curves made practical: Application to a previously unreachable curve over F_{p^6}” on eprint (eprint 2011/020). As I have already mentioned, this paper is accepted to EUROCRYPT 2012.

The paper is about “Weil descent” attacks on the ECDLP for curves over extension fields. More precisely they combine a cover attack (transforming the ECDLP to a DLP in some divisor class group of a high genus curve over an extension field of smaller degree) with Gaudry’s index calculus method (using summation polynomials for groups over extension fields). The paper does not contain any new fundamental concepts, but it gives tricks and techniques that can lead to large speedups for practical computation. The main computational result in the paper is a 149-bit elliptic curve discrete logarithm computation (taking about one month of elapsed time). This is an impressive computational result. In contrast, the current record for Pollard-type methods is around 110 bits (and a major campaign to solve a 130-bit instance for a Koblitz curve has already been running for over two years elapsed time).

Rather than discuss all the contents of the paper I will focus on the computational result.

The ECDLP instance is, of course, very special. It is important to note that it is not used for any application, and is already known to be a “weak curve”. First, the elliptic curve is defined over F_{p^6} where p is a 25-bit prime (the group order is four times a 149-bit prime). Second, the elliptic curve is of the very particular form y^2 = x(x – alpha)(x – alpha^{p^2}) where alpha in F_{p^6}, so that (as follows from work of Diem/Momose-Chao/Theriault) the Gaudry-Hess-Smart technique gives a method to transfer the discrete logarithm problem to a hyperelliptic genus 3 curve over F_{p^2}.

The first part of the attack is thus to transfer the DLP to the divisor class group of the hyperelliptic genus 3 curve over F_{p^2}. Now one can attempt to solve this DLP using Gaudry’s index calculus algorithm (inspired by Semaev’s summation polynomials). Instead of using summation polynomials, the authors follow a suggestion by Nagao to compute relations by computing Riemann-Roch spaces. Such computations boil down to solving systems of non-linear polynomial equations using Groebner basis methods. One of the main ideas in the paper is to pre-compute a “generic” Groebner basis for a “generic” system of such polynomials. This enables the authors to employ a sieving process, and this leads to an enormous practical speedup in the algorithm. The collection of relations using sieving is parallelised: the authors used 1024 cores for about 3 days to collect the required relations. The factor base was chosen to have size 2^{24}.

Rather than using a large-prime variant (which would be hard to combine with the sieving), the authors perform structured Gaussian elimination to eliminate about four-fifths of the elements of the factor base. The remaining linear algebra problem is solved using a Lanczos method and this is by far the most time-consuming part of the process (taking about 28.5 days). I am focussing here on the real elapsed time rather than total computational resources since what really matters in practice is the actual elapsed time of a computation, and some aspects of the algorithm cannot be arbitrarily sped-up using parallelisation.

To summarise, although this instance of the ECDLP was “clearly weak”, it was not at all clear that it could be solved with relatively modest computing resources in such a short time. The importance of the paper is to show that the Gaudry/Nagao algorithm can be made much more practical than expected in certain cases by using some good ideas and careful implementation.

What impact does this paper have on our understanding of the ECDLP over general extension fields F_{p^n} with n >= 4?

I suppose the main impact is to re-inforce that theoretically weak cases really should be treated with caution. Once the theoretical tools are in place, one should not be surprised if implementation tricks enable relatively large instances to be solved in relatively little time.

The paper discusses n = 6 in detail and gives several cases different to the one mentioned above. The case n = 4 is also studied, and a smaller improvement over the previous “state of the art” is obtained. In both cases it is not possible to attack a fully general elliptic curve over those fields, instead it would be necessary to use isogenies to pass to one of the special families of curves and this process is slow if the families are “sparse” among all curves. For prime values of n (such as n = 3, 5 and 7) one cannot combine the two methods, and so the paper does not discuss these cases (though the improvements to the Gaudry/Nagao method may be of interest). The cases n = 8 and 9 might be interesting to study, by again using a covering attack with respect to the degree 2 or 3 extension and then using Semaev/Gaudry/Nagao. For general n one needs to have good theoretical results about covering attacks to get the process started.

— Steven Galbraith

Eurocrypt 2012

The list of accepted papers for Eurocrypt is now public. 

You can find it at the below link:

http://www.di.ens.fr/~pointche/Events/EC12/final-list.txt

I was on the committee and I am quite excited by a couple of the papers.   I have been looking forward to the time when I can bring them to your attention.  First there is the paper “Cover and Decomposition Index Calculus on Elliptic Curves made practical. Application to a previously unreachable curve over Fp^6″ by Antoine Joux and Vanessa Vitse.  This paper is an improved version of the paper eprint.iacr.org/2011/020 and it contains a much more impressive computational example.

But more significant from a theoretical point of view is the paper “Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields” by Jean-Charles Faugère, Ludovic Perret, Christophe Petit, and Guénaël Renault.  Despite its modest title, this paper is nothing less than a strong step towards establishing that the ECDLP has subexponential complexity in characteristic 2! At the moment it seems that the result will not have any practical impact on the ECDLP for real-world examples, nor any impact on elliptic curves over prime fields.  But it does challenge the often quoted statement that “there is no subexponential algorithm for the ECDLP”.

I’ll give more details on this blog when the papers actually become public.

  — Steven Galbraith

Google uses ECC

I noticed this blog post about Firefox and Chrome using ECC whenever you visit a secure Google page.

— Steven Galbraith

Three news items

I apologise for the lack of posts on this blog in recent months. Here are three brief news updates:

 

1. There will be a Pairing 2012 conference.  It will be held in Cologne, Germany on May 16-18, 2012. The paper submission date will be January 30, 2012.  The proceedings will be published after the conference. More details will be advertised here once they are decided.

 

2. INDOCRYPT 2011, PQCrypto 2011 and ASIACRYPT 2011 are all taking place around this time. You can find the accepted papers on the web.  There are some interesting papers at each of them.  In particular I list the following:

Pierrick Gaudry, David Kohel and Benjamin Smith.  Counting points on genus 2 curves with real multiplication.

David Jao and Luca De Feo.  Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.
 
Craig Costello, Kristin Lauter and Michael Naehrig. Attractive subfamilies of BLS curves for implementing high-security pairings.

Robert Dryło. On constructing families of pairing-friendly elliptic curves with variable discriminant.

 

3. I just uploaded a revised version of my book “The Mathematics of Public Key Cryptography”. The files can be found here:

http://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html

This book will be published by Cambridge University Press in early 2012.  When that happens, most of the pdf files will be removed from the webpage.

 – Steven Galbraith