Fonction thêta et applications à la cryptographie, Theta functions and cryptographic applications : theta functions and applications in cryptography

Damien Robert

Description

Sous la direction de Guillaume Hanrot
Thèse soutenue le 21 juillet 2010: Nancy 1
Le logarithme discret sur les courbes elliptiques fournit la panoplie standard de la cryptographie à clé publique: chiffrement asymétrique, signature, authentification. Son extension à des courbes hyperelliptiques de genre supérieur se heurte à la difficulté de construire de telles courbes qui soient sécurisées. Dans cette thèse nous utilisons la théorie des fonctions thêta développée par Mumford pour construire des algorithmes efficaces pour manipuler les variétés abéliennes. En particulier nous donnons une généralisation complète des formules de Vélu sur les courbes elliptiques pour le calcul d'isogénie sur des variétés abéliennes. Nous donnons également un nouvel algorithme pour le calcul efficace de couplage sur les variétés abéliennes en utilisant les coordonnées thêta. Enfin, nous présentons une méthode de compression des coordonnées pour améliorer l'arithmétique sur les coordonnées thêta de grand niveau. Ces applications découlent d'une analyse fine des formules d'addition sur les fonctions thêta. Si les résultats de cette thèse sont valables pour toute variété abélienne, pour les applications nous nous concentrons surtout sur les jacobienne de courbes hyperelliptiques de genre~$2$, qui est le cas le plus significatif cryptographiquement.
-Cryptographie
-Courbes hyperelliptiques
-Variétés abéliennes
-Isogénies
-Couplage
-Fonctions thêta
The discrete logarithm on elliptic curves give the standard protocols in public key cryptography: asymmetric encryption, signatures, ero-knowledge authentification. To extends the discrete logarithm to hyperelliptic curves of higher genus we need efficient methods to generate secure curves. The aim of this thesis is to give new algorithms to compute with abelian varieties. For this we use the theory of algebraic theta functions in the framework of Mumford. In particular, we give a full generalization of Vélu's formulas for the computation of isogenies on abelian varieties. We also give a new algorithm for the computation of pairings using theta coordinates. Finally we present a point compression method to manipulate These applications follow from the analysis of Riemann relations on theta functions for the addition law. If the results of this thesis are valid for any abelian variety, for the applications a special emphasis is given to Jacobians of hyperelliptic genus~$2$ curves, since they are the most significantly relevant case in cryptography.
-Cryptography
-Hyperelliptic curves
-Abelian varieties
-Isogenies
-Pairing
-Theta functions
Source: http://www.theses.fr/2010NAN10037/document

Sujets

• Cryptographie
• Couplage

Informations

• Publié par: Thesee
• Nombre de lectures: 49
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : [e-mail]




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm Départementdeformationdoctoraleeninformatique. ÉcoledoctoraleIAEMLorraine.
UFRSTMIA
Fonctionsthêtaetapplicationsàla
cryptographie
Tetafunctionsandcryptographicapplications
THÈSE
présentéeetsoutenuepubliquementle21juillet2010
pourl’obtentiondu
Doctoratdel’universitéHenriPoincaré—Nancy1
(spécialitéinformatique)
par
DamienRobert
Rapporteurs:
AntoineChambert-Loir Prof.Univ.Rennes1
KristinLauter MicrosofResearch
Composition du jury :
GuillaumeHanrot Prof.ÉNSdeLyon (directeur)
Jean-MarcCouveignes Prof.Univ.Toulouse2
DidierGalmiche Prof.Univ.Nancy1
Pierrick Gaudry CRCNRS(LORIA)
DavidKohel Prof.Univ.Méditerranée
KristinLauter MicrosofResearch (rapporteur)
FrançoisMorain Prof.ÉcolePolytechnique
SylvainPetitjean DR INRIA(LORIA) (référent)
LaboratoireLorraindeRechercheenInformatiqueetsesApplications—UMR7503FONCTIONS THÊTA ET APPLICATIONS À LA
CRYPTOGRAPHIE
DAMIEN ROBERT
Tèse d’informatique
Juillet2010Damien Robert : Fonctions thêta et applications à la cryptographie, Tèse d’informatique,
©Juillet2010Àmesparents.
Àmapetitecoccinelle.RÉSUMÉ
Lelogarithmediscretsurlescourbeselliptiquesfournitlapanopliestandarddelacrypto-
graphie à clé publique : chifrement asymétrique, signature, authentifcation. Son extension à
des courbes hyperelliptiques de genre supérieur se heurte à la difculté de construire de telles
courbesquisoientsécurisées.
DanscettethèsenousutilisonslathéoriedesfonctionsthêtadéveloppéeparMumfordpour
construiredesalgorithmesefcacespourmanipulerlesvariétésabéliennes.Enparticuliernous
donnons une généralisation complète des formules de Vélu sur les courbes elliptiques pour le
calcul d’isogénie sur des variétés abéliennes. Nous donnons également un nouvel algorithme
pour le calcul efcace de couplage sur les variétés abéliennes en utilisant les coordonnées
thêta. Enfn, nous présentons une méthode de compression des coordonnées pour améliorer
l’arithmétiquesurlescoordonnéesthêtadegrandniveau.Cesapplicationsdécoulentd’une
analysefnedesformulesd’additionsurlesfonctionsthêta.
Silesrésultatsdecettethèsesontvalablespourtoutevariétéabélienne,pourlesapplications
nousnousconcentronssurtoutsurlesJacobiennesdecourbeshyperelliptiquesdegenre ,qui
estlecasleplussignifcatifcryptographiquement.
ABSTRACT
Tediscretelogarithmonellipticcurvesgivesthestandardprotocolsinpublickeycryp-
tography: asymmetric encryption, signatures, zero-knowledge authentifcation. To extend
thediscretelogarithmtohyperellipticcurvesofhighergenusweneedefcientmethodsto
generate secure curves.
Teaimofthisthesisistogivenewalgorithmstocomputewithabelianvarieties.Forthiswe
usethetheoryofalgebraicthetafunctionsintheframeworkof Mumford.Inparticular,wegive
afullgeneralizationofVélu’sformulasforthecomputationofisogeniesonabelianvarieties.
Wealsogive a newalgorithm forthe computation ofpairings using thetacoordinates. Finally
wepresentapointcompressionmethodtomanipulatemoreefcientlythetacoordinatesof
highlevel.TeseapplicationsfollowfromtheanalysisofRiemannrelationsonthetafunctions
fortheadditionlaw.
Whereas the results of this thesis are valid for any abelian variety, for the applications a
special emphasis is given to Jacobians of hyperelliptic genus curves, since they are the most
signifcantlyrelevantcaseincryptography.
Motsclefs: Cryptographie, courbes hyperelliptiques, variétés abéliennes, isogénies, couplage,
fonctions thêta
Keywords:Cryptography,hyperellipticcurves,abelianvarieties,isogenies,pairing,thetafunc-
tions
viiPUBLICATIONS
Quelquesidéesetfguresdecettethèsesontreprisesdespublicationssuivantes:
1. J.-C. Faugère, D. Lubicz et D. Robert. Computingmodularcorrespondencesforabelian
varieties.Mai2009.arXiv:0910.4668
2. D. Lubicz et D. Robert. Computingisogeniesbetweenabelianvarieties. Jan. 2010. arXiv :
1001.2016
3. D.LubiczetD.Robert. Efcientpairingcomputationwiththetafunctions.Sousladir.
deG.Hanrot,F.MorainetE.Thomé.9thInternationalSymposium,Nancy,France,
ANTS-IX, July 19-23, 2010, Proceedings. Jan. 2010. url : http://www.normalesup.
org/~robert/pro/publications/articles/pairings.pdfREMERCIEMENTS
Wehaveseenthatcomputerprogrammingisanart,
becauseitappliesaccumulatedknowledgetotheworld,
because it requires skill and ingenuity, and especially
becauseitproducesobjectsofbeauty.
—DonaldE.Knuth[Knu74]
Awordofwarning—andapology.Tereareseveralthousandformulasinthispaperwhich
allowone or more“sign-likeambiguities”:i.e.,alternateandsymmetricbutnon-equivalent
reformulations.[...]Ihavemadeasuperhumaneforttoachieveconsistencyandeventomake
correctstatements:butIstillcannotguaranteetheresult.
—DavidMumford “Ontheequationsdefningabelianvarieties.”
$ { IFS=’
’; for i in ‘cat acknowledgements.txt‘; do
printf ’%s\a%s\n’ ‘printf "$i" | sha256sum‘ "$i";
done } | sort | cut -d ‘printf ’\a’‘ -f 2 > acknowledgements.tex
Ilyabiensûrtouslesmembresdel’équipeCacao/Caramel!Sonchefgrand,beau,fortet
1surtoutchevelu ,PierrickGaudry,quiatoujoursréponseàmesquestionsstupides;Emmanuel
Thoméentreautrespour sesconseilsUnixienset T Xniques,ainsique JérémieDetreypourE
toutes les explications sur les détails d’implémentation des couplages. Les rapporteurs Kristin
Lauter et Antoine Chambert-Loir m’ont fait l’honneur d’accepter de rapporter cette thèse,
qui est bien plus longue que ce que je n’espérais. Malgré cela, ils ont efectué un travail en
tout point remarquable. Avant tout, je souhaite remercier mon directeur de thèse, Guillaume
Hanrot,quim’aaccueilliàNancy,etatoujourssuprendredutempspourmoi.Laclartéde
2sesexplicationsscientifques,sesconseilsavisés,etsesqualitéshumaines enfontundirecteur
3en toutpoint remarquable. Jeremercie également les«jeunes »:RomainCossetetGaëtan
Bisson pour les remarques et rapports de bug sur mon programme de calcul d’isogénies. De
même, je remercie vivement les membres du jury, qui ont accepté de venir malgré la date peu
pratique.
Bien sûr, une thèse ne se limite pas seulement au travail scientifque, et je devrais remer-
cier tous les gens qui m’ont encadré pour mon monitorat, Monique Grandbastien, Lofi
Bellalem, Marion Videau et Pierrick Gaudry, ainsi que l’ensemble des personnels adminis-
tratifsquisimplifentconsidérablementlavied’unthésard.Jem’excuseauprèsdetoutesles
personnesquejen’aipascitées,jenevousaipasoubliés!
Les remerciements sont la partie la plus importante d’une thèse (car la plus lue), mais je ne
suis pas très fort pour cet exercice...Je préfère faire preuve de ma gratitude à l’oral plutôt qu’à
a1..Hum,çarisquedesevoir... 2.etculinaires !
3. JeneciteraipasNicolasEstibalsquiesttellementjeunequ’ilfaitplutôtpartiedelacatégoriedesbambins...
a..J’espère que j’aurai le droit à une tarte au citron après ma soutenance!
ix