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.

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.

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: y² + x·y = x³ + a₆ defined over a finite field F_q where q = 2^d.

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

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 j_i simultaneously. Indeed writing out the equations Phi₂(J_i, J_i+1) for 0 <= i < d yields an algebraic system over Z_qwithout Frobenius, which can be solved quickly by a multi-variate Newton iteration.

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

Next for each i we find a curve y² + x·y = x³ + A₆ defined over Z_q and having j-invariant J_i. This is done with an ordinary Newton iteration to compute A₆ to precision O(2ⁿ). 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(2^n-1).

Now, the trace of Frobenius can be written as a norm from Z_q to Z₂ of a certain partial trace. Each triple (J_i, A₆, X) allows us to compute the square of one of the conjugate partial traces, using the formulae of Vélu, to precision O(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(2ⁿ⁺¹), except for its sign. As is well known, c is confined to the interval -2^d/2+1,...,2^d/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).