CHIC Project

Home     Presentation     Archives

Pierrick Gaudry

A curve!

I am pleased to announce that the curve "11,-22,-19,-3" (from the name of the coefficients of its associated Kummer surface) over GF(2^^127-1) has a Jacobian the order of which is 16 times a prime number, as well as its quadratic twist, which is optimal given that the square of the theta null vales are rational.

Its equation is y2 = 81689052950067229064357938692912969725 + 9855732443590990513334918966847277222 * x + 154735094972565041023366918099598639851 * x2 + 76637216448498510246042731975843417626 * x3 + 64408548613810695909971240431892164827 * x4 + x5

The characteristic polynomial of the Frobenius morphism is T4 - s1*T3 + s2*T2 - s1*p*T + p2, with s1 = -7393453752833430168 s2 = -58693655204203573205502023766223379410 which gives the cardinality: 28948022309329048857150677223539304343060898790394936937146761976741707621424 and 28948022309329048854634815280804649582776141498175061009244276764818874016816

This curve has been obtained by counting the points of all the curves such that their associated Kummer surface has small coefficients, based upon an aggressive early-abort strategy which stop the computations as soon as a big factor is detected on one side or the other.

This curve provides about the same security as AES-128. The arithmetic on GF(2127-1) is relatively easy : it is not so often that we can use a true Mersenne! and the small coefficients replace some big multiplications by small ones, which allows also to improve slightly.

The fact that we are almost prime on the 2 sides allows to avoid to "check" the points that we have to multiply : to be and the Kummer surface is enough to be secure; it is not necessary to check that we are not on the twist.

In order to count the points, we have been using the same (Schoof-like) method as for our last year record: We have just evolved the process from the prototype level to the industrial application with some ten of thousands of considered curves and 261 curves for which we have completely computed the number of points (we still have some yet to be finished).

The computations have mostly taken place in Canada, on the Sharcnet grid.

With the same sorftware and some reasonable power of computation, we could count the number of points over GF(2192) (size for a security comparable to the second level of AES). It's probable that we are going to it soon. Nonetheless, to reach the level of AES-256, is still science-fiction... we would need explicit isogenies.

Chic-serely, Pierrick (avec Éric Schost)