David Lubicz

Liste des publications

Articles de recherche

Computing Isogenies Between Abelian Varieties. David Lubicz, Damien Robert Compositio, 2012

Nous décrivons un algorithme efficace pour le calcul d'isogénies entre variétés abéliennes représentées dans le système de coordonnées donné par les fonctions thêta algébriques. Nous expliquons comment calculer toutes les isogénies entre variétés abéliennes dont le noyau est isomorphe à un groupe abstrait donné. Nous décrivons aussi un analogue des formules de Vélu pour calculer une isogénie dont le noyau est connu. Tous nos algorithmiques reposent d'une manière essentielle sur une généralisation des formules de Riemann.

Afin d'améliorer l'efficacité de nos algorithmiques, nous introduisons un algorithme de compression de point qui représente un point de niveau $4\ell$ d'une variété abélienne de dimension $g$ en utilisant seulement $g(g+1)/2 \cdot 4^g$ coordonnées. Nous donnons aussi des formules pour calculer le couplage de Weil et le couplage par commutateur de points donnés par leur coordonnées thêta. Nous les algorithmes présentés dans ce papier fonctionnent en toute généralité sur toute variété abélienne définie sur un corps fini de caractéristique impaire.

Computing modular correspondances for abelian varieties. Jean-Charles Faugère, David Lubicz, Damien Robert Journal of Algebra, 2011

L'objet de cet article est de donner un équivalent pour la dimension plus grande que 1 des classiques polynômes modulaires $\Phi_\ell(X,Y)$. Si $j$ est le $j$-invariant associé à une courbe elliptique $E_k$ définie sur un corps $k$ alors les racines de $\Phi_\ell(j,X)$ correspondent aux $j$-invariants des courbes qui sont $\ell$-sogènes à $E_k$. Désignons par $X_0(N)$ la courbe modulaire qui paramétrise l'ensemble des courbes elliptiques munies d'une sous-groupe de $N$-torsion. Il est possible d'interpréter $\Phi_\ell(X,Y)$ comme une équation définissant l'image d'une certaine correspondance modulaire $X_0(\ell) \rightarrow X_0(1) \times X_0(1)$ dans le produit $X_0(1) \times X_0(1)$.

Soit $g$ un entier positif et soit $\overline{n} \in \N^g$. Nous sommes intéressés par l'espace de module que nous notons $\mathcal{M}_{\overline{n}}$ des variétés abéliennes de dimension $g$ définies sur un corps $k$ munies d'une structure thêta de type $\overline{n}$. Soit $\ell$ un nombre premier et soit $\overline{\ell}=(\ell, \ldots , \ell)$, alors il existe une correspondance modulaire $\mathcal{M}_{\overline{\ell n}} \rightarrow \mathcal{M}_{\overline{n}} \times \mathcal{M}_{\overline{n}}$. Nous donnons un système d'équations algébriques qui définissent l'image de cette correspondance.

Nous donnons un algorithme pour résoudre ce système algébrique de manière bien plus efficace qu'avec un algorithme de calcul de base de Groebner général. Comme application, nous expliquons comment cet algorithme peut-être utilisé afin d'accélérer la phase d'initialisation d'un algorithme de comptage de points.

Efficient Pairing Computation With Theta Functions. ANTS IX, 2010

Dans ce papier, nous présentons une nouvelle approche utilisant les fonctions thêta afin de calculer les couplages de Weil et Tate. Un avantage de notre méthode, qui ne repose pas sur le classique algorithme de Miller, est sa généralité puisque qu'elle étend au cas de toutes les variétés abéliennes les formules classiques pour calculer les couplages de Weil et de Tate. Dans le cas de variétés abéliennes de dimension $1$ et $2$, nos algorithmes donnent lieu à des implémentations efficaces et naturellement déterministes. Nous introduisons aussi les couplages de Weil et Tate symétriques et expliquons comment les calculer efficacement. Nous exhibons une jolie compatibilité algorithmique entre certains groupes algébriques quotientés par l'action de l'automorphisme $-1$, pour lesquels la $\Z$-action résultante peut se calculer efficacement à l'aide d'un algorithme de type Montgomery ladder.

On the security of oscillator-based random number generators. Mathieu Baudet, David Lubicz, Julien Micolod, André Tassiaux Journal of Cryptology, 2010

Les générateurs d'aléa physiques (alias TRGNs) apparaissent comme des éléments critiques pour de nombreux cryptosystèmes. Cependant de tels composants viennent rarement accompagnés d'une évaluation formelle de leur sécurité comme c'est le cas pour la briques cryptographiques classiques. Dans ce travail, nous présentons une étude statistique complète des TRNGs à base d'oscillateurs sujets à un bruit de phase. Ce schéma classique, typiquement instancié avec un anneaux d'oscillateurs, fournit un moyen simple et élégant d'implémenter un TRNG sur un composant. Notre étude mathématique permet d'évaluer et de contrôler les principaux paramètres de sécurité d'une telle source d'aléa, en particulier son taux d'entropie et le biais de certaines chaînes de bits, pourvu qu'un petit nombre de paramètres physiques de l'oscillateur son connus. Afin d'évaluer ces paramètres de manière sûre, nous décrivons aussi une méthode expérimentale permettant de filtrer les perturbations globales affectant un un circuit, perturbations possiblement visibles d'un attaquant. Finalement, à partir de notre modèle, nous déduisons des tests statistiques applicables à la suite de bits produites par un TRNG. En particulier, dans le cas d'une implémentation non sûre, nous montrons comment retrouver les paramètres de l'oscillateur sous-jacent.

A point counting algorithm using cohomology with compact support. Gweltaz Chatel, David Lubicz LMS Journal of Computation and Mathematics , 2009.

Nous décrivons un algorithme pour compter le nombre de points rationnels sur une courbe hyperelliptique définie sur un corps fini de caractéristique impaire fondé sur le calcul de l'action du morphisme de Frobenius sur une base de la cohomologie de Monsky-Washnitzer à support compact. Cet algorithme s'inscrit dans la veine d'une exploration systématique d'applications potentielles des théories cohomologiques à la problématique du comptage de points.

Notre algorithme se compose de deux étapes. La première consiste en le calcul d'une base de la cohomologie afin, dans une deuxième étape, de calculer une représentation du morphisme de Frobenius. Négligeant les termes logarithmiques, nous obtenons une complexité en temps de O(g^4 n^3) pour une consomation mémoire de l'ordre de O(g^3 n^3) avec g le genre de la courbe et n le degré absolu du corps de base. Nous donnons une analyse de complexité détaillée ainsi qu'une preuve de correction de notre algorithme.

The arithmetic of characteristic 2 Kummer surface. Pierrick Gaudry, David Lubicz Finite Fields and Applications, 2009.

L'objectif de cet article est une description d'un modèle pour des surfaces de Kummer en caractéristique 2 avec des formules associées pour le calcul de la loi de pseudo-groupe. Puisque le modèle classique a mauvaise réduction une renormalisation des paramètres est nécessaire qui peut être justifiée grâce à la théorie des fonctions théta algébriques. Les formules que nous obtenons sont très efficaces et pourraient être utiles pour des applications cryptographiques. Nous montrons aussi que la même stratégie appliquées aux courbes elliptiques redonne des formules à la Montgomery en caractéristique impaire qui ont un certain intérêt et nous retrouvons des formules déjâ découvertes par Stam en caractéristique 2.

A p-adic quasi-quadratic point counting algorithm. Robert Carls, David Lubicz Int. Math. Res. Not., 2008.

Dans cet article, nous présentons un algorithme pour calculer le nombre de points rationnels d'une jacobienne de courbe hyperelliptique ordinaire définie sur un corps fini F_q ayant q éléments, avec une complexité en temps de O(n^{2+o(1)}), avec n=\log(q). Dans cette dernière fonction de complexité le genre et la caractéristique sont supposées fixées. Nous donnons une analyse de complexité détaillée de l'algorithmique. Une preuve de correction sera publiée autre part car elle dépasse le cadre de cet article.

Notre algorithme généralise à la fois l'algorithme AGM de J.-F. Mestre et de la méthode du relèvement canonique de T. Satoh. Nous relevons de caniquement un certain invariant arithmétique donné par par des théta constantes. Les théta constantes sont calculées par rapport à une théta structure produit semi-canonique de niveau 2p avec p=\mathrm{char}(\F_q)>2.

Les résultats de ce papier suggèrent une réponse positive globale à la question de savoir s'il existe un algorithme de complexité quasi-quadratique pour le calcul du nombre de points rationnels d'une variété abélienne ordinaire définie sur un corps fini.

Attribute-Based Broadcast Encryption Scheme Made Efficient. David Lubicz, Thomas Sirvent Proc. of Advances in Cryptology- Africacrypt'08, 2008, Casablanca

Dans ce papier, nous décrivons un nouveau schéma de broadcast pour des récepteurs sans état. La principale différence entre notre schéma et ceux dérivés à partir des paradigme des sous-arbres complets est que dans notre cas le groupe des utilisateurs privilégiés est décrit par des attribus. En effet, il existe des applications réelles pour lesquelles l'utilisation d'une structure d'accès apporte une plus grande efficacité et une plus grande facilité de déploiement. D'autre part, l'algorithme de déchiffrement dans les schéma basés sur les attribus décrits dans la littérature compatibles avec la problématique de broadcast est consomatrice de beaucoup de temps pour le receveur puisque cela entraine le calcul d'un grand nombre de couplages. Cela consitue un réel problème pour les applications de broadcast pour lesquels les contraintes technologiques se situent du coté du receveur.

Notre schéma peut être vu comme un moyen de bénéficier à la fois des performances de déchiffrement des schémas de broadcast classiques et de la facilité de mise en oeuvre apportée par gestion par attribus. De manière plus précise, notre schéma permet de sélectionner ou de révoquer des utilisateurs en envoyer des chiffrés de taille linéaire par rapport au nombre d'attribus, ce qui est en général beaucoup moins que le nombre d'utilisateurs. Nous prouvons que notre schéma est sûr contre des collusions dans le modèle du groupe général avec couplage.

Pseudo-random groups and related problems. David Lubicz, Thomas Sirvent Identity-Based Cryptography, M. Joye et G. Neven,Cryptology and Information Security Series, IOS Press, 2008

Les familles de groupes avec couplage sont considérés comme des blocs élémentaires standards afin de constituer des primitives cryptographiques. La sécurité de schémas basés sur de tels groupes repose sur des hypothèses reliées au problème du logarithme discret. Comme ce problèmes ne sont pas prouvés difficiles, il est possible de se demander s'il existe quand même des arguments qui laisserait à penser que de tels problèmes sont difficiles. En fait, il est assez habituel d'évaluer leur difficulté à l'aune du modèle du groupe générique introduit pas Nechaev et Shoup. Le réalisme de ce modèle est toutefois sujet à des critiques: en particulier, le fait que la réponse à toute requète fraiche soit une suite aléatoire contrevient à ce que l'on attend d'une loi de groupe usuelle. Afin d'améliorer ce modèle, nous introduisons de famille de groupes pseu-aléatoires. Nous expliquons comment reduire la sécurité d'un problème dans une famille de groupes pseudo-aléatoire à la sécurtié du même problème évaluée dans le modèle du groupe générique et la sécurité d'une famille de permutations fortement pseudo-aléatoires.

Higher dimensional 3-adic CM construction. Robert Carls, David Kohel, David Lubicz J. of Algebra, 319(4)971-2006, 2008.

Nous décrivons une méthode pour construire des courbes hyperelliptiques de genre $2$ sur un corps de nombre de petit degré dont la jacobienne est à multiplication complexe et à une réduction bonne et ordinaire modulo $3$. Nous démontrons l'existence d'un algorithme de complexité en temps quasi-quadratique pour calculer le relevé canonique en caractéristique $3$ basé sur des équations définissant un analogue en dimension plus grande de la classique courbe modulaire $X_0(3)$. Nous donnons une description détaillé de notre méthode dans le cas particulier du genre $2$.

On a classification of finite statistical tests. David Lubicz Adv. Math. of Com., 1(4):509-524, 2007.

Des tests statistiques du caractère aléatoire de suites sont souvent utilisées en cryptographie afin d'effectuer des tests de routine pour des générateur de pseudo-aléa ou d'aléa physique. La plupart des suites de tests disponibles sont basées sur la théorie des tests d'hypothèse qui permet de décider si un échantillon a été tiré suivant une certaine distribution. Dans cet article, nous développons les fondements théoriques des tests statistiques de suites aléatoires et des tests d'hypothèse avec un intérêt particulier pour les applications crypotographiques. Nous en déduisons des conséquences pratiques intéressantes.

A quasi-quadratic time algorithm for hyperelliptic curve point counting. Reynald Lercier, David Lubicz. Ramanujan J., 12(3):399-423, 2006.

Nous décrivons un algorithme qui permet de calculer la cardinalité de jacobiennes de courbes hyperelliptiques ordinaires sur un corps fini F_2^n en temps O(n^{2+o(1)}). Ce algorithme est dérivé d'idées dués à Mestre. Plus précisémment, nous expliquons les fondements mathématiques de l'algorithme de Mestre et développons une variante ayant une complexité quasi-quadratique. Entre autre, nous présentons un algorithme pour trouver des racines dans un système d'équations d'Artin -Schreier généralisées et nous donnons les résultats que nous avons obtenus à l'aide d'une implémentation efficace. En particulier, nous avons été capable d'obtenir la cardinalité de courbes de genre un, deux ou trois définies sur des corps finis de très grande taille.

Counting points in elliptic curves over finite fields of small characteristic in quasi quadratic time. Reynald Lercier, David Lubicz Advances in cryptology-EUROCRYPT 2003, 360-373, Lecture Notes in Comput. Sci., 2656, Springer, Berlin, 2003.

Soit p un petit nombre premier et soit q=p^n. Soit E une courbe elliptique sur F_q. Nous décrivons un algorithme sans précalcul qui donne le $j$-invariant du relevé canonique de E en un temps O(\log n) fois le temps nécessaire pour calculer une puissance du relevé du morphisme de Frobenius. Soit \mu la constante telle que le produit de deux entiers de n bits prenne O(n^\mu) opérations élémentaires, ce produit un algorithme pour calculer le nombre de points d'une courbe elliptique ayant une complexité en espace O(n^{\frac{5}{2}}) en en temps O(n^{\max(1.19, \mu)+\mu+\frac{1}{2}}\log n). Quand le corps de base est muni d'une base Gaussienne optimale de petit type, nous obtenons de plus un algorithme avec une complexité en temps O(\log(n)n^{2\mu}) et O(n^2) en espace. D'un point de vue pratique, l'algorithme correspondant s'implémentaire particulièrement bien. Nous le montrons en faisant un calcul sur un corps de base de 100002 bits.

Pencils of curves defined by a regular function. David Lubicz Bull. Sci. Math. 125,no. 2, 139-160, 2001.

Dans cet article, nous généralisons beaucoup de résultats sur la topologie des fonctions polynomes $f:C^2-> C$ dans le cas de fonctions $f:U-> C$.

Description of the cohomology of the complement of a nonreducible divisor. David Lubicz Bull. Sci. Math. 124,no. 6, 447-458, 2000.

Dans cet article, nous étudions la topologie du plongement d'une courbe algébrique dans $\proj_{\comp}^2$ en donnant des bases effectives pour la cohomologie à coefficient complexe de l'espace complémentaire. Nous obtenons en particulier une majoration de l'ordre des poles d'une telle base qui est meilleure que celle décrite dans les travaux fondamentaux de P. Griffiths. Nous traitons quelques exemples qui illustrent certains résultats de comparaison entre la filtration par l'ordre du pôle et la filtration de Hodge de la cohomologie à coefficient complexe.

Preprints

Linear Algebra over $\Z_p[[u]]$ and related rings} . Xavier Caruso, David Lubicz preprint

Soit un anneau de valuation discrète complet, S=R[[u]] et n un entier positif. L'objectif de ce papier est d'expliquer comment calculer efficacement les opérations usuelles tel que la somme et l'intersection de sous-S-modules de S^n. Comme S n'est pas principal, il n'est pas possible d'avoir une borne uniforme sur le nombre de générateurs du module résultant des opérations précédentes. Nous expliquons comment contourner ce problème, suivant une idée d'Iwasawa, en calculant une approximation du résultat de l'opération à un quasi-isomorphisme près. Au cours de l'analyse de la précision p-adique et u-adique nécessaire pour les calculs, nous introduisons des anneaux de coefficients plus généraux. Les calculs d'algèbre linéaire modulo quasi-isomorphisme avec les S-modules a des applications en théorie d'Iwasawa et en théorie de Hodge p-adique.

Un algorithme de calcul de réseaux dans les représentations semi-stables. Xavier Caruso, David Lubicz preprint

Le but de cet article est de présenter un algorithme de complexité polynômiale pour calculer la semi-simplifiée modulo p d'une Q_p-représentation semi-stable du groupe de Galois absolu d'un corps p-adique. Pour ce faire, nous utilisons abondamment la théorie de Hodge p-adique et, en particulier, la théorie des modules de Breuil-Kisin.

A generalisation of Miller's algorithm and applications to pairing computations. David Lubicz, Damien Robert preprint

Dans cet article, nous utilisons la théorie des fonctions thêta afin de généraliser à toutes le variétés abliennes l'algorithme de Miller qui permet de calculer la fonction associée à un diviseur principal. Nous expliquons aussi comment utiliser le morphisme de Frobenius sur les variétés abéliennes définies sur un corps fini afin de racourcir le nombre de boucles nécessaires au calcul des couplages de Weil et de Tate. Cela extend des résultats connus sur les couplage de Ate à toutes les variétés abéliennes. Ensuite, nous utilisons les précédent ingrédients afin d'obtenir une varianté du couplage optimal sur les variétiés abéliennes. Nous comparons en terme de performance les algorithmes que nous obtenons à ceux déjà connus dans le cas des courbes elliptiques.

Towards an oscillator based TRNG with a certified entropy rate. David Lubicz, Nathalie Bochard preprint

Nous décrivons une méthode pratique et efficace pour mesurer le taux d'entropie d'un générateur d'aléa physique (TRNG) à base d'anneaux d'oscillateurs qui ne nécessite pas de sortir et d'analyser un signal à l'aide d'un dispositif externe. La méthode repose plutôt sur des calculs simples, qui peuvent être embarqués dans n'importe quel FPGA ou ASIC avec une adaptation mineure de design classiques. Elle peut être utilisée pour la calibration d'un TRNG à base d'anneaux d'oscillateurs ou afin de certifier le taux d'entropie d'un TRNG en fonctionnement. Nous approche, qui est inspirée de la méthode d'échantillonnage cohérent, s'applique sous l'hypothèse générale que le jitter de phase est petit comparé à la période des oscillateurs. Dans ce cas, nous montrons qu'il est possible de mesurer la phase relative entre deux oscillateurs avec une précision qui est bien meilleure que la résolution temporelle de n'importe quelle horloge interne. Nous utilisons cette observation afin de retrouver, sous des hypothèses raisonnables, la distribution de la composante marche aléatoire du bruit de phase à partir de laquelle il est possible de calculer une borne inférieure pour le taux d'entropie du TRNG. Nous méthode a fait l'objet de nombreux tests avec des simulations et des implémentations matérielles. Nous tirons des conclusions et des recommandations pour une implémentation fiable de TRNG pour des applications cryptographiques.

A Secure Key Management Interface with Asymmetric Cryptography. Marion Daubignard, David Lubicz, Graham Steel preprint

Les systèmes cryptographiques tels que les modules matériels de sécurité ne peuvent apporter de garanties de sécurité que dans la mesure où leur interface de programmation (API), qui offre les services de cryptographie à l'extérieur de module, atteint un certain niveau de sécurité. Il a été constaté que des défauts de conception ou des erreurs d'implémentation dans les APIs de sécurité sont à l'origine de vulnérabilités pouvant entraîner la fuite de secrets comme des clefs ou des PINs. Idéalement, nous voudrions concevoir de telles interfaces de manière à pouvoir prouver formellement des propriétés de sécurité, même si certaines clefs sont corrompues. Dans cet article, nous partons d'une telle API, due à Cortier et Steel, conçue de manière à disposer d'une preuve de sécurité pour la gestion de clefs symétriques, et nous l'adaptons à la cryptographie asymétrique en donnant une nouvelle définition de sécurité avec les preuves associées. Afin de prendre en compte la cryptographie asymétrique, nous sommes amenés à gérer de manière différentiée les propriétés de confidentialité et d'intégrité et à ajouter les fonctionnalités classiques d'une infrastructure de gestion de clefs publiques (i.e. la certification des clefs publiques). \`A notre connaissance, il s'agit de la première preuve d'interface prouvée permettant l'usage de primitives asymétriques pour la gestion de clefs : l'interface de Cachin et Chandran prévoit l'usage de primitives asymétriques uniquement pour le chiffrement et la signature de données, et non pas pour la gestion des clefs.

Chapitres de livres

Random numbers generation and testing. Tanja Lange, David Lubicz, Andrew Weigl. Handbook of elliptic and hyperelliptic curve cryptography, 715--735, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Point counting on elliptic and hyperelliptic curves. Reynald Lercier, David Lubicz, Frederik Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography, 407--453, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Cohomological background on point counting. David Lubicz, Frederik Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography, 133--141, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Background on $p$-adic numbers. David Lubicz. Handbook of elliptic and hyperelliptic curve cryptography, 39--44, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Algebraic background. Christophe Doche, David Lubicz. Handbook of elliptic and hyperelliptic curve cryptography, 19--37, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Manuscripts

Quelques aspects algorithmiques de la cryptographie. David Lubicz. [French] Mémoire d'Habilitation à Diriger des Recherches.

La cryptographie à clef publique, qui fut inventée dans les années soixante-dix par W. Diffie et M. Hellman, apporte par rapport à la cryptographie symétrique un certain nombre de fonctionnalités particulièrement intéressantes pour les applications pratiques. Sa mise en oeuvre repose le plus souvent sur la difficulté calculatoire de certains problèmes issus de la théorie des nombres. De là, on peut déduire des fonctions à sens unique, des fonctions trappes puis construire et prouver par réduction des protocoles permettant de répondre à des objectifs de sécurité variés, les plus courants étant le chiffrement ou la signature numérique.

Un problème classiquement utilisé en cryptographie asymétrique est le problème du logarithme discret qui est par exemple à la base de toute la cryptographie sur courbe elliptique. Le problème du logarithme discret permet de construire des fonctions supposées à sens unique à partir de familles de groupes disposant d'un certain nombre de bonnes propriétés. Dans ce mémoire, nous présentons des techniques permettant de définir, représenter et calculer des familles de groupes utilisables dans des cryptosystèmes à base de logarithme discret. Des considérations de sécurité ou de performance nous amènent à revisiter d'un point de vue algorithmique des concepts développés dans les années soixante pour les besoins de la théorie des nombres et de la géométrie arithmétique : citons par exemple la multiplication complexe, les fonctions thêta algébriques, la cohomologie rigide, la théorie de Serre-Tate.

Les tests statistiques en cryptographie. David Lubicz. [French] preprint.

L'objet de ce document est de définir la notion de suite aléatoire et de justifier des tests afin de valider le bon fonctionnement d'un générateur d'aléa ou de pseudo-aléa.

Mémoire de thèse.. David Lubicz. [French] Thèse de l'Université Bordeaux I.

Dans cette thèse, on s'intéresse à la topologie du complément $U=\proj^2 \backslash C$, qui est une surface lisse et affine. Dans le premier chapitre, on décrit des bases explicites pour les groupes de cohomologie à coefficients complexes, $H^i(U)$ pour $i=1,2$ en supposant données des bases pour les groupes $H^i(U_j)$ o\`u $U_j=\proj^2 \backslash C_j$. Dans le deuxième chapitre, on généralise beaucoup de résultats sur la topologie d'une fonction polynomiale, $f: \comp^2 \rightarrow \comp$ dans le cas d'une fonction régulière $f:U \rightarrow \comp$.