ECDLP in less than square-root time

As an apology for my “April Fool’s” blog post, I thought I would present a summary of what is known about algorithms for ECDLP that run in asymptotic time less than the square-root time of Pollard rho.

Let q = p^n and let E be an elliptic curve over \mathbb{F}_q. One can solve the ECDLP in E( \mathbb{F}_q ) in O( \sqrt{q} ) = O( p^{n/2} ) group operations. With large storage this is deterministic and rigorous (baby-step-giant-step algorithm), but requires O( \sqrt{q} ) = O( p^{n/2} ) group elements of storage. With Pollard rho the algorithm is randomised and the running time claim is heuristic and average-case, but the storage is low.

Can we do better?

The rest of this article lists some approaches that give ECDLP algorithms with running time better than O( \sqrt{q} ) group operations. None of these results are new, and most of them are very well known. None of them have any impact on currently used elliptic curve cryptosystems, so please do not panic. Full details and references can be found in a recent survey paper I wrote with Pierrick Gaudry.

  1. One can always “unbalance” the baby-step-giant-step algorithm. By using O(M) precomputation and storage one can solve an instance of the ECDLP in an “online” time of O( q/M ) group operations. For example, taking M = q^{2/3} we have an algorithm that solves each individual instance of the ECDLP in O( q^{1/3} ) group operations.

    This approach is usually completely impractical, especially due to the storage requirement. But the concept can make sense if one is going to be solving a very large number of instances of the ECDLP in the same (relatively small) group, and it demonstrates that the O( \sqrt{q} ) bound is not absolute.

  2. A similar idea can be done for Pollard rho. The precomputation is still enormous, but at least the storage stays small. Bernstein and Lange have analysed this approach (see the papers Computing small discrete logarithms faster and Non-uniform cracks in the concrete). Bernstein and Lange explain that with O( q^{2/3} ) precomputation one has can solve individual ECDLP instances in O( q^{1/3} ) group operations.

    Again, for practical applications this is not necessarily a serious concern. But in systems where many users work in the same group one should be careful to set security levels that take into account such a scenario (for example, recall the Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice paper, which has too many authors to write down here).

  3. Brown-Gallant and Cheon have considered variants of the ECDLP where one is given P, aP, a^dP where P is a point of order r and d \mid (r-1). (I assume that r \approx q.) They show one can solve this variant of the ECDLP (i.e., compute a) in O( \max\{ \sqrt{r/d}, \sqrt{d} \} ) group operations. Taking d \approx \sqrt{r} gives an algorithm with O( r^{1/4} ) group operations. There are also algorithms for the case when d \mid (r+1), but they need more intermediate group elements.

    These methods require that r \pm 1 has a factor of the appropriate size and that auxiliary points such as a^d P are available. Hence, these methods are not a threat to elliptic curve cryptosystems as presently used.

  4. Semaev introduced summation polynomials in 2004. Gaudry and Diem were quick to realise that they could be combined with Weil descent. Gaudry focussed on the case of E( \mathbb{F}_{p^n} ) where n is fixed and p goes to infinity. His approach, combined with a “double-large-prime” strategy leads to an algorithm with running time O( p^{2 - 2/n} ) operations (ignoring log terms). The constant in the running time depends exponentially (at least) in n.

    Taking n = 3 we have an algorithm with running time O( p^{1.333} ) operations, which is better than the O( p^{1.5} ) operations of Pollard rho, and the gap grows as n grows. Hence, it is well known that one can beat Pollard rho for curves over such fields, at least asymptotically. Due to this algorithm, elliptic curves E( \mathbb{F}_{p^n} ) for “intermediate” values of n are no longer used for elliptic curve cryptography.

    Returning to my recent hoax: Is there a O( q^{1/24} ) ECDLP algorithm? Yes indeed: When n \ge 47 then the running time of Gaudry’s algorithm on E( \mathbb{F}_{p^n} ) is asymptotically better than O( p^{n/24} ). But the constants are terrible and I am confident that no-one is ever going to perform an experiment of Gaudry’s algorithm in E( \mathbb{F}_{p^{47}} ) that beats Pollard rho. I also remark that such curves have never been suggested for ECC in practice.

    Diem showed an even stronger result: that there are families of finite fields \mathbb{F}_{p^n} for which the ECDLP is subexponential time. But there are no practical implications of this method to elliptic curve cryptosystems.

  5. Several recent papers have suggested improved results for ECDLP on elliptic curves over extension fields. These methods are all based on summation polynomials.

    The papers about ECDLP in characteristic two have been discussed in these two blog posts. These ideas potentially give some speedups to the summation polynomial algorithms, but there is currently little theoretical or experimental evidence to support these claims. The methods do not apply to elliptic curves over prime fields.

    Most recently, the paper Algebraic approaches for the Elliptic Curve Discrete Logarithm Problem over prime fields by Christophe Petit, Michiel Kosters and Ange Messeng was published at PKC 2016. This paper has some interesting and original ideas, and it does apply to elliptic curves over prime fields. But there seem to be no serious implications at present for the use of elliptic curves in practice. From a theoretical point of view, the method is unlikely to perform as well as the methods for characterstic 2 fields (of prime degree), and those methods have not been established yet to beat Pollard rho, so there is currently no evidence that the method in the PKC 2016 paper can beat Pollard rho either. Table 4 of the Petit-Kosters-Messeng paper reports on experiments: the new algorithm solves the ECDLP over a 22-bit finite field in around 5000 seconds, compared with Magma’s implementation of baby-step-giant-step which solves the same problem in 0.01 seconds.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

ECDLP is not broken in 24-th root time

In case anyone has not figured it out, yesterday’s blog post was an April fool’s day hoax. The mathematical arguments written in the blog post make absolutely no sense at all.

Normal service is now resumed. Ellipticnews will continue to be the most reliable news source on the internet for information about new results on the ECDLP.

— Steven Galbraith, April 2 (New Zealand time)

Posted in Uncategorized | 1 Comment

ECDLP can be solved in 24-th root time

We report breaking news of an O( q^{1/24} ) time algorithm for the ECDLP in any elliptic curve E( F_q ). While still exponential complexity, this result will require a major increase in parameter for elliptic curve cryptosystems.

Full details are yet to be released, but the main idea is to exploit recent work by
Maryna Viazovska on sphere packings.

Her work on the 8-dimensional packing seems to lead to an O( q^{1/8} ) algorithm, which would already require a major change in elliptic curve key sizes. But her new joint work with Cohn, Kumar, Miller and Radchenko on sphere packings in dimension 24 gives a much stronger result. As a result we recommend increasing elliptic curve key sizes from 256 bits to 3072 bits.

The method is an index calculus approach. The factor base is chosen by combining two standard results:

  1. The connection between the elliptic curve discrete logarithm problem and the minimal distance of an elliptic codes, and sphere packings (see for example
    this blog post.

  2. The connection between minimal distances of codes and sphere packings.

The decomposition algorithm for the factor base therefore gets translated to a sphere packing problem in 24 dimensions, now solved by Viazovska and her collaborators.

More details to follow. Watch this space.

— Steven Galbraith, April 1, 2016.

Posted in Uncategorized | 2 Comments

eprint 2016/003 by Nicolas Courtois

Nicolas Courtois has posted the paper On Splitting a Point with Summation Polynomials in Binary Elliptic Curves on eprint. The original paper is from January 3rd, but it was updated on January 4 and again on January 5. Probably there will be further updates in the future.

The paper ends with the strong statement “Our conjecture is however that there exists an algorithm for solving the full DL problem on binary elliptic curves with running time of order of 2^{n/3}.”

The context of the paper is index calculus algorithms for the ECDLP. The basic problem in these algorithms is writing an arbitrary point R as a sum P_1 + \cdots + P_k of points that all lie in some “factor base”. This is sometimes called “splitting” a point or “decomposing” a point. The recent work in this area, as summarised in these blog posts, is based on Semaev’s summation polynomials, Weil descent, and Groebner basis algorithms. A problem with this approach is that it is very hard to determine the asymptotic running time of the Groebner basis algorithms, in part because the memory costs are enormous.

This idea does not apply to elliptic curves over prime fields \mathbb{F}_p, and the security of these curves is not affected by any work in this area. For elliptic curves over extension fields \mathbb{F}_{p^n}, for certain values of n, this approach can definitely lead to a faster algorithm than Pollard rho.
However one particularly awkward case is elliptic curves over \mathbb{F}_{2^n} where n is prime, and it is still an open question whether the ECDLP can be solved faster than Pollard rho for such curves. The situation was recently surveyed by Pierrick Gaudry and myself.

Rather than using Groebner basis methods, Nicolas Courtois considers a different approach to solving the point decomposition problem. His approach combines exhaustive search with solving linear equations. To demonstrate the applicability of this idea he gives methods to decompose points as a sum of 2 or 3 points. I have not had time to check the technical parts of the paper in detail yet, but the methods seem to be practical and do not require very large amounts of memory. This work gives insight into the potential for such techniques as part of an index calculus algorithm, and it will be very interesting to see how these ideas develop for decompositions into sums of 4 or more points.

The proposed decomposition algorithms all run in exponential time (e.g., 2^{n/3} steps). It is not immediately clear (to me anyway) that the problem of decomposing a point into a sum of 2 or 3 points should be hard. There is not a direct relationship between point decomposition and ECDLP. For example, if one is given an ECDLP oracle then I don’t see how to use it to solve point decomposition efficiently. So ECDLP could be easy and yet point decomposition hard. On the other hand, decomposing a point as a sum of two points in a factor base of size 2^{n/2} could be polynomial-time and yet, due to the size of the factor base and the cost of the linear algebra stage, the index calculus algorithm would still be slower than Pollard rho.

The paper makes two claims as a consequence of the decomposition algorithms:

  1. Violation of the ideal group model for binary curves.

    The author suggests that his results already show that elliptic curves do not behave like “ideal groups”. In my opinion, it is unclear how to formalise the point decomposition problem in terms of generic algorithms. I tend to think of the generic group model as a “representation independent” model. A generic algorithm has access to group operations and nothing more. A factor base is not a “generic” object, as it depends on the representation. So I am not sure that this comment really has any meaning.

  2. Conjecture of a cube-root-time algorithm for ECDLP on binary elliptic curves.

    It would be very interesting if this claim is true, and I look forward to the future research on this topic. It is certainly an important and interesting problem to consider new approaches to the point decomposition problem.

    At the moment however, there is no evidence to support the claim. The January 5 version of the paper has three decomposition methods.
    The first decomposes to points in a factor base of size 2^{n/2} and so an index calculus algorithm based on this method would have storage cost proportional to 2^{n/2} and be slower than baby-step-giant-step and Pollard rho.
    The second method decomposes in time O( 2^{n/3} ) into a sum of three points in a factor base of size 2^{n/3}. Since we need O( 2^{n/3} ) relations we need to perform the decomposition method O( 2^{n/3} ) times, giving a total complexity of O( 2^{2n/3} ) to solve an instance of the ECDLP, which is worse than Pollard rho.
    The final proposal is an algorithm to decompose a point as a sum of two points in a factor base of size 2^{n/3} and again the decomposition takes time O( 2^{n/3} ), giving an algorithm to solve ECDLP with time O( 2^{2n/3} ).

I conclude by re-stating that it is an important and interesting problem to consider algorithms for the point decomposition problem that are not based on Groebner basis method. The new ideas by Courtois are to be welcomed, and I look forward to future work on this problem.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

Asiacrypt 2015, Auckland, New Zealand

I am the most biased person to write a review of this event, since I was the general chair. But I thought I would write some comments.

The event began on Sunday November 29 with a Maori welcome ceremony at the University Marae. The conference participants were given a powerful oration (in the Maori language) by the kaikorero Te Aroha Morehu (Ngati Whatua Orakei). Christian Cachin then gave some remarks on behalf of the Manuhiri (visitors) after which I got to Hongi (touch noses) with everyone.

The conference consisted of 3 invited lectures and 64 contributed papers. The first invited talk was by Masa Abe and it was on “Structure-Preserving Cryptography”. This is a branch on pairing-based cryptography, where all objects in a cryptosystem are required to be elements of the same group. The second talk was by Gilles Barthe and it was about “Computer-Aided Cryptography”, which means using automated tools to verify the correctness and security of cryptographic protocols and implementations. The final invited lecture was Phil Rogaway’s IACR Distinguished Lecture on the “Moral Character of Cryptographic Work”. This was a bold and challenging talk, presented with great conviction. A more detailed summary can be found here or by reading Phil’s article on eprint.

Slides of the invited lectures are here. A video of Phil Rogaway’s lecture is also on that page, and audio recordings will be put online eventually.

The rump session was chaired by Nigel Smart. Pierre Karpman gave the funniest talk at the rump session, giving him the great honour of being invited to submit a paper to both the Journal of Cryptology and the Journal of Craptology from the same conference.

The best paper award went to “Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance” by Shi Bai, Adeline Langlois, Tancrède Lepoint, Damien Stehlé and Ron Steinfeld. This paper explains that the Renyi Divergence is a general tool that can be used instead of statistical distance in many security proofs.

The paper of most direct relevance to elliptic curve cryptography was “FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime”, presented by Craig Costello (joint work with Patrick Longa). The paper reports a very fast implementation of elliptic curve scalar multiplication using a curve over GF( p^2 ) for p = 2^{127} - 1 based on 4-dimensional GLV/GLS arithmetic.

I also enjoyed the talk by Sanjit Chatterjee on “Type 2 Structure-Preserving Signature Schemes Revisited” (joint with Alfred Menezes) which explained how some papers make incorrect claims of efficiency by treating Type 2 pairings too abstractly. Taechan Kim’s paper “Multiple Discrete Logarithm Problems with Auxiliary Inputs” was about using Cheon-type algorithms in the presence of multiple instances of the DLP. Aurore Guillevic’s paper “Computing Individual Discrete Logarithms Faster in GF(p^n) with the NFS-DL Algorithm” was about improving the individual DLP stage for finite field discrete logarithms coming from pairing-based cryptography.

During the free afternoon there was a boat trip to Rangitoto Island (a 600-year old dormant volcano) and a climb to the summit and crater. The conference banquet was held at the Pullman Hotel with entertainment by a troupe of Cook Island drummers and dancers.

Following the conference, on Friday December 4, were two satellite meetings. One, sponsored by Intel, was on real-world crypto. The other was on lattice crypto and multilinear maps (read this blog post for more details of that meeting).

— Steven Galbraith

Posted in Uncategorized | Leave a comment

ECC 2015, Bordeaux, France, September 28-30, 2015.

The conference took place at the University of Bordeaux, preceded by a well-attended summer school.

Slides of talks are available on the conference website .

The main conference began on Monday 28th. The first three talks were notable for being about finite field discrete logs (rather than elliptic curves).

Nadia Heninger (presenting joint work with a zillion authors) discussed the usage of finite fields for Diffie-Hellman key exchange in internet protocols such as TLS and IKE. By scanning the internet the researchers found a large number of servers that supported 512-bit “export level” keys. They also identified primes that were shared by a large number of servers. It therefore makes sense to attack such primes using the Number Field Sieve DLP algorithm. Their experiments using CADO-NFS showed that, once the precomputation is completed, individual dlogs can be solved in 70 seconds. This allows practical attacks on supposedly secure internet sessions. The talk discussed “downgrade” attacks (forcing servers to use smaller keys which can then be broken). Blame was laid upon US government export controls from the 1990s and the lack of knowledge by security practitioners about DLP algorithms. For more information see https://weakdh.org/

Aurore Guillevic talked about solving the DLP in finite fields F_{p^n} coming from pairing applications, in particular fields coming from polynomial families like MNT and BN curves. The focus is on the “individual discrete logarithm” step. This work will appear at Asiacrypt.

Cecile Pierrot presented joint work with Antoine Joux about the DLP in medium characteristic finite fields. The talk covered two techniques: (1) combining the Multiple Number Field Sieve and the Conjugation approach; (2) a way to accommodate some non-sparse columns in the (block) Wiedemann method.

I gave a survey of ECDLP algorithms, focussing on open problems in the baby-step-giant-step algorithm and summation polynomials. In case there is any confusion: elliptic curves in characteristic 2 are not broken; Pollard rho is still the fastest algorithm for elliptic curves over F_{2^n} where n is prime.

Michiel Kosters discussed summation polynomial attacks on the ECDLP. He explained the work of his three papers on arxiv.

Kim Laine talked about Diem’s algorithm for the DLP on plane quartic curves, with particular focus on how to implement the two-large-prime variant using a graph. He presented a way to build up the factor base together with relations of the desired type, and discussed the massive storage requirements.

There was a reception followed by a rump session.

Tuesday September 29:

Enea Milio talked about “Computation of modular polynomials in dimension 2”. Modular polynomials are a fundamental tool for elliptic curves with many computational applications. A long-standing problem is to get similar techniques for abelian varieties of dimension 2 (Jacobians of hyperelliptic curves). The rather technical talk reported progress on this problem. Most interesting was the introduction of modular polynomials for cyclic subgroups of prime order p, compared with the usual situation of subgroups order p^2. But these are only for some very special curves with real multiplication

There were then two talks about computational problems in lattice cryptography. Leo Ducas presented his paper with Cramer, Peikert and Regev about the ideas of Bernstein and Campbell-Groves-Shepherd for computing short generators of principal ideals by decoding in the log-unit lattice. The talk was illustrated with some beautiful images. Then Katherine Stange talked about work of Eisentrager-Hallgren-Lauter, Elias-Lauter-Ozman-Stange and Chen-Lauter about an attack on a variant of Ring-LWE called Poly-LWE (meaning the errors are chosen using the polynomial basis rather than the canonical embedding representation).

Peter Schwabe gave a stimulating talk about the problem of using automated tools to prove the correctness and security of crypto software. He demonstrated how the valgrind profiling tool can be used on real crypto code, but emphasised that such tools create a massive overhead for software developers.

Michael Hamburg discussed some simple implementation tricks for ECC that are useful to obtain efficient and secure systems.

The last event of the day was a panel discussion about standardisation. The panel was chaired by Ben Smith. The panellists were: Daniel Bernstein, Joppe Bos, Jean-Pierre Flori, Michael Hamburg, Manfred Lochter, Dustin Moody.

Panel

The first question was about people’s experience with the recent IETF, and the on-going NIST, processes.

DB: IETF looks at what is being done and tries to standardise and improve. NIST doesn’t necessarily start from current systems, and so it is less clear where it will end up.

JB: Things could have been better with IETF. It would have been better if more academics were involved. It is an important decision, so want more involvement from industry and academia. It would be good to have backward compatibility (to earlier standards) when the NIST standard is introduced.

JPF: The ECC standard process was quite different to the competition process used to choose AES and the SHA3 hash function.

MH: IETF was an exercise in exhaustion.

ML: IETF was very emotional, and scientists were turned-away from participating. I believe this is a bad thing. Academia should participate since they are the experts. Germany likes to follow international standards. SHA3 hash competition was very helpful. Advice to conference attendees: participate and follow the process.

DM: NIST won’t be doing something like AES/SHA3 for the ECC process. Right now NIST is getting lots of feedback. In the next week or two there will be a request for comments from the public. There is likely to be another workshop to discuss requirements and criteria.

Ben then asked about the timeframe/lifetime of standards?

DM: Standards should be reviewed every 5 years or so. Standard curves should last a long time.

ML: NSA has recently announced new policy for post-quantum crypto. We should not change too much about ECC. Instead, we should move to standardise post-quantum crypto. All these processes are very slow. It takes years for Academic results to feed into standards, and then years for standards to feed into software. Maybe the main issue is not standards, but keeping software up to date.

MH: Depends on whether quantum computer is built. If not, standard should last 20-30 years.

JB: Shouldn’t be revising standards too often. I’m a big fan of crypto agility. Would be nice to support a family of curves. It would be good to have a common framework where most things stay the same and can plug-in new parameters if need to change.

DB: If crypto is working then shouldn’t touch it. If the old standard is working fine then don’t use the new standard. If you want to distract people then best thing you can do is have a whole bunch of standards. How many crypto standards are there? No-body can review security and support on many platforms. Best thing is to limit number of standards. Problem: most things aren’t working and the internet is mostly not secure. Need to do what it takes to get security. We should figure out why the current standards are not doing the job and fix them. If a new standard is not doing the job then fix it.

BS: What tools do we need to check that we are adhering to standards? What tools to develop right standards in the first place?

DB: Peter Schwabe talked about this, e.g., formal verfication. There are a ton of problems to be solved.

JB: Peter’s talk was interesting and such tools would be very helpful. More traditional testing is still valid. It would be good to have a database of test cases.

JPF: Many people don’t trust NIST curves. How many people verified the curve generation? Open source tools would be nice.

MH: It is very difficult to make a set of test vectors without knowing the special cases in the implementation, so formal verification more appropriate.

ML: Peter’s talk was great. There are many other side-channel attacks than timing. One solution may be optimal on one platform but not on others. So need flexibility. Not only correctness of implementation but also physical errors and fault injection. So absolutely necessary to test points before and after operations.

DM: I agree with need for tools. The more eyes looking over a standard the better. Regarding earlier point: NIST has verfied the curve generation process. We believe the NIST curves are secure despite concerns about their provenance. But NIST is open to new curves as well.

Ben asked if there are any theorems that can help?

MH: If you have a set of formulas for some elliptic curve process, put them into Groebner basis algorithms and prove the formula in an automated fashion. It would be nice if there were an automated way to prove that formulas are complete.

DB: Anyone doing formulas — do sage scripts and make them public online. So people can run them for themselves. This would minimise number of typos etc.

JB: When using side-channel countermeasures, such as dedicated formulas and large precomputed tables of points etc, not many people have looked at the counter cases and proved things about them.

ML: There are dozens or hundreds of implementations of ECC. To avoid patents companies choose their own implementations. When one cryptanalyses them then one runs into all sorts of mathematical problems, e.g., lattice problems or statistics. Need tools to extract secret from the data coming from side-channels etc.

Panellists were asked about the NSA announcement that users should consider moving to post-quantum crypto.

DB: We’ve been saying for more than 10 years that quantum computers are coming and we need to be prepared. Nice that NSA finally understands that message. But the details are really puzzling. Suite B lowest security was 384 bits ECC, and other gigantic security levels. Now it has 3000-bit RSA, which we know is breakable in like 2^{128} operations. I am puzzled by the details. Everyone I have talked to at NSA said “we didn’t see this in advance”.

JB: Puzzling announcement, especially the timing during the NIST ECC standard process. In my opinion it is premature to consider post-quantum systems, as lots more work is needed on post-quantum crypto.

MH: The NSA is concerned with 50-year security. Highest assurance data should consider quantum computing a threat. I also don’t know why 3072-bit RSA — is it for people who were thinking to move to ECC? You should be implementing elliptic curves. If you are worried about quantum computers in 10 years then build with ECC + post-quantum perhaps. Signatures less a concern. Adding post-quantum key-exchange a good idea.

ML: If NSA says it then we take it seriously. For top secret information, 30 years is the regulation, and it can be extended a further 30 years. Health data and voting information have unlimited lifetime. One case where quantum-secure systems are mandated is satellite communications. We are using Merkle signatures. I don’t see a mature post-quantum systems.

DM: NSA knows transitions are painful. It is very surprising all the details they didn’t say. It was surprising to the NSA guys I know. They also don’t know where it came from. I’m confident NSA still believe in the security of ECC, but NIST is also working on post-quantum crypto. NSA has been less engaged than usual in curve selection process this time.

Ben asks if standards can give a false sense of security.

DB: I prefer a de-centralised approach, where implementors do good work that becomes a de-facto standard. If it isn’t what the devices are using then it is not a useful standard.

JB: We (NXP) have to follow standards. We go to evaluation labs who do a lot of testing and they try to break it in physical ways. I guess a lot of software implementations do not follow standards.

JPF: Standards make it easier to help people not to make mistakes. We need better education of implementors.

MH: Try to make sure the entire crypto in the system is secure. Too often someone has a product with “military grade security AES”, but have not considered buffer overruns and side-channels etc. Often using AES in an insecure way. Need to find some way to get better quality.

DM: Better off with standards than without them.

ML: Companies have lifecycle management. But with open source people come along and add things. Then you start to find bugs. Can’t blame it on standards. Blame it on process. I don’t know how to mitigate that. Common criteria require evaluation lab testing.

DB: You CAN blame the standard. It can be too complicated and encourage implementors to have to deal with things that are likely to go wrong. Current NIST ECC standards allow, for example, invalid curve attacks thanks to choices of elliptic curves. It is hard to tell the difference between an implementation that follows the standard and one that doesn’t. This leads to major security problems. We know how to fix this at the standardisation level.

DB: Not enough to ask for more academics to be involved in the standardisation process. An example of a scientist in the standardisation process is Ron Rivest in 1990s. Rivest in 1992 sent several pages of comments stating “This standard has enough rope for the user to hang himself, which is not something a standard should do”. The expert said the standard was not good enough, but it turned out NSA was behind DSA and it got standardised. So it is not clear that expert opinion will help.

JB: Standards can be simplified, and this is a good thing. But don’t want a situation where everyone is expected to write crypto. Crypto should be done by crypto experts. Blame people over-extending their expertise.

Ben asked about the difference between hardware/commercial software/open source.

JB: Implementation on servers is a different security model than smart cards. So leads to different requirements and different decisions about curves. Should try to find balance. A list of requirements at the start might be a better idea.

JPF: Different needs. So maybe different curves?

ML: If you want to read the BSI position then read our requirements document on the web.

DM: The NIST position is not too many curves. Originally there were 15, and not many are being used. If software/hardware need different curves then we will support that.

We then all crossed the river for a fine conference dinner at Cafe du Port.

Wednesday 30

The conference ended with three talks. Christian Grothoff talked about rebuilding the internet on secure foundations. Arnaud Tisserand talked about general purpose and open-source Hardware accelerators for ECC and HECC. Juliane Krämer gave a very clear talk about Fault Attacks on Pairing-Based Cryptography (in particular, glitch attacks, which seem to be very powerful).

Andreas Enge, Damien Robert and their team are to be thanked for an excellent conference.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

NIST workshop and Chinese mirror site

For discussion of what took place at the NIST workshop see these threads on the curves@moderncrypto mailing list:

Readers may also be interested to know that this blog now has an offical mirror site in China since wordpress is not accessible there.

— Steven Galbraith

Posted in Uncategorized | Leave a comment