Dans ma thèse j'etude les variétés abéliennes ordinaires définies avec multiplication réelle maximale. Je définis des polynômes modulaires dans ce situation et je donne un algorithme pour calculer sur les nombres complexes et pour les surfaces sur des corps finis. Je donne aussi un théorème de structure pour les graphs des isogénies dans ce contexte. Je donne une généralisation de Schoof-Elkies-Atkin aux courbes de genre 2 avec multiplication réelle maximale fixe en utilisant les polynômes modulaires. / My thesis looks at ordinary abelian varieties defined with maximal real multiplication. I define modular polynomials in this setting and give an algorithm to compute them over the complex numbers, and for surfaces over finite fields. I also give a structure theorem for isogeny graphs in this setting. I give a generalisation of Schoof-Elkies-Atkin to genus 2 curves with fixed maximal real multiplication using the modular polynomials.

La cryptographie est indispensable aux réseaux de communication modernes afin de garantir la sécurité et l'intégrité des données y transitant. Récemment, des cryptosystèmes efficaces, sûr et riches ont été construits à partir de variétés abéliennes définies sur des corps finis. Cette thèse contribue à plusieurs aspects algorithmiques de ces variétés touchant à leurs anneaux d'endomorphismes. Cette structure joue un rôle capital pour construire des variétés abéliennesmunies de bonnes propriétés, comme des couplages, et nous montrons qu'un plus grand nombre de telles variétés peut être construit qu'on ne pourrait croire. Nous considérons aussi le problème inverse qu'est celui du calcul de l'anneau d'endomorphismes d'une variété abélienne donnée. Les meilleures méthodes connues ne pouvaient précédemment résoudre ce problème qu'en temps exponentiel ; ici, nous concevons plusieurs algorithmes de complexité sous-exponentielle le résolvant dans le cas ordinaire. Pour les courbes elliptiques, nous bornons rigoureusement la complexité de nos algorithmes sous l'hypothèse de Riemann étendue et démontrons qu'ils sont extrêmement efficaces en pratique. Comme sous-routine, nous développons notamment un algorithme sans mémoire pour résoudre une généralisation du problème du sac à dos. Nous généralisons aussi notre méthode aux variétés abélienne de dimension supérieure. Concrètement, nous développons une bibliothèque qui permet d'évaluer des isogénies entre variétés abéliennes ; cet outil nous permet d'appliquer une généralisation de notre méthode à des exemples jusqu'alors incalculables. / Modern communications heavily rely on cryptography to ensure data integrity and privacy. Over the past two decades, very efficient, secure, and featureful cryptographic schemes have been built on top of abelian varieties defined overfinite fields. This thesis contributes to several computational aspects of ordinary abelian varieties related to their endomorphism ring structure. This structure plays a crucial role in the construction of abelian varieties with desirable properties, such as pairings, and we show that more such varieties can be constructed than expected. We also address the inverse problem, that of computing the endomorphism ring of a prescribed abelian variety. Prior state-of-the-art methods could only solve this problem in exponential time, and we design several algorithms of subexponential complexityfor solving it in the ordinary case. For elliptic curves, we rigorously bound the complexity of our algorithms assuming solely the extended Riemann hypothesis, and demonstrate that they are very effective in practice. As a subroutine, we design in particular a memory-less algorithm to solve a generalization of the subset sum problem. We also generalize our method to higher-dimensional abelian varieties. Practically speaking, we develop a library enabling the computation of isogenies between abelian varieties; this building block enables us to apply a generalization of our algorithm to cases that were previously not computable.

Le problème du calcul d'isogénies est apparu dans l'algorithme SEA de comptage de points de courbes elliptiques définies sur des corps finis. L'apparition de nouvelles applications du calcul d'isogénies (crypto système à trappe, fonction de hachage, accélération de la multiplication scalaire, crypto système post quantique) ont motivé par ailleurs la recherche d'algorithmes plus rapides en dehors du contexte SEA. L'algorithme de Couveignes (1996), malgré ses améliorations par De Feo (2011), présente la meilleure complexité en le degré de l'isogénie mais ne peut s'appliquer dans le cas de grande caractéristique.L'objectif de cette thèse est donc de présenter une modification de l'algorithme de Couveignes (1996) utilisable en toute caractéristique avec une complexité en le degré de l'isogénie similaire à celui de Couveignes (1996).L'amélioration de l'algorithme de Couveignes (1996) se fait à travers deux axes: la construction de tours d'extensions de degré $ell$ efficaces pour rendre les opérations plus rapides, à l'image des travaux de De Feo (2011), et la détermination d'ensemble de points d'ordre $ell^k$ stables sous l'action d'isogénies.L'apport majeur de cette thèse est fait sur le second axe pour lequel nous étudions les graphes d'isogénies dans lesquels les points représentent les courbes elliptiques et les arrêtes représentent les isogénies. Nous utilisons pour notre travail les résultats précédents de Kohel (1996), Fouquet et Morain (2001), Miret emph{et al.} (2005,2006,2008), Ionica et Joux (2001). Nous présentons donc dans cette thèse, à l'aide d'une étude de l'action du Frobenius sur les points d'ordre $ell^k$, un nouveau moyen de déterminer les directions dans le graphe (volcan) d'isogénies. / Isogeny computation problem appeared in the SEA algorithm to count the number of points on an elliptic curve defined over a finite field. Algorithms using ideas of Elkies (1998) solved this problem with satisfying results in this context. The appearance of new applications of the isogeny computation problem (trapdoor crypto system, hash function, scalar multiplication acceleration, post quantic crypto system) motivated the search for a faster algorithm outside the SEA context. Couveignes's algorithm (1996) offers the best complexity in the degree of the isogeny but, despite improvements by DeFeo (2011), it proves being unpractical with great characteristic.The aim of this work is to present a modified version of Couveignes's algorithm (1996) that maintains the same complexity in the degree of the isogeny but is practical with any characteristic.Two approaches contribute to the improvement of Couveignes's algorithm (1996) : firstly, the construction of towers of degree $ell$ extensions which are efficient for faster arithmetic operations, as used in the work of De Feo (2011), and secondly, the specification of sets of points of order $ell^k$ that are stable under the action of isogenies.The main contribution of this document is done following the second approach. Our work uses the graph of isogeny where the vertices are elliptic curves and the edges are isogenies. We based our work on the previous results of David Kohel (1996), Fouquet and Morain (2001), Miret emph{& al.} (2005,2006,2008), Ionica and Joux (2001). We therefore present in this document, through the study of the action of the Frobenius endomorphism on points of order $ell^k$, a new way to specify directions in the isogeny graph (volcano).

Cette thèse concerne des propriétés des variétés jacobiennes de courbes de genre 2 qui couvrent des courbes elliptiques. Soit E une courbe plane, donnée par une équation y^2=F(x), où F(x)=x^3+a2x^2+a1x+a0 est un polynôme à coefficients rationnels, qui a trois racines distinctes. Pour des raisons historiques, une telle courbe est appelée courbe elliptique. On sait que toute courbe elliptique E peut être équipée d'une structure de groupe commutatif - on peut additionner et soustraire ses points. Un point O « à l'infini », qui est contenu dans toutes les droites verticales (droites de la forme x=c), est l'élément neutre. Cette structure de groupe est décrite par la condition que trois points P,Q,R sur E satisfont P+Q+R=O si et seulement s'ils sont alignés. Les surfaces avec une structure de groupe commutatif sont appelées abéliennes. Par exemple, un produit de deux courbes elliptiques E1xE2 est une surface abélienne, de façon évidente. Considérons maintenant une courbe plane C donnée par une équation y^2=G(x), où G(x)=x^6+b5x^5+b4x^4+b3x^3+b2x^2+b1x+b0 est un polynôme à coefficients rationnels, qui a six racines distinctes. La courbe C est appelée hyperelliptique et n'a pas de structure de groupe. Par contre, nous pouvons lui associer, d'une façon naturelle, une surface abélienne Jac(C), appelée la jacobienne de C. En plus, nous pouvons plonger C dans Jac(C). Certaines courbes hyperelliptiques sont spéciales car elles couvrent des courbes elliptiques. Par exemple, considérons une courbe C donnée par l'équation y^2=x^6+ax^4+bx^2+c, dans laquelle seulement des puissances paires de x apparaissent. Si (x,y) est un point de cette courbe alors de même (-x,y), et nous pouvons définir une application algébrique f:(x,y)->(x^2,y) de degré 2, c'est-à-dire, de fibre générale à deux points. Alors (X,Y)=(x^2,y) est un point de la courbe elliptique E donnée par Y^2=X^3+aX^2+bX+c et nous disons que C est un revêtement double de E. Si E1 est une courbe elliptique, si C est une courbe hyperelliptique, et si C->E1 est un revêtement de degré n qui n'est pas une composition de revêtements, alors nous pouvons plonger E1 dans la surface Jac(C) comme un sous-groupe. De plus, il existe une autre courbe elliptique E2 et un revêtement C->E2 de degré n, tel que la surface Jac(C) a une propriété spéciale - elle peut être obtenue comme quotient de la surface E1xE2 par un sous-groupe fini. Le chapitre 1 de cette thèse traite les aspects géométriques de cette situation. Nous cherchons à savoir quelles courbes peuvent avoir une telle relation et nous nous concentrons surtout sur les cas n=2 et n=3, qui ont déjà été analysés dans la littérature. Dans le cas général, nous obtenons quelques résultats, mais une description complète s'avère très difficile de manière explicite. Le chapitre 2 traite les aspects arithmétiques de la situation, via la théorie des fonctions hauteurs, qui sont un outil très utile pour répondre à des questions concernant des points rationnels de courbes et surfaces. Pour tout nombre rationnel x=a/b, avec a et b des entiers premiers entre eux, on définit la hauteur h(x) de x, de façon très précise, comme une mesure de sa complexité arithmétique - la hauteur dit approximativement combien de chiffres sont nécessaires pour écrire les entiers a et b. De la même façon, la hauteur d'un point rationnel d'une courbe ou surface nous dit combien de chiffres ont les coordonnées. Par exemple, (3,5) et (1749/1331,-1861/1331) sont deux points rationnels de complexités plutôt différentes de la courbe y^2=x^3-x+1, tandis que (2,√7) n'est pas un point rationnel. Il est possible d'attacher une hauteur aux courbes elliptiques et aux surfaces abéliennes qui mesure leur complexité arithmétique totale. Une relation spécifique entre ces deux notions de hauteur est alors conjecturée et nous étudions cette conjecture dans la situation décrite plus haut. Nous montrons que cette relation est vraie pour E1xE2 si et seulement si elle est vraie pour Jac(C). / This thesis deals with properties of Jacobians of genus two curves that cover elliptic curves. Let E be a curve in the plane, given by an equation y^2=F(x), where F(x)=x^3+a2x^2+a1x+a0 is a polynomial with rational coefficients and with three distinct roots. For historical reasons, such a curve is known as an elliptic curve. It is known that every elliptic curve E can be equipped with a structure of a commutative group - its points can be added and subtracted. A point O "at infinity", which is contained in all vertical lines (lines of form x=c), is the neutral element. This group structure is described by the condition that three points P,Q,R in E satisfy P+Q+R=O if and only if they are collinear. Surfaces with a commutative group structure are called abelian. For example, a product of two elliptic curves E1xE2 is an abelian surface in the obvious way. Next we consider a planar curve C given by an equation y^2=G(x), where G(x)=x^6+b5x^5+b4x^4+b3x^3+b2x^2+b1x+b0 is a polynomial with rational coefficients and six distinct roots. The curve C is called hyperelliptic and it does not have a group structure. However, we can associate to it, in a natural way, an abelian surface Jac(C), called the Jacobian of C. Moreover, we can embed C into it. Some hyperelliptic curves, of the form y^2=G(x) as above, are special because they cover elliptic curves. For example, consider a curve C given by y^2=x^6+ax^4+bx^2+c, so that only even powers of x appear. If (x,y) is a point on this curve then so is (-x,y) and we can define an algebraic map f:(x,y)->(x^2,y), that is of degree 2, i.e. 2-to-1. Now (X,Y)=(x^2,y) is a point on the elliptic curve E given by Y^2=X^3+aX^2+bX+c and we say that C is a double cover of E. If E1 is an elliptic curve, C is a hyperelliptic curve, and C->E1 is an n-to-1 covering that is not a composition of coverings, then we can embed E1 into the surface Jac(C) as a subgroup. Moreover, there exists another elliptic curveE2 and an n-to-1 covering C->E2, such that the surface Jac(C) has a special property - it can be obtained as the quotient of the surface E1xE2 by a finite subgroup. The first chapter of the thesis deals with the geometric aspects of this setup. We investigate which curves can form this special relationship and we focus mostly on the cases n=2 and n=3, which have already been analysed in literature. We also gain some insight into the general case, but a full description proves to be very difficult computationally. The second chapter deals with the arithmetic aspects of the setup, via the theory of height functions, which are a very useful tool in answering questions about rational points on curves and surfaces. For every rational number x=a/b, where a and b are coprime integers, one can define its height h(x), in a very precise way, as a measurement of its arithmetic complexity - the height roughly tells us how many digits are needed to write down the integers a and b. Likewise, the height of a rational point on a curve or surface tells us about the number of digits of the coordinates. For example, (3,5) and (1749/1331,-1861/1331) are two rational points of rather different complexity on the curve y^2=x^3-x+1, while (2,√7) is not a rational point. It is also possible to associate a height to an elliptic curve or an abelian surface and measure its arithmetic complexity as a whole. A specific relation between these two heights is conjectured and we investigate it in the context of the setup above. We show that this relation holds for E1xE2 if and only if it holds for Jac(C).

Most isogeny-based cryptosystems ultimately rely, for their security, on l- IsoPath, i.e. the problem of finding a secret l-smooth isogeny between two elliptic curves. As cryptographic applications usually employ weaker variants of l-IsoPath for practical reasons, it is natural to ask whether these variants are equally hard from a computational perspective. For example, what happens if the endomorphism ring of one of the curves is known? Does the existence of suitable pairings affect the hardness of l-IsoPath? What happens if some non-trivial endomorphisms of the domain and codomain curves are known? These kinds of questions lead to different problems, some of which are considered throughout this thesis. To prevent anyone from knowing the endomorphism ring of a supersingular elliptic curve, we would need a method to hash in the supersingular isogeny graph, i.e. the graph whose vertices are supersingular elliptic curves (up to isomorphism) and whose edges are isogenies of fixed degree. We give examples of cryptographic protocols that could benefit from this and survey some known methods. Since none of them is at the same time efficient and cryptographically secure, we also point out a few alternative approaches. Later on, we leverage the classic Deuring correspondence between supersingular elliptic curves and quaternion orders to study a weaker version of l-IsoPath, inspired by the study of CM theory from the previous part. We then focus on the construction of pairings of elliptic curves, showing that, in the general case, finding distinct pairings compatible with a secret isogeny is no easier than retrieving the isogeny itself. In the presence of an orientation, on the other hand, we show that the existence of suitable self-pairings, together with a recent attack on the isogeny-based key-exchange SIDH, does lead to efficiently solving l- IsoPath for some class-group-action-based protocols. In particular, we completely characterize the cases in which these selfpairings exist. Finally, we introduce a different graph of elliptic curves, which has not been considered before in isogeny-based cryptography and which does not arise, in fact, from isogenies: the Hessian graph. We give a (still partial) account of its remarkable regularity and discuss potential cryptographic applications.

Progress in the field of quantum computing has shown that, should construction of a sufficiently powerful quantum computer become feasible, much of the cryptography used on the Internet today will be rendered insecure. In lieu of this, several approaches to “quantum-safe” cryptography have been proposed, each one becoming a serious field of study. The youngest of these approaches, isogeny based cryptography, is oriented around problems in algebraic geometry involving a particular variety of elliptic curves. Supersingular isogeny Diffie-Hellman (SIDH) is this subfields main contender for quantum-safe key-exchange. Yoo et al. have provided an isogeny-based signature scheme built on top of SIDH. Currently, cryptographic algorithms in this class are hindered by poor performance metrics and, in the case of the Yoo et al. signature scheme, large communication overhead. In this dissertation we explore two different modifications to the implementation of this signature scheme; one with the intent of improving temporal performance, and another with the intent of reducing signature sizes. We show that our first modification, a mechanism for batching together expensive operations, can offer roughly 8% faster signature signing and verification. Our second modification, an adaptation of the SIDH public key compression technique outlined in [CJL + 17], can reduce Yoo et al. signature sizes from roughly 688λ bytes to 544λ bytes at the 128-bit security level on a 64-bit operating system. We also explore the combination of these techniques, and the potential of employing these techniques in different application settings. Our experiments reveal that isogeny based cryptosystems still have much potential for improved performance metrics. While some practitioners may believe isogeny-based cryptosystems impractical, we show that these systems still have room for improvement, and with continued research can be made more efficient - and eventually practical. Achieving more efficient implementations for quantum-safe algorithms will allow us to make them more accessible. With faster and lower-overhead implementations these primitives can be run on low bandwidth, low spec devices; ensuring that more and more machines can be made resistant to quantum cryptanalysis. / Thesis / Master of Science (MSc)

No description available.

Die fortschreitende Entwicklung immer leistungsstärkerer Quantencomputer bedroht die Informationssicherheit kryptographischer Anwendungen, die auf dem Faktorisierungsproblem oder dem Problem des diskreten Logarithmus beruhen. Die US-amerikanische Standardisierungsbehörde NIST startete 2017 ein Projekt mit dem Ziel, Kryptographiestandards zu entwickeln, die gegen Angriffe von Quantenrechnern resistent sind. Einer der Kandidaten ist SIKE (Supersingular Isogeny Key Encapsulation), der einzige Vertreter isogeniebasierter Kryptographie im Standardisierungsverfahren. Diese Diplomarbeit enthält eine weitgehend in sich abgeschlossene Beschreibung der SIKE-Protokolle, Sicherheitsbetrachtungen sowie eine einfache Implementierung des Kryptosystems.:1. Einleitung 2. Grundlegende Definitionen 2.1. Elliptische Kurven 2.2. Punktaddition 2.3. Montgomery-Kurven 2.4. Isogenien 2.5. Der Diffie-Hellman-Schlüsselaustausch 2.6. Das Elgamal-Kryptosystem 3. Supersingular Isogeny Key Encapsulation 3.1. Supersingular Isogeny Diffie-Hellman Key Exchange 3.2. Erzeugung der Systemparameter 3.3. Erzeugung der Schlüsselpaare 3.4. Berechnung der gemeinsamen Kurve 3.5. Vom Schlüsselaustausch zum Kryptosystem 3.6. Schlüsseleinschluss (Key Encapsulation) 3.7. Implementierungen 4. Sicherheitsbetrachtungen 4.1. Ciphertext indistinguishability 4.2. Größe der Parameter 4.3. Weitere Aspekte 5. Zusammenfassung A. Implementierung

The Signal protocol can be considered state-of-the-art when it comes to secure messaging, but advances in quantum computing stress the importance of finding post-quantum resistant alternatives to its asymmetric cryptographic primitives. The aim is to determine whether existing post-quantum cryptography can be used as a drop-in replacement for the public-key cryptography currently used in the Signal protocol and what the performance trade-offs may be. An implementation of the Signal protocol using commutative supersingular isogeny Diffie-Hellman (CSIDH) key exchange operations in place of elliptic-curve Diffie-Hellman (ECDH) is proposed. The benchmark results on a Samsung Galaxy Note 8 mobile device equipped with a 64-bit Samsung Exynos 9 (8895) octa-core CPU shows that it takes roughly 8 seconds to initialize a session using CSIDH-512 and over 40 seconds using CSIDH-1024, without platform specific optimization. To the best of our knowledge, the proposed implementation is the first post-quantum resistant Signal protocol implementation and the first evaluation of using CSIDH as a drop-in replacement for ECDH in a communication protocol.

Cette thèse porte sur l'étude des points entiers et rationnels de certaines courbes et variétés modulaires. Après une brève introduction décrivant les motivations et le cadre de ce genre d'études ainsi que les résultats principaux de la thèse, le manuscrit se divise en trois parties. Le premier chapitre s'intéresse aux Q-courbes, et aux morphismes Gal(Q/Q) -> PGL2(Fp) qu'on peut leur associer pour tout p premier. Nous montrons que sous de bonnes hypothèses, pour p assez grand par rapport au discriminant du corps de définition de la Q-courbe, ce morphisme est surjectif, ce qui résout un cas particulier du problème d'uniformité de Serre (toujours ouvert en général). Les outils principaux du chapitre sont la méthode de Mazur (basée ici sur des résultats d'Ellenberg), la méthode de Runge et des théorèmes d'isogénie, suivant la structure de preuve de Bilu et Parent. Le second chapitre consiste en des estimations analytiques de sommes pondérées de valeurs de fonctions L de formes modulaires, dans l'esprit de techniques développées par Duke et Ellenberg. La motivation de départ d'un tel résultat est l'application de la méthode de Mazur dans le premier chapitre. Le troisième chapitre est consacré à la recherche de généralisations de la méthode de Runge pour des variétés de dimension supérieure. Nous y redémontrons un résultat de Levin inspiré de cette méthode, avant d'en prouver une forme assouplie dite "de Runge tubulaire", plus largement applicable. Dans l'optique de recherche de points entiers de variétés modulaires, nous en donnons enfin un exemple d'utilisation à la réduction d'une surface abélienne en produit de courbes elliptiques. / This thesis concerns the study of integral and rational points on some modular curves and varieties. After a brief introduction which describes the motivation and the setting of this topic as well as the main results of this thesis, the manuscript follows a threefold development. The first chapter focuses on Q-curves, and on the morphisms Gal(Q/Q) -> PGL2(Fp) that we can build with a Q-curve for every prime p. We prove that, under good hypotheses, for p large enough with respect to the discriminant of the definition field of the Q-curve, such a morphism is surjective, which solves a particular case of Serre's uniformity problem (still open in general). The main tools of the chapter are Mazur's method (based here on results of Ellenberg), Runge's method, and isogeny theorems, following the strategy of Bilu and Parent. The second chapter covers analytic estimates of weighted sums of L-function values of modular forms, in the fashion of techniques designed by Duke and Ellenberg. The initial goal of such a result is the application of Mazur's method in the first chapter. The third chapter is devoted to the search for generalisations of Runge's method for higherdimensional varieties. Here we prove anew a result of Levin inspired by this method, before proving an enhanced version called "tubular Runge", more generally applicable. In the perspective of studying integral points of modular varieties, we finally give an example of application of this theorem to the reduction of an abelian surface in a product of elliptic curves.