Vignette d'image

Trace-zero subgroups of elliptic and twisted Edwards curves: a study for cryptographic applications

Auteur(s)
Bianco, Giulia,
Editeur(s)
Date de parution
2017
Mots-clés
Résumé
En 1999, Frey a proposé, pour la première fois, les sous-groupes de trace nulle des courbes elliptiques pour les applications à la cryptographie: il les a désignés comme une alternative valide, dans ce secteur, aux groupes classiques des points des courbes elliptiques. Considérons une courbe elliptique $E$ définie sur un corps fini $\mathbb{F}_q$, avec l'addition standard entre ses points. Etant donnée une extension de corps $\mathbb{F}_{q} \subseteq \mathbb{F}_{q^n}$ de degré $n$ premier et impair, le sous groupe de trace nulle de la courbe elliptique $E$, de degré $n$, est un sous-groupe du groupe des points de $E$ avec coordonnées dans $\mathbb{F}_{q^n}$. <br> En 2007, les courbes d'Edwards ont été introduites par Edwards, et elles ont été proposées pour les applications cryptographiques par Bernstein et Lange. Après, elles ont été généralisées aux courbes d'Edwards tordues. Les courbes d'Edwards tordues peuvent être considérées comme des courbes elliptiques speciales, décrites sous une nouvelle forme. Elles ont des advantages cryptographiques sur les courbes elliptiques dans la forme usuelle de Weierstrass. Les sous-groupes de trace nulle des courbes d'Edwards tordues sont definies de la même manière que les sous-groupes de trace nulle des courbes elliptiques. <br> Dans cette thèse, nous étudions les sous-groupes de trace nulle des courbes elliptiques et des courbes d'Edwards tordues, du point de vue de leur application potentielle à la cryptographie. En particulier, nous nous concentrons sur trois aspects distincts pour les sous-groupes de trace nulle: l'utilisation de représentations optimales des éléments du groupe, la construction d'algorithmes pour le produit scalaire, et l'étude de possibles attaques cryptographiques basés sur le problème du logarithme discret. Tous ces aspects sont tres importants pour l'efficacité et la sécurité d'un cryptosystème construit sur le groupe considéré. <br> A propos de représentations optimales de groupes, nous proposons deux représentations optimales pour les sous-groupes de trace nulle des courbes d'Edwards tordues. Nous donnons des algorithmes efficaces pour l'utilisation de nos représentations, et nous faisons des comparaisons avec les représentations analogues pour les sous-groupes de trace nulle des curbes elliptiques. <br> En ce qui concerne l'arithmétique efficace dans les sous-groupes de trace nulle, notre contribution consiste en un algorithme pour effectuer le produit scalaire dans les sous-groupes de trace nulle de degré trois. Cet algorithme suit une approche originale et il utilise des coordonnées optimales pour représenter les éléments du groupe. <br> Enfin, nous nous concentrons sur la sécurité des sous-groupes de trace nulle contre les attaques cryptographiques. Nous présentons une nouvelle variante de l'algorithme d'index calculus pour le problème du logarithme discret dans ces sous-groupes. Nous comparons la complexité de la résolution des systèmes polynômiaux obtenus avec notre méthode à celle de la résolution des systèmes construits avec l'unique autre spécialisation d'index calculus aux sous-groupes de trace nulle. Nous montrons que nos systèmes sont plus faciles à résoudre, dans les cas de sous-groupes de trace nulle de degré petit, qui sont les cas importantes pour les applications cryptographiques. <br> Dans l'algorithme pour le produit scalaire dans les sous-groupes de trace nulle de degré trois, et dans notre nouvelle méthode d'index calculus, nous utilisons les polynômes de sommation généralisés de courbes elliptiques. Ces polynômes sont présentés dans cette thèse pour la première fois, et ils peuvent être vus comme une généralisation originale des polynômes de sommation de courbes elliptiques de Semaev. Les polynômes de sommation généralisés permettent de trouver des relations entre points sur la courbe elliptique. Grâce à leur propriété géométrique, ils peuvent avoir des applications pertinentes en cryptographie., In 1999, Frey first suggested trace-zero subgroups of elliptic curves for applications to cryptography, as a valid alternative to the use of classical groups of points of elliptic curves in this sector. Take an elliptic curve $E$ defined over a finite field $\mathbb{F}_q$, with the standard addition between points. Given a field extension $\mathbb{F}_q\subseteq \mathbb{F}_{q^n}$ of odd prime degree $n$, the trace-zero subgroup of the elliptic curve $E$ of degree $n$ is a subgroup of the group of points of $E$ with coordinates in $\mathbb{F}_{q^n}$. <br> In 2007, Edwards curves were introduced by Edwards, and proposed for cryptographic applications by Bernstein and Lange. Right afterwards, they were generalized to twisted Edwards curves. Twisted Edwards curves can be seen as special elliptic curves, written in a new form. They have some cryptographic advantages over elliptic curves in the usual Weierstrass form. Trace-zero subgroups of twisted Edwards curves are defined in the same way as trace-zero subgroups of elliptic curves.<br> In this thesis, we study trace-zero subgroups of elliptic and twisted Edwards curves, from the point of view of their potential application to cryptography. In particular, we focus on three distinct aspects for trace-zero subgroups: the use of optimal representations for group elements, the construction of fast algorithms for scalar multiplication, and the study of possible cryptographic attacks based on the discrete logarithm problem. All these aspects are of great relevance for the efficiency and the security of a cryptosystem built on the given group.<br> Concerning optimal representations for group elements, we propose two optimal representations for trace-zero subgroups of twisted Edwards curves. We give efficient algorithms to deal with them, and we make comparisons with analogous representations for trace-zero subgroups of elliptic curves. <br> Concerning efficient arithmetic in trace-zero subgroups, our contribution consists of an algorithm to perform scalar multiplication in the trace-zero subgroup of degree three. This algorithm follows an original approach and makes use of optimal coordinates to represent the elements of the group. <br> Finally, we focus on the study of security of trace-zero subgroups against cryptographic attacks. We propose a new variant of the index calculus algorithm for the discrete logarithm problem in these subgroups. We compare the complexity of solving the polynomial systems obtained with our method with that of solving the systems computed with the only other specialization of the index calculus to trace-zero subgroups. We show that our systems are easier to solve in the case of trace-zero subgroups of small degree, that is the important case for cryptographic applications. <br> In both the algorithm for scalar multiplication in trace-zero subgroups of degree three, and in our new index calculus method for trace-zero subgroups, we make use of generalized summation polynomials of elliptic curves. Such polynomials are introduced in this thesis for the first time, and they can be seen as an original generalization of Semaev's summation polynomials of elliptic curves. Generalized summation polynomials allow to find relations between points on the elliptic curve. Thanks to their geometric property, they can have relevant applications to cryptography.
Notes
Thèse de doctorat : Université de Neuchâtel, 2017
Identifiants
https://libra.unine.ch/handle/123456789/2355
_
10.35662/unine-thesis-2631
Type de publication
doctoral thesis
Dossier(s) à télécharger