In this bilingual talk, we will describe a new algorithm for small characteristic, especially characteristic two, which is asymptotically and practically the best one discovered to date. In the first half, in French, JFM will present the required theoretical background on lifting elliptic curves and constructing isogenous curves using the AGM iteration and will describe the fast point-counting algorithm based on these ideas. In the second half, in English, RH will explain how to implement the algorithm in practice and will present some results obtained with a very efficient implementation, including an application to dynamic generation of secure curves and a record computation on a 15013-bit curve. Security proofs for systems involving cryptography are getting increasing attention in theory and practice, and they are used for increasingly large systems. Both the cryptographic and the formal-methods community are working on such proofs, and the techniques were so far almost disjoint.
Cryptographic techniques are precise, but also lengthy and error-prone.
We show how to bridge this gap. We do this by extending cryptographic simulatability definitions to reactive systems. Finally we sketch how the approach can be used in the future for an actual link with formal methods.