Counting in the Jacobian of hyperelliptic curves [Elektronische Ressource] : in the light of genus 2 curves for cryptography / Sandeep Sadanandan

Sujets

• Wissenschaft

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 7
• Langue: English

Extrait

◦
◦ ◦ ◦ TECHNISCHE UNIVERSITÄT MÜNCHEN
◦ ◦ ◦ ◦
◦ ◦
◦ ◦ ◦
◦ ◦ ◦ ◦ FAKULTÄT FÜR INFORMATIK
◦ ◦ ◦
Lehrstuhl für Effiziente Algorithmen
Counting in the Jacobian of Hyperelliptic Curves
In the light of genus 2 curves for cryptography
Sandeep Sadanandan
Vollständiger Abdruck der von der Fakultät für Informatik der Technischen Universität
München zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: UNIV.-PROF. DR. GEORG CARLE
Prüfer der Dissertation:
1. UNIV.-PROF. DR. ERNST W. MAYR
2. UNIV.-PROF. DR. HANS-JOACHIM BUNGARTZ
Die Dissertation wurde am 06.05.2010 bei der Technischen Universität München
eingereicht und durch die Fakultät für Informatik am 24.09.2010 angenommen.ii
DocumentClassificationaccordingtoACMCCS(1998)
Categoriesandsubjectdescriptors:Abstract
With the drastic increase in the number and the use of handheld devices, – mobile
phones and smart cards – light weight cryptography has come to the lime light. El-
liptic and Hyperelliptic curve cryptosystems (ECC, HECC) are emerging as the best
solutions for light weight cryptography. Like in any traditional cryptosystem, the size
ofthecipher-textspaceisasignificantfactorindicatingtheachievablesecuritylevel. In
the traditional systems, the size of the group on which the system is defined, defines
the cipher-text space. Unlike the traditional ones, ECC and HECC are defined on the
Jacobian of curves. Gaining knowledge about the size of the Jacobian is not straight-
forward and the computation is inefficient. Since the generic group order counting
160methods are incapable of counting in large groups of cryptographic size (2 ), special
methods were devised for counting in the Jacobian of hyperelliptic curves, which are
not yet fast enough for practical applications. In this thesis, we are bringing together
theadvancesingroupordercountingandthespecialpropertiesofgenus2hyperelliptic
curves. The Primorial method for group order counting is applied in a special interval
where the group order is predicted to be. The resulting method provides an improve-
Pment factor of , whereP is the product of the firstp primes andϕ is Euler’s totient
ϕ(P)
function. We will see that the value of p varies, depending on the expected size of the
Jacobian. Itwillalsobeshownthatthefactorofimprovementbecomeslargerwhenthe
sizeofthegroupgetslarger.
iiiivAcknowledgment
Itwouldnothavebeenpossibletofinishthisthesis,withoutthehelpfrommanypeople.
On successful completion of the dissertation I take this opportunity to thank all those
involveddirectlyorindirectlyinitsaccomplishment.
First and foremost, I thank Prof. Dr. Ernst W Mayr for accepting me as a doctoral
candidatetoworkattheChairforEfficientAlgorithms. Hehasbeenverykindtomeall
throughthe4yearsofmydoctoralstudies. Foranykindofacademicornon-academic
matters,Icouldapproachhimandtherewasalwayssomesolutiontomyproblems.The
discussions with him were invaluable; the discussions and his infinite energy have in-
spiredandencouragedmeinnumeroustimesduringthepastfewyears.
I also thank Dr. Peter Ullrich, who guided me through the first few months of doc-
toral studies. It was he who gave me the initial momentum whichhelped me continue
myresearchonthetopicofthisthesis.
The atmosphere in the institute was always very warm. Hanjo, who could be very
wellbecalledthe“Guru”ofthechairwastheretoansweranylogisticalqueries. Ernst
BayerandthesecretariesweremorethanfriendlyandhelpfulwheneverIwasinneed.
Johannes Nowak, Johannes Krugel and Stefan Schmidt were alwaysthere for any little
puzzlesorriddlesorsomerandomproofs/jokes. Ithankallofthemforbeingwonder-
ful.
ManythankstothememberofGraduiertenKollegeGKAAMandGermanResearch
Foundation (DFG - Deutsche Forschungsgemeinschaft) for the scholarship they pro-
videdmefortheinitialcoupleofyears.
Last but not the least - family and friends. On this occasion I not only thank them,
butalsoexpressmyloveforallofthem. IthankRajyalakshmiforbeingthereforalmost
anythingIneededduringmydoctoralstudies. IalsothankSuthirthaSahawhohelped
meinitiallywithcomingtoGermany. Thelistwouldgettoolong,ifIamtodoso. Ionce
againthankeverybodywhohelpeddirectlyorindirectlyinthemakingofthisthesis.
SandeepSadanandan
München,May2010
vviIT IS BETTER TO DO THE RIGHT PROBLEM THE WRONG WAY THAN THE
WRONG PROBLEM THE RIGHT WAY.
- RICHARD HAMMING.
viiviiiContents
vii
Preface xvii
1 Introduction 1
1.1 Lightweightcryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Genericalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Privatekeysystems . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Publickeysystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Improvementovertraditionalsystems . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Whatisthisthesisabout? . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Bird’sview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Anoteonnotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 MathematicalBackground 9
2.1 Cryptographicrequirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Onewayfunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 DiscreteLogarithmProblem-DLP . . . . . . . . . . . . . . . . . . . 11
2.2 Algebraicgeometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Affinegeometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Projectivegeometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Affineandprojectivespaces-relation . . . . . . . . . . . . . . . . . 14
2.2.4 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Genusofacurve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Hyperellipticcurves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
ixx CONTENTS
2.3.3 Semi-reduceddivisors . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.4 Reduceddivisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.5 Representationsofdivisors . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Jacobianofacurve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 GroupoperationinJacobian . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Frobeniusendomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.1 Characteristicpolynomial . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.2 Boundsoncardinality-WeilInterval . . . . . . . . . . . . . . . . . 27
2.6 Additionalgorithmsfordivisors . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.1 Geometricallywhatisit? . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.3 Algebraicmethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.7 ECDLPandHECDLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.7.1 EllipticCurveDiscreteLogarithmProblem . . . . . . . . . . . . . . 33
2.7.2 HyperellipticCurveDLP . . . . . . . . . . . . . . . . . . . . . . . . 34
3 TheStateOfTheArt 35
3.1 Existingmethodsforcounting . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 BabyStepGiantStep-BSGS . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Birthdayparadoxmethod . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.3 OrdercountingwithPrimorial . . . . . . . . . . . . . . . . . . . . . 38
3.2 CountingintheJacobian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.1 Fieldswithsmallcharacteristic . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Fieldswithlarger/arbitrarycharacteristic . . . . . . . . . . . . . . . 39
3.2.3 Gaudry-Harleymethod . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Canthisbeimproved? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4 TheSolution 43
4.1 PrimorialVsWeil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 PrimorialandWeil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.1 Putinperspective. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 IncludingCartierManinoperator . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.1 TheCost-ReductionandEstimation . . . . . . . . . . . . . . . . . 48
4.4 IncludingSchoof’simprovement . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4.1 Thetroubleintroduced . . . . . . . . . . . . . . . . . . . . . . . . . . 50