On s'intéresse dans cette thèse à la complexité bilinéaire de la multiplication dans toute extension de degré $n$ d'un corps $F_{q}$ à $q$ éléments, qui est étroitement liée au rang de tenseur de la multiplication dans $F_{q^n}$. L'algorithme de type évaluation-interpolation, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes uniformes et asymptotiques de la complexité bilinéaire. Pour obtenir ces meilleures bornes, la stratégie adoptée jusqu'à présent consistait à fixer le degré des places en augmentant le genre du corps de fonctions algébriques.Néanmoins, l'étude de la construction effective associée à ce type de stratégie fut jusqu'à présent négligée en raison d'un obstacle, lié à la construction du point de degré $n$, relevé par Shparlinski, Tsfasman et Vladut en 1992.On présente dans cette thèse une nouvelle stratégie qui consiste à fixer le genre du corps de fonctions algébriques tout en augmentant le degré des places.En appliquant cette stratégie aux corps de fonctions elliptiques, on montre d'une part que le rang de tenseur de la multiplication dans $F_{q^n}$ est quasi-linéaire en $n$, et d'autre part que la construction des algorithmes de multiplications bilinéaires issus de cette stratégie est réalisable en temps polynomial. On montre également comment construire explicitement ces algorithmes sur $F_{q^n}$, en les illustrant par un exemple. Enfin, on établit la première construction asymétrique de l'algorithme de type Chudnovsky. / In this thesis, we focus on the bilinear complexity of multiplication in any degree $n$ extension of the finite field $ F_{q}$, which is closely related to the tensor rank of multiplication in $ F_{q^n} $. The evaluation-interpolation type algorithm introduced by D.V and G.V Chudnovsky in 1987, is the basis of all algorithmic technique providing for now, the lower asymptotic and uniform bounds for the bilinear complexity.So far, the strategy to obtain these lower bounds was to fix the degree of places while increasing the genus of algebraic function fields. However, the study of the effective construction associated with this kind of strategy was until now neglected because of an obstacle related to the construction of a degree $n$ point, identified par Shparlinski, Tsfasman and Vladut in 1992. We present a new strategy which consists in fixing the genus of algebraic function fields while increasing the degree of places. Applying this strategy to the elliptic function fields, we show on the one hand that the tensor rank of multiplication in $ F_{q^n} $ is quasi-linear in $ n $, and on the other hand we prove that the construction of bilinear multiplication algorithms with this strategy is feasible in polynomial time. We also show how to construct explicitly these algorithms over $ F_{q^n} $ for large $n$ by illustrating the construction with an example. Finally, we establish the first asymmetric construction of the Chudnovsky type algorithm.

On s'intéresse dans cette thèse à la détermination du rang de tenseur de la multiplication dans $mathbb{F}_{q^n}$, l'extension de degré $n$ du corps fini $mathbb{F}_q$ ; ce rang de tenseur correspond en particulier à la complexité bilinéaire de la multiplication dans $mathbb{F}_{q^n}$ sur $mathbb{F}_q$. Dans cette optique, on présente les différentes évolutions de l'algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky et qui a permis d'établir que le rang de tenseur de la multiplication dans $mathbb{F}_{q^n}$ était linéaire en~$n$. Cet algorithme en fournit désormais les meilleures bornes connues dans le cas d'extensions de degré grand relativement au cardinal du corps de base — le cas des petites extensions étant bien connu. Afin d'obtenir des bornes uniformes en le degré de l'extension, il est nécessaire, pour chaque $n$, de déterminer un corps de fonctions algébriques qui convienne pour appliquer l'algorithme pour $mathbb{F}_{q^n}$, c'est-à-dire qui ait suffisamment de places de petit degré relativement à son genre $g$ et pour lequel on puisse établir l'existence de diviseurs ayant certaines propriétés, notamment des diviseurs non-spéciaux de degré ${g-1}$ ou de dimension nulle et de degré aussi près de ${g-1}$ que possible ; c'est pourquoi les tours de corps de fonctions sont d'un intérêt considérable. En particulier, on s'intéresse ici à l'étude des tours de Garcia-Stichtenoth d'extensions d'Artin-Schreier et de Kummer qui atteignent la borne de Drinfeld-Vlu{a}duc{t}. / In this thesis, we focus on the determination of the tensor rank of multiplication in $mathbb{F}_{q^n}$, the degree $n$ extension of the finite field $mathbb{F}_q$, which corresponds to the bilinear complexity of multiplication in $mathbb{F}_{q^n}$ over $mathbb{F}_q$. To this end, we describe the various successive improvements to the evaluation-interpolation algorithm introduced in 1987 by D.V. and G.V. Chudnovsky which shows the linearity of the tensor rank of multiplication in $mathbb{F}_{q^n}$ with respect to $n$. This algorithm gives the best known bounds for large degree extensions relative to the cardinality of the base field (the case when the degree of the extension is small is well known). In order to obtain uniform bounds, we need to determine, for each $n$, a suitable algebraic function field for the algorithm on $mathbb{F}_{q^n}$, namely a function field with sufficiently many places of small degree relative to its genus $g$ and for which we can prove the existence of divisors with some good properties such as non-special divisors of degree ${g-1}$ or zero-dimensional divisors with degree as close to ${g-1}$ as possiblestring; these conditions lead us to consider towers of algebraic function fields. In particular, we are interested in the study of Garcia-Stichtenoth towers of Artin-Schreier and Kummer extensions which attain the Drinfeld-Vlu{a}duc{t} bound.

Voir le texte.

Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980's. They provide public key cryptosystems based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) , which is so called because of its similarity to the discrete logarithm problem (DLP) over the integers modulo a large prime. One benefit of elliptic curve cryptosystems (ECCs) is that they can use a much shorter key length than other public key cryptosystems to provide an equivalent level of security. For example, 160 bit ECCs are believed to provide about the same level of security as 1024 bit RSA. Also, the level of security provided by an ECC increases faster with key size than for integer based discrete logarithm (dl) or RSA cryptosystems. ECCs can also provide a faster implementation than RSA or dl systems, and use less bandwidth and power. These issues can be crucial in lightweight applications such as smart cards. In the last few years, ECCs have been included or proposed for inclusion in internationally recognized standards. Thus elliptic curve cryptography is set to become an integral part of lightweight applications in the immediate future. This thesis presents an analysis of several important issues for ECCs on lightweight devices. It begins with an introduction to elliptic curves and the algorithms required to implement an ECC. It then gives an analysis of the speed, code size and memory usage of various possible implementation options. Enough details are presented to enable an implementer to choose for implementation those algorithms which give the greatest speed whilst conforming to the code size and ram restrictions of a particular lightweight device. Recommendations are made for new functions to be included on coprocessors for lightweight devices to support ECC implementations Another issue of concern for implementers is the side-channel attacks that have recently been proposed. They obtain information about the cryptosystem by measuring side-channel information such as power consumption and processing time and the information is then used to break implementations that have not incorporated appropriate defences. A new method of defence to protect an implementation from the simple power analysis (spa) method of attack is presented in this thesis. It requires 44% fewer additions and 11% more doublings than the commonly recommended defence of performing a point addition in every loop of the binary scalar multiplication algorithm. The algorithm forms a contribution to the current range of possible spa defences which has a good speed but low memory usage. Another topic of paramount importance to ECCs for lightweight applications is whether the security of fixed curves is equivalent to that of random curves. Because of the inability of lightweight devices to generate secure random curves, fixed curves are used in such devices. These curves provide the additional advantage of requiring less bandwidth, code size and processing time. However, it is intuitively obvious that a large precomputation to aid in the breaking of the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve which would be unavailable for a random curve. Therefore, it would appear that fixed curves are less secure than random curves, but quantifying the loss of security is much more difficult. The thesis performs an examination of fixed curve security taking this observation into account, and includes a definition of equivalent security and an analysis of a variation of Pollard's rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. A lower bound on the expected time to solve such ECDLPs using this method is presented, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. It is concluded that adding a total of 11 bits to the size of a fixed curve provides an equivalent level of security compared to random curves. The final part of the thesis deals with proofs of security of key exchange protocols in the Canetti-Krawczyk proof model. This model has been used since it offers the advantage of a modular proof with reusable components. Firstly a password-based authentication mechanism and its security proof are discussed, followed by an analysis of the use of the authentication mechanism in key exchange protocols. The Canetti-Krawczyk model is then used to examine secure tripartite (three party) key exchange protocols. Tripartite key exchange protocols are particularly suited to ECCs because of the availability of bilinear mappings on elliptic curves, which allow more efficient tripartite key exchange protocols.