Courbes Hyperelliptiques : Isogénies et Comptage – CHIC

This project aims at providing the study of the Jacobians of small genus curves over finite fields with a rich algorithmic toolbox, in order to promote the use of these curves for cryptography. In particular, the improvements sought will be organized around efficient arithmetic and efficient point counting. As a result, we would obtain a new family of cryptosystems comparing favorably to elliptic curves, with the same level of security and equal or improved performance. The project will be divided in four main tasks. The first task will concentrate on arithmetic aspects of Jacobians of genus 2 curves. The third and fourth task will respectively focus on point counting algorithms for arbitrary genus 2 curves over prime fields, and approaches for building special curves such as those with complex or real multiplication. Such curves are built together with information on their group order. The second task of the project will handle construction of explicit isogenies between general abelian varieties ; the outcome of this second task will be of prime importance to the success of the third and fourth task. Our approach to the different tasks of the project will combine theoretical analysis and computational experimentation or verification of the methods developed, in line with the methodology used by the project partners for their existing work. Task 1: The arithmetic of genus 2 curves and their Jacobian. The main goal of this part is to find new representations for the Jacobian of genus 2 curves with very efficient group law formulas. This has recently been done with success for elliptic curves thanks to the Edwards form. Several lines of research could be pursued in that direction. One idea is to use the formalism of theta functions in order to obtain efficient formulas. This could be seen as a generalisation of the Edwards model, which can also be formulated using theta functions. Another interesting point would be to obtain a genus 2 model with unified formulas, which would have the particular advantage of thwarting side-channel attacks. Pairing-based cryptography could also appear as an application of efficient arithmetic, insofar as the Kummer surface representation is likely to provide speed-ups in the context of pairings. Task 2: Isogeny computation between general abelian varieties. There exist formulas due to V?u to compute isogenies between elliptic curves given in their Weierstrass model. V?u's formulas can be obtained using some simple techniques of geometric invariant theory and the canonical characterisation of the coordinate system of the Weierstrass model of an elliptic curve. Using theta functions, we plan to generalise this approach in order to compute isogenies between general abelian varieties. While some theoretical results exist in this direction, no approach is effective enough at the present time. Task 3: General point counting algorithms over prime fields. There exists a higher genus adaption of the polynomial time point counting algorithm of Schoof due to Pila. The main improvements of Schoof's algorithm in genus 1, which are due to Elkies and Atkin, are presently lacking in genus 2. We intend to obtain analogues of the Elkies-Atkin improvements, using the methods obtained above for constructing explicit isogeny, together with their kernel. Some approaches led to results for (2,2)-isogenies, notably the generalisation of the Richelot correspondence, as well as the use of the Riemann duplication formulas arising from theta functions. Extension of the latter approach could yield interesting result if some efficiency stumbling blocks are overcome. Task 4: Special curves and point counting. The preceding tasks concern algorithms for generic curves, however, special curves play an important role in cryptography. In particular we focus on curves with complex multiplication (CM), families with real multiplication (RM), and twists of curves with large automorphism group. We intend to extend the 2-adic and 3-adic CM methods to other primes and investigate improvements to the complex analytic CM constructions, as well as higher dimensional CRT analogues, for which the main component will be to generalise the thesis work of Kohel to higher genus curves, exploiting explicit isogeny computations. We will also exploit recent developments on RM curves. Besides explicit endomorphism ring computations which have an application for CM methods, RM curves also provide shortcuts for point counting algorithms. Following this last idea, for fixed small real discriminant, we expect to develop a semi-generic random cryptographic curve selection. Lastly, curves having a large geometric automorphism group are a potentially interesting area. Curves C/k whose Jacobian decomposes over a proper extension of k may be suitable for use in cryptography. Using twists of these curves is likely to provide efficient constructions for cryptography.