809 bit finite field discrete logarithms

A couple of weeks ago, Barbulescu, Bouvier, Detrey, Gaudry, Jeljeli, Thome, Videau and Zimmermann announced a new finite field discrete logarithm record.  They have used the function field sieve algorithm to solve the DLP in GF( 2^{809} ), which is a prime field degree.

It would be easy for this result to be eclipsed by the recent discrete log computations in GF( 2^n ) where n is highly composite.  However, the case of GF( 2^{809} ) is a major advance over the previous records (namely GF( 2^{613} ) and GF( 2^{619} )), and it is a significant computation.

At some point it may turn out to be more efficient to solve discrete logs in GF( 2^p ), where p is prime, by embedding them into fields GF( 2^{p*m} ).  But for the moment, the best way to solve such problems appears to be the traditional use of the function field sieve. And so this new discrete log record deserves just as much acclaim as the previous results.

  — Steven Galbraith

New results on the discrete logarithm problem in finite fields of small characteristic

Two recent papers on eprint have made tremendous progress on the discrete logarithm problem in the multiplicative group of a finite field of characteristic two. The papers are:

• Antoine Joux, A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic, Cryptology ePrint Archive: Report 2013/095.
• Faruk Gologlu, Robert Granger, Gary McGuire and Jens Zumbragel, On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in F_{2^{1971}}, Cryptology ePrint Archive: Report 2013/074.

The story starts with Antoine Joux’s paper “Faster index calculus for the medium prime case: Application to 1175-bit and 1425-bit finite fields” which is accepted to Eurocrypt 2013 and can be found at Cryptology ePrint Archive: Report 2012/720. This paper is about the “medium prime case” (i.e., discrete logs in F_{p^n} where p and n are both “large” (e.g., n approx log(p)). The paper uses a factor base consisting of “linear polynomials” (read the paper for the precise details). It introduced a key idea (called “pinpointing” in that paper) which is an alternative approach to sieving.

The recent papers are motivated by the above work, but have two major differences. First is to consider composite degree finite fields F_{2^{mk}} as “medium prime” fields F_{q^k} where q = 2^m. Second is to find one smooth relation and then generate many more by simple polynomial transformations (the two papers differ in the details).

The resulting algorithms are then very different from previous approaches: The typical scenario would involve a factor base of size L_{2^{mk}}( 1/3, c ), and the cost of generating relations would dominate the computation. Now, the factor base is rather small and generating the relations is extremely fast (even polynomial-time). The linear algebra still must be performed, but this is not too bad since the factor base is small.

The problem now is the final stage of the index calculus algorithm: Writing the problem instance in terms of the factor base. Since the factor base is now very small, this problem has become much harder. The serious work in both papers is to provide solutions to this problem and to determine the complexity. The details differ and I will not go into them now (partly because I am still digesting them myself). Gologlu et al claim L_{2^{mk}}( 1/3, c ) while Joux claims a very unexpected running time of L_{2^{mk}}( 1/4 + o(1), c ) field operations (note that this is not the same as L( 1/4, c + o(1))). Both results are heuristic. Joux’s paper is still very sketchy and contains many typographical errors, but if correct then this will be the first sub-L( 1/3 ) algorithm known in the literature — a major advance!

For concreteness, the above discussion is restricted to characteristic equal to 2. However, the methods also apply to any small characteristic.

It is worth stressing that both papers apply to composite field extensions F_{2^{mk}} where m and k satisfy some relationship. The case of prime fields F_{2^k} can of course be embedding in F_{2^{mk}} for a suitable m. Asymptotically this might mean that field sizes for discrete logarithm cryptography need to be adjusted, but it seems that fields F_{2^k} where k is prime and 1000 < k < 2000 are probably not currently weakened by these ideas. However, in pairing based cryptography using supersingular curves over F_{2^k} of genus 1 or 2, one maps into fields of the form F_{2^{4k}} or F_{2^{12k}} (and, in char 3, F_{3^{6k}}) for prime values for k. Hence, one consequence of the new algorithms may be that characteristic 2 and 3 fields are not appropriate for pairing-based cryptography.

— Steven Galbraith

Accepted papers for EUROCRYPT 2013

The EUROCRYPT 2013 conference will be held in Athens, Greece on May 26-30, 2013. The list of accepted papers is here.  There are several papers of interest to researchers in ECC.

Joppe Bos, Craig Costello, Huseyin Hisil  and Kristin Lauter have a paper called “Fast cryptography in genus 2″.  This was posted on eprint with the less illuminating title Two is Greater than One.  The paper gives a detailed implementation of exponentiation for genus 2 curves using various techniques (such as the Kummer surface) and concludes that genus 2 can be faster than elliptic curves in some settings.

Antoine Joux has reported several new discrete logarithm records recently; see his posts in December, January and February at the Number Theory Web. At Eurocrypt his paper “Faster index calculus for the medium prime case. Application to a 1425-bit finite field” reports on some of this work. These results apply to finite fields of the form GF( q^n ) where q is not prime. They may be of relevance in pairing-based cryptography, which uses finite fields of composite extension degree.

The paper “Candidate Multilinear Maps from Ideal Lattices and Applications” by Sanjam Garg, Craig Gentry and Shai Halevi will also appear at EUROCRYPT.  I have already discussed this paper in an earlier blog post.

  — Steven Galbraith

Richard Crandall

I just learned that Richard Crandall died in December.  There are two obituaries here and here.  His book with Pomerance on primes is an excellent text for some aspects of elliptic curves and computational number theory.

  — Steven Galbraith

David G. Cantor

I learned that David G. Cantor died at the age of 77.  A small article is here.  I never met him, but he is well-known due to his paper “Computing in the Jacobian of a hyperelliptic curve” in Mathematics of Computation, 1991 that gives the famous Cantor algorithm for computing in hyperelliptic curves.

 – Steven Galbraith

Asiacrypt 2012

Asiacrypt 2012 was held during December 2-6 in the Beijing International Convention Center, Beijing, China.

In the first session on Monday a paper by Hayashi, Shimoyama, Shinohara and Takagi was presented. They outline how they broke a eta_T pairing by reducing the elliptic curve discrete logarithm problem for a supersingular elliptic curve over F_{3^97} to a discrete logarithm problem over F_{3^{6*97}}. They solved the latter 923-bit discrete logarithm using the function field sieve in less than 150 days using 252 CPU cores. See also http://ellipticnews.wordpress.com/2012/06/19/new-finite-field-discrete-log-record/.

The IACR distinguished lecture was given by Dan Boneh and titled “Pairing-based Cryptography: Past, Present, and Future”. In this talk the applications of pairings to cryptography were outlined and the current open problems were mentioned. The recent multi-linear maps paper (http://eprint.iacr.org/2012/610) by Garg, Gentry and Halevi (see also this blog post (http://ellipticnews.wordpress.com/2012/12/02/multi-linear-maps/)) was discussed.  

On Tuesday afternoon there was the social event; visiting either the Birdnest/Watercube on the Beijing Olympic park (right next to the convention center) or the national museum. This was followed by the rump session chaired by Ed Dawson. Besides a significant number of invitations to various crypto conferences and workshops there were some fun talks by Yvo Desmedt and Claudio Orlandi, and interesting announcements. Shamir announced new round reduced attacks on SHA-3 while the only elliptic curve related talk was by Kanaoka announcing TEPLA: a new software library for pairing based  cryptosystems.

On Wednesday morning I presented my work with Thorsten Kleinjung outlining how to speed up the elliptic curve scalar multiplication when the scalar is fixed. Our methods are particularly suitable for memory-constrained devices like graphics cards and are useful in the setting of factoring integers using the elliptic curve method. The number theory session contained two very interesting papers by Ducas and Nguyen related to lattices, and the paper by Petit and Quisquater describing a heuristic subexponential algorithm for solving the elliptic curve discrete logarithm problem for curves over F_{2^n}. The current elliptic curve systems are currently not threatened because it is estimated that this approach outperforms the generic algorithms for n>2000 (ssee http://ellipticnews.wordpress.com/2012/05/16/two-new-papers-on-the-ecdlp-in-characteristic-2/ for more info).

On the last day in the implementation section the work by Longa and Sica was presented. Here it was shown, based on the work by Gallant, Lambert and Vanstone (GLV) and Galbraith, Lin and Scott (GLS), how to achieve a four-dimensional scalar decomposition for some curves over F_{p^2}. This merged GLV-GLS approach is up to 50% faster compared to the GLV approach in practice. A number of implementations are presented and performance numbers for sequential and multi-core execution and implementations resistant against several side-channel attacks are given. This sets new performance 
software speed records for computing point multiplication. 

Hence, Asiacrypt 2012 was a very pleasant and interesting conference with quite some talks related to elliptic curve cryptography!

 – Joppe Bos

Multi-linear maps

Recently the paper Candidate Multilinear Maps from Ideal Lattices and Applications, by Sanjam Garg, Craig Gentry and Shai Halevi, has been posted on eprint. The paper gives a construction of multi-linear maps, and gives some applications.

Let’s first recall the background. Bi-linear pairings have been extremely useful for constructing cryptosystems, and it has been a natural question for a long time to consider multi-linear maps. An n-multi-linear map on a group G is a function e : G^n –> G_T such that e( [a1]P, [a2]P, . . ., [an]P ) = e( P, P, . . ., P )^{a1 * a2 * . . . * an}. Such a map would have interesting cryptographic applications. But previously no such map (secure for crypto) was known. Boneh and Silverberg, in the paper Applications of Multilinear Forms to Cryptography, discussed why it seems to be hard to find such maps from algebraic geometry.

The new paper uses lattices and homomorphic encryption to construct an n-multi-linear map for any n.

Their scheme and description use a quite different formulation from the elliptic curve case.  So it is first easier to translate elliptic curve pairings into this different language.  The discrete logarithm problem allows us to “encode” an integer a as the point [a]P.  This is *not* encryption, but a “one-way” encoding. By this we mean it is hard to decode, but easy to determine whether or not a given encoding corresponds to a given integer a.  The bilinear pairing is a function that takes two encodings [a1]P and [a2]P and outputs a binary string.  We think of this as “extracting” some information about the product a1*a2 of the integers corresponding to the two encodings.   The requirement of the extraction function is that it gives the same value even when given different encodings of the same value — this is the essential requirement of pairings that e( [a1]P, [a2]P ) = e( [a1*a2]P, P ).

The new scheme can be expressed, at a high level, in the above way.  There is an “encoding” process, that enables one to generate an encoding of a random element.  We stress again that this is not encryption, in exactly the same way that computing [a]P on an elliptic curve is not encryption of the integer a.  Actually, the analogy with discrete logs already breaks down here: the encoding of a ring element is just multiplication by a fixed public element, so the “discrete log problem” is easily solved by division in the ring.  This weakness is fixed by adding some random “encodings of zero” to hide the ring element. For the n-multi-linear map, one then uses a homomorphic property of multiplication of encodings to compute an encoding of the product.  This is very similar in flavour to recent homomorphic encryption schemes. The crucial new idea is that the public key contains a special element called p_{zt}. This element enables anyone to compute some function of the product from its encoding (in other words, it is a bit like a proxy decryption key).  This process is called “extraction”.  Furthermore, this gadget only works to a certain depth (number of multiplications) and can’t be used to extract information from a product of more than n terms. It is important to understand that extraction is not the reverse operation of decoding — information is lost by the extraction process.

One can use this multi-linear map to achieve a one-round n-party (unauthenticated) Diffie-Hellman key exchange.  One first sets up an (n-1)-multi-linear public key.  The n users then choose random elements ai and publish encodings of them.  A user who receives all the other player’s encodings can multiply one of them by their own element, and then compute the product of them all, and then apply the extraction function to get a session key.  All players will compute the same session key using their inputs.  An eavesdropper needs to compute the n-multi-linear map from all the n encodings. The eavesdropper can indeed compute an encoding of the product of all n values, but the special element p_{zt} only extracts correct information for products of (n-1) encodings. Hence the eavesdropper has no information.

I won’t try to give a description of the scheme.  It suffices to say that it is based on the ring Z_q[x]/(x^{2^n} + 1), as used in NTRU and Ring-LWE. The scheme is somehow motivated by standard techniques in homomorphic encryption using lattices, but it is not identical to any existing scheme. The paper is reasonably clear, especially if one jumps directly to section 4 and ignores the general definition of “graded encodings” in section 2.2.  The scheme relies on a new computational assumption, and the paper contains a great deal of discussion of it.  

The paper does not state any explicit parameters, but it seems that the scheme will be quite practical.  Certainly it should be much more practical for small n than general homomorphic encryption, since it only requires computing a product of n terms.  (In other words, there is no bootstrapping required.)

The paper also gives an asymmetric case, which is analogous to pairings on G1 x G2 x . . . x Gn. The SXDH problem makes sense and seems to be hard in this setting. Of course, more research will be needed to evaluate these assumptions.

I now mention some crucial differences between this new proposal and the pairings case:

1. The scheme does not perform any role like “transforming the DLP from one group to another”.  This is because the extraction function does not seem to have any algebraic properties. The point is that the “pairing computation” is replaced by two components. The first component is multiplication in a homomorphic encryption scheme, and so is a map with algebraic properties. The second component is applying an extractor to some high order bits of some ring elements, and is not an algebraic map.

2. The scheme requires a trusted generator to compute the public values. This entity knows a master secret that allows them to decode all ciphertexts/encodings. Interestingly, this means the scheme is somewhat like a “trapdoor discrete logarithm” system with a pairing.  It is possible that this extra functionality will have some new applications, but it could also be a serious problem for some other applications.

3. There is a small chance that extraction does not behave correctly (due to the small additive errors in the encoding).  However, the paper claims that this can be made negligible.

   — Steven Galbraith