Research

Current research topics

At ArgoTech we believe that a strong emphasis on novel research will keep us at the leading edge of software technology. We are particularly involved in fast arithmetic algorithms and implementation methods with applications in domains such as cryptography and signal processing. Some highlights are in the particular area of curves and finite field arithmetic:

  • Theoretical work on counting points on elliptic curves.
  • Implementation of the above in our ECPC product. For results at cryptographic sizes and larger “research level” sizes, see immediately below.
  • Note: demos of the above are available.
  • Extension to hyperelliptic curves of genus 2 (pure research!)

ECPC Results

The first version of ECPC was our efficient implementation of the Satoh-FGH algorithm, described below. It sped up the computation of elliptic-curve group sizes by a factor of about 6 (or more for large fields) over what had previously been possible.

ECPC v2 implemented a new (patent-pending) method based on a non-converging AGM iteration, which gained a factor of about 8 in speed, while reducing memory usage to a negligible amount, at least for cryptographic sized curves. ECPC v3 had many internal improvements and used a fast ‘norm’ algorithm to gain another factor of 3 or so in speed.

The current version is ECPC v4 which uses an asymptotically and practically faster algorithm, which gains a factor ranging from 2 or 3 at small sizes up to 30 or more for record sizes.

Table 1: Time for counting one arbitrary curve with ECPC v4.

Size
(bits)
Alpha EV6
750 MHz
Pentium III
1 GHz
163 0.06 sec 0.09 sec
197 0.09 sec 0.15 sec
239 0.13 sec 0.22 sec
283 0.29 sec 0.46 sec
409 0.70 sec 1.17 sec
571 1.74 sec 3.25 sec
1000 5.91 sec 11.17 sec

ECPC can be used for cryptographic key generation. The following table describes the runtime for curves used in elliptic-curve cryptography using v3. For instance a secure 163-bit curve can be generated in 2 seconds on average by trying about 70 random curves, filtering out ¾’s of them using an early-abort strategy and counting the remaining ones to find those whose number of points is twice a prime. The resulting ECC key is roughly as secure as a 1000-bit RSA key.

Table 2: Secure curve generation times
WARNING: ECPC v4 times not yet available.

Size
(bits)
Alpha EV6
750 MHz
163 2 sec
197 5 sec
239 8 sec

For information on record results, please head over to this page.

Technical Description of ECPC v1

Please note: A technical description of the more recent ECPC versions will be available soon!

The following is a brief technical explanation of the Satoh-FGH point-counting algorithm used in ECPC v1. It was designed by Robert Harley at ArgoTech with Gaudry, Fouquet and Morain at the Computer Science Laboratory of École Polytechnique, by extending the ideas reported by Professor Satoh in his preprint [Sat] to apply in characteristic two (and three) as described in [FGH]. We refer to the algorithm as Satoh-FGH to distinguish it from a different extension designed by Berit Skjernaa.


The input to the algorithm is an elliptic curve E: y2 + x·y = x3 + a6 defined over a finite field Fq where q = 2d.

First of all it is necessary to lift the curve E up to a curve defined over a certain 2-adic ring Zq above Fq. Intuitively, Zq is to Fq as the 2-adic integers Z2 are to the 2-element field F2. More precisely, Zq is the unique (unramified) discrete valuation ring having residue field Fq. By a result of Lubin-Serre-Tate, there is a canonical way to lift E by lifting its j-invariant from Fq to Zq using the modular polynomial Phi2. A direct implementation of LST would be slow due to computations of the (rather complicated) Frobenius in Zq.

The remarkable efficiency of the algorithm comes from an insight by Pr. Satoh: rather than lifting j up to J in isolation, it is faster to lift j along with all its conjugates ji simultaneously. Indeed writing out the equations Phi2(Ji, Ji+1) for 0 <= i < d yields an algebraic system over Zqwithout Frobenius, which can be solved quickly by a multi-variate Newton iteration.

The first stage of Satoh-FGH is thus to compute all the Ji‘s to 2-adic precision O(2n) where n = ceiling(d/2)+1.

Next for each i we find a curve y2 + x·y = x3 + A6 defined over Zq and having j-invariant Ji. This is done with an ordinary Newton iteration to compute A6 to precision O(2n). Next for each curve, we find (half of) the X-coordinate of the non-trivial point in the kernel of the dual isogeny of the Frobenius. This is done with another Newton iteration to precision O(2n-1).

Now, the trace of Frobenius can be written as a norm from Zq to Z2 of a certain partial trace. Each triple (Ji, A6, X) allows us to compute the square of one of the conjugate partial traces, using the formulae of Vélu, to precision O(2n+2).

To finish, we compute the product of these conjugates and take a 2-adic square root, yielding the trace c of Frobenius to precision O(2n+1), except for its sign. As is well known, c is confined to the interval -2d/2+1,...,2d/2+1. Since it is necessarily equal to 1 modulo 4, the number of points q+1-c can be determined exactly.

Much more detail may of course be found in the referenced papers. And here is an easy read.

 References

[FGH]:Mireille Fouquet, Pierrick Gaudry, Robert Harley,”An extension of Satoh’s algorithm and its implementation“,Journal of the Ramanujan Mathematical Society,vol. 15, pp. 281-318 (2000).[Sat]:Takakazu Satoh,”The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting“,Journal of the Ramanujan Mathematical Society,vol. 15, pp. 247-270 (2000).