Weyl Gröbner basis cryptosystems [Elektronische Ressource] / Rashid Ali

Rashid Ali

Description

DissertationWeylGrobner¨ BasisCryptosystemsRashidAliEingereicht anderFakultat¨ fur¨ InformatikundMathematikderUniversitat¨ PassaualsDissertationzurErlangungdesGradeseinesDoktorsderNaturwissenschaftenSubmittedtothe DepartmentofInformaticsandMathematicsofthe Universitat¨ PassauinPartialFulfilmentoftheRequirementsfor the Degreeof aDoctorintheDomainofScienceBetreuer/Advisor:Prof. Dr. MartinKreuzerUniversitat¨ PassauApril2011Tomy Parents,my wife Samina,my kids, Ahmed and Maheen ...AbstractIn this thesis, we shall consider a certain class of algebraic cryptosystems calledGrobner¨ Basis Cryptosystems. In 1994, Koblitz introduced the Polly Cracker cryp-tosystem that is based on the theory of Grobner¨ basis in commutative polynomialsrings. The security of this cryptosystem relies on the fact that the computation ofGrobner¨ basisis,ingeneral,EXPSPACE-hard. CryptanalysisofthesecommutativePolly Cracker type cryptosystems is possible by using attacks that do not requirethe computation of Grobner¨ basis for breaking the system, for example, the attacksbased on linear algebra. To secure these (commutative) Grobner¨ basis cryptosys-tems against various attacks, among others, Ackermann and Kreuzer introduced ageneral class of Grobner¨ Basis Cryptosystems that are based on the difficulty ofcomputing module Grobner¨ bases over general non-commutative rings.

Sujets

• Mathematics

Informations

• Publié par: universitat_passau
• Publié le: 01 janvier 2011
• Nombre de lectures: 52
• Langue: Deutsch

Extrait

Dissertation

WeylGr¨obnerBasisCryptosystems

AliRashid

EingereichtanderFakult¨atf¨urInformatikundMathematik

derUniversit¨atPassaualsDissertationzurErlangungdes

NaturwissenschaftenderDoktorseinesGrades

SubmittedtotheDepartmentofInformaticsandMathematics

oftheUniversit¨atPassauinPartialFullmentoftheRequirements

fortheDegreeofaDoctorintheDomainofScience

Advisor:/Betreuer

Prof.Dr.MartinKreuzer

Universit¨atPassau

2011April

To

my

my

my

Parents,

wife

kids,

SaminaAhmed,

and

Maheen...

Abstract

Inthisthesis,weshallconsideracertainclassofalgebraiccryptosystemscalled
Gr¨obnerBasisCryptosystems.In1994,KoblitzintroducedthePollyCrackercryp-
tosystemthatisbasedonthetheoryofGr¨obnerbasisincommutativepolynomials
rings.Thesecurityofthiscryptosystemreliesonthefactthatthecomputationof
Gr¨obnerbasisis,ingeneral,EXPSPACE-hard.Cryptanalysisofthesecommutative
PollyCrackertypecryptosystemsispossiblebyusingattacksthatdonotrequire
thecomputationofGr¨obnerbasisforbreakingthesystem,forexample,theattacks
basedonlinearalgebra.Tosecurethese(commutative)Gr¨obnerbasiscryptosys-
temsagainstvariousattacks,amongothers,AckermannandKreuzerintroduceda
generalclassofGr¨obnerBasisCryptosystemsthatarebasedonthedifcultyof
computingmoduleGr¨obnerbasesovergeneralnon-commutativerings.Theobjec-
tiveofthisresearchistodescribeaspecialclassofsuchcryptosystemsbyintroduc-
ingtheWeylGr¨obnerBasisCryptosystems.Wedividethisclassofcryptosystems
intwopartsnamelythe(left)WeylGr¨obnerBasisCryptosystemsandTwo-Sided
WeylGr¨obnerBasisCryptosystems.WesuggesttouseGr¨obnerbasesforleftand
two-sidedidealsinWeylalgebrastoconstructspecicinstancesofsuchcryptosys-
tems.Weanalysetheresistanceofthesecryptosystemstothestandardattacksand
providecomputationalevidencethatsecureWeylGr¨obnerBasisCryptosystemscan
bebuiltusingleft(resp.two-sided)Gr¨obnerbasesinWeylalgebras.

ledgementwAckno

Iwouldliketousethisspacetosayabig‘ThankYou’tomanypeoplewhohave
helpedandencouragedmethroughoutthelonganddifcultprocessofcompleting
studies.doctoralmyAtthetopofthelististhenameofmysupervisor,ProfessorDr.MartinKreuzer,
whoseencouragement,guidanceandsupportfromtheinitialtothenallevelen-
abledmetodevelopanunderstandingofthesubject.Ithasbeenanhonourtobe
hisPh.Dstudent.Iappreciateallhiscontributionsoftime,ideas,andsuggestions
tomakemyPh.D.experienceproductiveandstimulating,andaboveallforpro-
vidingawonderfulresearchandworkingenvironmentinourgroupof‘Symbolic
Computations’.IwishtoacknowledgeDr.ViktorLevandovskyyforhelpfuldiscussionsabout
thecomputationsinWeylalgebrasandforprovidingmanyvaluablesuggestionson
thetopic.FundsforthisworkareprovidedbytheHigherEducationCommission
ofPakistanandtheDeutscherAkademischerAustauschDienst(GermanAcademic
ExchangeService).Theservicesandsupportofbothoftheseorganizationsare
highlyappreciated.Atthispoint,IamindebtedtoProf.Dr.GrafandDr.Levan-
dovskyyforrecommendingmyapplicationforthefurthernancialsupport.
Iamindebtedtoallmycolleagueswhohavesharedtheirexpertisewithme.
InparticularIwouldliketothankS.Kasper,J.LimbekandS.Schusterfortheir
helpandfruitfuldiscussionsduringthedevelopmentofthepackageWeylforthe
computeralgebrasystemApCoCoA.Manythankstomyofce-mateEhsanUllah
fortheproof-readingsomepartsofthisworkandforthefruitfuldiscussionrelated
solving.systempolynomialtoIwouldalsoliketothankmyfriendsDrTayyabKamran,DrAsifBashir,Bi-

lal,Riaz-ur-Rehman,Izhar,ImranandMudassarforbeingavailableatanytimefor
everythingandfortheircontinuousmotivationandencouragementforthecomple-
tionofthiswork.Infact,theyqualifythecriteriathat‘Afriendinneedisafriend
indeed’.MyexperienceatPassauwouldnothavebeensuchapleasurableonewith-
outthepresenceofallmy‘new’friendslivingthere.Inparticular,thepresenceof
Ehsan-UllahFarman,AamirShahzad,AmirChishtiandtheirfamilieshavemade
myexperienceoflivingabroadsuchaniceandwonderfulthatcannotbeforgotten
life.mythroughoutLastly,Iwouldliketothankmywholefamilyforalltheirloveandencourage-
ment.Formyparentswhoraisedmewithloveandcareandsupportedmeinallmy
pursuits.IwishtoexpressmyloveformylovelysonAhmed,andmycutedaughter,
MaheenforallowingmeutilizingthetimethatIshouldhavetospendwiththem.
Andmostofall,Iwouldliketoexpressmydeepgratitudetomyloving,supportive,
andencouragingwifeSaminaforhercontinuoussupportandpatienceduringallthe
stagesofthisthesis.Thankyou.

201114,AprilUniversit¨atPassau,Germany

vi

AliRashid

Contents

Abstract

wledgementAckno

Notations

ListofAbbreviations

oductionIntr1

iii

v

xi

xiii

1

2Gr¨obnerBasesinWeylAlgebras13
2.1WeylAlgebras.............................13
2.2BasicProperties............................18
2.3LeftGr¨obnerBasesinWeylAlgebras................21
2.4LeftIdealMembership........................31
2.5ConstructingGr¨obnerBasesofLeftIdealsofA...........33
n2.6ComputerAlgebraSystems......................36

3Gr¨obnerBasisCryptosystems39
3.1Cryptography.............................39
3.2ThePollyCrackerCryptosystems..................43
3.3CryptanalysisofPollyCracker....................45
3.4TheChosenCiphertextAttack....................45
3.5TheLinearAlgebraAttack......................46

vii

Contents

3.6IntelligentLinearAlgebraAttack...................50
3.7CommutativeGr¨obnrBasisCryptosystems..............53
3.8AttackByPartialGr¨obnerBasis...................56
3.9ChosenCiphertextAttackandCGBC................58
3.10GeneralGr¨obnerBasisCryptosystems................60

4WeylGr¨obnerBasisCryptosystems63
4.1TheWGBC..............................63
4.2WGBCKeyGenerationandImplementation.............70
4.3ConstructionofHardInstances....................73
4.4AWGBCBasedonRemark2.5.5..................83

87SecurityandEfciency55.1Efciency...............................87
5.2LinearAlgebraAttacks........................90
5.3PartialGr¨obnerBasisAttack.....................100
5.4ChosenCiphertextAttackandWGBC................104
5.5AdaptiveChosen-CiphertextAttack.................106
5.6FurtherSecurityParameters.....................108

6TwoSidedWeylGr¨obnerBasisCryptosystems109
6.1Two-SidedGr¨obnerBases......................110
6.2Two-sidedWeylGr¨obnerBasisCryptosystems............116
6.3TWGBCKeyGenerationandImplementation............119
6.4ConcreteHardInstances.......................126
6.5EfciencyandSecurity........................136
6.6TWGBCChallenge:..........................142

APackageWeyl149
A.1AvailableFunctions..........................150

161ImplementationBB.1LinearAlgebraAttack(commutative)................161
B.2IntelligentLinearAlgebraAttack...................163

viii

C

B.3LinearAlgebraAttackforWeylAlgebras......

B.4IntelligentLinearAlgebraAttackforWeylAlgebras

DataExamples

C.1

C.2

C.3

2Chapter

4Chapter

6Chapter

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

ix

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Contents

.

.

.

.

.

.

.

.

.

.

166.

168.

173

173.

174.

178.

Contents

x

Notations

K,Fp,QFields
Pacommutativepolynomialring
x1,:::x,nindeterminates
TnthesetoftermsofpolynomialringP,theK-basisofP
AnWeylalgebraofindexn
¶1,:::¶,nadditionalindeterminatesforaWeylalgebra
BnthesetofWeyltermsofA,theK-basisofA
orderingstermtΣnumberprimepunitxtplaintemunitxtciphertecdcdegreeoftheciphertextc
GthesecretkeyorthesetofelementsofaGr¨obnerbasis
OΣ(I)isthecomplementofLTΣ(I)
GthetupleofelementsinG
HthesetofelementsofapartialGr¨obnerbasis
HthetupleofelementsinH
Qthepublickey
I,J(left)idealsofA
IT,JTtwo-sidedidealsofA

xi

xii

ofList

PKC

SKC

PCC

CAS

CGBC

CGBC

GBC

GBC

RSA

LAA

ILAA

WGBC

WGBC

TWGBC

TWGBC

viationsAbbre

PublicKeyCryptography

SecretKeyCryptography

CryptosystemerCrackPolly

SystemAlgebraComputer

CommutativeGr¨obnerBasisCryptosystem

Basisobner¨GrCryptosystem

AdlemanShamirestvRi

AttackAlgebraLinear

AttackAlgebraLinearIntelligent

(left)WeylGr¨obnerBasisCryptosystem

Two-SidedWeylGr¨obnerBasisCryptosystem

xiii

vxi

1Chapter

Introduction

Thedistanceisnothing;itisonlytherststepthatisdifcult.
ymousAnon

ThedevelopmentandstudyofGr¨obnerbasiscryptosystemsisanactiveareaofre-
searchintheGr¨obnerbasiscommunity.Itisbelievedthatifsuchcryptosystemsare
develop