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

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 : theses.sciences@scd.uhp-nancy.fr




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