; TeX output 2001.08.05:2033Y!vފDፑssrc:44ip7long.texgG cmmi12C=!", cmsy10 XQ cmr12+sNG cmbx12andz}h!G cmsl12HM:VaGariationsaroundtuwozschemesofjT.zMatsumotoandH.ImailύXQ ff cmr12-/ExtendedV4ersion-5JacquesPratarin,LouisGoubin7.BULLSmartcardsandTVerminals68routedeVVersailles-BP45278431LouvreciennesCedex-FVrancere-mail:8fJ.Pratarin,L.Goubing@frlv.bull.frENicolasCourtois[SystrsemesInformationSignal(SIS)vUnivrersitsedeTVoulonetduVar-BP132 cmmi10C^ O!cmsy7P,(andwasbasedontheideaofhidingamonomial eldequation.Thisjschemewasbrokenin[8]byJacquesPatarin,duetounexpGectedalgebraicproperties..J.PatarinandL.Goubinthensuggested([9],'[10 ],[11],[12])someschemestorepairC^P,'butthiswasdoneatd&thecostofslightlymorecomplexpublickeyorsecretkeycomputations.;InpartId"ofthispapGer,we{OwillstudysomeverysimplevqariationsoftheC^ Oscheme,wheretheattackof[8]isavoided,andhwheretheverysimplesecretkeycomputationsarekept.wTheC^ٓRcmr7+L!schemewillbGeoneofthesevqariations.W*eohwilldesignsomenewcryptanalysisthatareecientagainstsomeof{butnotall{theseUUvqariations.src:49ip7long.texAnotherg schemeof[4],kvverydi erentfromC^ (despitethename),kvwascalled[C]andwasbasedonYtheideaofhidingamonomialmatrixequation.mNocryptanalysishasbGeenpublishedsofarforthisрscheme.EInpartIGI^ofthispaper,wewillshowhowtoattackthisscheme[C].EW*ewillthenstudymore"generalschemes,stillusingtheideaofhidingmatrixequations./Thep0J cmsl10HMlschemewillbGeoneofUUthesevqariations."AQ Nff cmbx121gIntros3ductionqQsrc:54ip7long.texK`y 3 cmr10Whatzis{atthepresen!t{theasymmetricsignaturealgorithmwiththemostsimplesmartcardimple-Qmen!tationf(intermsofspMeedandRAMneeded),andnotbroken?Qsrc:56ip7long.texWeethinkthatitisonesimplevdDariationoftheMatsumoto-Imai! b> 3 cmmi10CȁK cmsy8 \algorithmthatw!ewillpresentQin"thepartIofthispapMer..TheCȁ Ialgorithmw!aspresentedin[4y]and[7],andw!asbrokenin[8y],QdueItounexpMectedalgebraicproperties.mHo!wever,AitIispossibletoimagineman!ywaysofavoidingtheQcryptanalysisfof[8y].Qsrc:58ip7long.texIn[9y],4J.P!atarinsuggestedtousea"hiddenpMolynomial"insteadofa"hiddenmonomial".These"HFE"Qalgorithms.arestillun!broken.However,F(the.secretk!eycomputationsinHFE-schemesaresensiblymoreQcomplexthanintheoriginalCȁ qsc!heme.In[10 4],[11]and[12 4],J.P!atarinandL.GoubinalsostudiedQsomegvdDariations,&wherethepublicequationsaregiv!enindi erentforms(someoftheseschemesareQalsovpresen!tedin[5y]),zbuthereagain,inordertoa!voidvtheattac!ks,thesecretk!eycomputationsortheQpublicfk!eycomputationsaregenerallyslightlymorecomplexthanintheoriginalCȁ .scheme.Qsrc:60ip7long.texInEpartIEofthispapMer,Xw!ewilldesignandstudyafewverysimplevdDariationsoftheoriginalCȁ scheme.QWeewillk!eepaquadraticpublickeyandthemainsecretkeyopMerationswillstillbethecomputationQofamonomialfunctionf):Jxm"!", 3 cmsy107!x2cmmi8h `ιina nite eld.C(Thelengthoftheelemen!tsofthis nite eldis!1*Y!vފ Qm!uch]shorterthanwhatw!ehaveinRSA,andthisexplainswhytheimplementationsaremuchmore Qecien!t.)Qsrc:62ip7long.texSomeXofthenewvdDariationswillbMebrok!eninthispaper.Ho!wever,asXwewillsee,therearestillsomeQv!erysimpleandecientvdDariationsthatwedonotknowhowtobreak.TheseschemesarerelatedtoQsomeY problemsoforthogonalpMolynomials(ho!wtocompleteasetoforthogonalpolynomials,ho!wtoQeliminatefsomerandompMolynomialslinearlymixedwithorthogonalpolynomials,etc).Qsrc:64ip7long.texItcanbMenoticedthatallthev!erysimpletransformationsthatwewillstudyinthecaseoftheCȁQsc!heme,canXValsobMeappliedtothemoregeneralHFEX(schemeof[9y].WeeconcentrateonCȁ ۹bMecauseQthefsecretcomputationsofCȁ }areparticularlyecien!t, &andbMecausewewantedtoseeifthesesimpleQideas0couldbMesucien!tornottoenforcethesecurity(inHFE,theanalysisismoredicultsincenoQecien!tfattacksareknownatthepresent).Qsrc:66ip7long.texInBpartIMIAofthispaper,V"w!ewillstudyaverydi erent(despitethename)algorithmof[4y],V"called[Cȁ].kItQisbasedontheideaofhiding(withsecretanetransformations)amonomialmatrixequation.T%SinceQtheSm!ultiplicationofmatricesisanon-commutativeopMeration,~KitcreatesaschemewithveryspMecialQfeatures.~Ho!wever,TasinCȁ vorHFE,thepublick!eyisstillgivenasasetofmultivdDariatepMolynomialsQonfa nite eld,andsomeoftheideasusedin[8y]willalsobMeuseful.Qsrc:68ip7long.texWee willsho!whowtobreaktheoriginal[Cȁ]sheme(nocryptanalysisofthisschemewaspublishedQbMefore).IWeewillthenstudysomemoregeneralsc!hemes,3=basedonthesameideaofhidingmatrixQequations.Qsrc:70ip7long.texSinceSalltheun!brokenSalgorithmspresen!tedinthispapMerarenewandverysimilartobrokenalgorithms,Qw!e#ycertainlydonotrecommendtousethemforverysensibleapplications.UHowever,BwebMelievethatQit1isnicetostudythembMecausetheyha!ve1veryecientimplementationsandbMecausetheyprovideQaZbMetterunderstandingofthesubtlelinksbet!weenZtheconceptofasymmetriccryptosystemandtheQcomputationsfrequiredforsecurit!ye.$۸Qsrc:72ip7long.texPartffIQ#Nq cmbx12V=ariations around%gq cmmi12C}Ny?(!",ff cmsy10 $ʍQ2gAffshortdescriptionofHFEand&gff cmmi12C= !", cmsy10qQsrc:76ip7long.texWeenpresen!tashortdescriptionoftheHFEnandCȁoschemes.^See[7y](forCȁ),zor[9](forHFE)nformoreQdetails.ōQ)"V 3 cmbx10The2quadraticfunctionfDsrc:79ip7long.texLetfK(= F zq2ubMea nite eldofcardinalit!yqd.LetFzqI{;cmmi6n Ybeanextensionofdegreeno!verfFzq.Let`i|f-(a) =C0u cmex10X 7ʍi;jO zi;j XazqI{Nij t|{Ycmr8+qI{N'ij(M8+nC0X |Vk Ȯk#azqI{ k<+n2FzqI{n 5[a]ЍQsrc:81ip7long.texbMefapolynomialinao!verfFzqI{n 5,ofdegreed,forin!tegerszijJ,'zij JandȮk 0.Qsrc:83ip7long.texSincemFzqI{n isisomorphictoF[x]=(gd(x)),ifg(x)2Fzq[x]misirreducibleofdegren,elemen!tsofFzqI{n mayQbMeSrepresen!tedasn-uplesoverFzq,d\andfmaybMerepresentedbynpMolynomialsinnvdDariablesaz1,d\...,aznQo!verfFzq:p}Nf-(az1;1:::;aznP) =(fz1(az1;1:::;aznP);:::;fzn(az1;:::;azn)):્Qsrc:85ip7long.texThefziarequadraticpMolynomials,/duetothec!hoiceoffùandthefactthata7!aqDisalineartransfor-QmationfofFzqI{n 5.QSecret2anetransformationoffDsrc:89ip7long.texLetLsandtbMet!woLsecretanebijections(Fzq)n! (Fzq)nP,whereL(Fzq)n_isregardedasann-dimensionalQv!ectorfspaceoverFzq.Qsrc:91ip7long.texUsing̤thefunctionf`abMo!ve̤andsomerepresen!tationofFzqI{n ٹoverFzq,3thefunction(Fzq)n!Jc(Fzq)n tthatQassignsft(f-(s(x)))tox 2(Fzq)n NcanfbMewrittenas'at(f-(s(xz1;1:::;xznP))) =(pz1(xz1;1:::;xznP);:::;pzn(xz1;:::;xzn));!2נY!vފ Qsrc:93ip7long.texwherefthepzi @arequadraticpMolynomialsduetothec!hoiceofs,tandf-.\QThe2"basic"HFE(cf[9K]) Dsrc:97ip7long.texQPublic2ktey:%src:98ip7long.texThefpMolynomialspzidڹ,fori =1;12;:::;n,fasabo!ve.QSecret2ktey:%src:101ip7long.texTheffunctionf"andthet!wofanebijectionssandtasabMo!ve.QEncryption:Zsrc:104ip7long.texTeoencryptthen-uplexV=(xz1;1:::;xznP),Mcomputetheciphertexty=V(pz1(xz1;1:::;xznP),M...,QpznP(xz1;1:::;fxzn))(xshouldha!veredundancye,orahashofxshouldalsobMesent).QDecryption:`src:107ip7long.texTeoٱdecryptyd, rst ndallthesolutionszTtotheequationf-(z{I)`$=t1 \|(y)ٱb!ysolvingaQmonotvLariate`=pMolynomialequationofdegreed. cThisisalw!ays`=feasiblewhendisnottoolarge(sa!yQd 10008forexample)orwhenfhasaspMecialshape(asw!ewillseebelo!winthecaseoftheCȁrscheme).QNext,fcomputeallthes1 \|(z{I),andusetheredundancy(orthehashofx)to ndMfromthese.QThe2"basic"HFEinsignatureDsrc:111ip7long.texHFE~^can~halsobMeusedinsignature,hasexplainedin[9y](essen!tiallye,theideaisthatno!wxwillbMetheQsignatureyandy thehashofthemessagetobMesigned.َIftheequationf-(z{I) =t1 \|(yd)yhasnosolutionz,Qw!efcomputeanotherhash).QThe2Cȁ algorithm(cf[7K])Dsrc:115ip7long.texCȁpcanbMeseenasaspecialcaseofthemoregeneralHFEsc!heme,7wherethefunctionfisf-(a) =a1+qI{-:.Qsrc:117ip7long.texSuc!hafunctionfžhassomepracticaladvdDantages:ifK]cisofcharacteristic2andif1K+qdiscoprimetoQqdnr1,thentf0isabijection,andthecomputationoff-1 8(b)iseasysincef-1(b)=bh-:q% cmsy60,whereth0zistheQin!versefof1n+qdmoMdulofqdn{1.Qsrc:119ip7long.texHo!wever,Tthe_Cȁ vschemewasbrokenin[8y],TessentiallybMecause{inthecaseofaCȁ vscheme{thereQalw!aysfexistequationssuc!hasVlVC0X 7ʍni;j| zijJxzidyzj+nC0X 7ʍ5di zixziƹ+nC0X 7ʍj zjf yzj+nz0ʫ= 0d(1)k%Qsrc:121ip7long.texfrom(swhic!hitispMossibletobreakthescheme(see[8y]).d(Herexisthecleartext(orthesignature),HyQisCtheciphertext(orthehashofthemessage),zand zijJ, zidڹ, zi andz0{Gareelemen!tsofKȁ.)uThroughoutQthisfpapMer,w!ewillcall"equationoftypMe(1)"anyequationlike(1).Qsrc:123ip7long.texIn3thecaseofHFE,nocryptanalysishasy!etbMeenfound(whenfaViswellchosen),VbutthesecretkeyQcomputationsfaremorecomplex.!𼍍Q3gThreeffsimplevariationsofC= %(andHFE)񍍑Q-N cmbx123.1 Lesspublicp`olynomialsQsrc:129ip7long.texThe5pMolynomials(Pz1;1:::l;1PznP)ofthe"basic"HFEalgorithmgiv!eygȹfromx.IHowever,hitispMossibletoQk!eep.someofthesepMolynomialssecret.v9LetkĹbethen!umber.ofthesepolynomialsPzi_thatw!edonotQgiv!efinthepublickeye,sothatonlyPz1,Pz2,...,PȮnkarepublic.Vlsrc:136ip7long.texInhanencryptionsc!heme,u kmusthbMesmall,bMecauseinordertoreco!verhxfromyd,w!ewillcomputetheqdk pMossibilitiesforyd,-computeallthecorrespondingpossiblex,-and ndthegoodxthankstoftheredundancye.dsrc:140ip7long.texWhenOqisnottoMolarge,=andwhenkwisv!erysmall,forexamplewithk,i=*1or2,thisisclearlyfeasible.i.lsrc:144ip7long.texIn4asignaturesc!heme,'kVsmay4bMem!uch4larger.FHowever,we4muststillhaveenoughpMolynomialsPziEinkorderthattheproblemof ndingavdDaluex,jwhoseimagesb!yPz1,...,PȮnkkŹaregiv!envdDalues,isfstillin!tractable.AvdDaluekb= 1,2,ork=K=n=ڟfe(PPAt&2?ùforexamplema!ybMepracticalandecient.!3*`Y!vފ QNote:]src:150ip7long.texThisideatok!eepsomepMolynomialsPziusecretmayincrease,ksignature,ditiseasytoin!troMducemorexzivdDariables.(Ina"basic"HFE>scheme,dwehaveb=f-(a),Qwhere:i f-(a) =C0X 7ʍi;jO zijJazqI{Nij t+qI{N'ij(M8+nC0X 7ʍ5di zidazqI{-:i+nz0;_(1)Qsrc:183ip7long.texwheref zijJ, zi @andz0fjareelemen!tsofLznP.Qsrc:185ip7long.texLetfa0= (a0g1;1:::;a0'͍k#)bMeakX?-upleofvdDariablesofKȁ.Qsrc:187ip7long.texIn\(1),letno!w zi:6bMeanelementofLzn }suchthateachofthencompMonentsof zi:6inabasisisasecretQrandomflinearfunctionofthevdDariablesa0g1,...,a0'͍k#.Qsrc:189ip7long.texAndin(1),letno!wz0bbMeanelementofLzn JgsuchthateachoneofthencompMonentsofz0binabasisisQafsecretrandomquadraticfunctionofthevdDariablesa0g1,...,a0'͍k#.Qsrc:192ip7long.texThen,thekn,+kݪvdDariablesaz1,...,aznP,a0g1,...,a0'͍k#,willkbMemixedinthesecretanebijectionsinordertoQobtainfthevdDariablesxz1,...,xȮn+kZ.Qsrc:194ip7long.texAnd,fasbMefore,t(bz1;1:::;bznP) =(yz1;1:::;yznP),fwheretisasecretanebijection.Qsrc:196ip7long.texThenfthepublick!eyisgivenasthenequationsyzio= Pzidڹ(xz1;1:::;xȮn+kZ).Qsrc:198ip7long.texTeo6computeasignature,ZthevdDaluesa0g1,...,a0'͍k ZQwillsimplybMec!hosenatrandom.Then,thevdDaluesz0Qandf zi @willbMecomputed.Then,themono!vdDariateequation(1)willbesolv!ed(ina)inLznP.QNote:%src:202ip7long.texThisfidea,asbMefore,ma!yormaynotincreasethesecurityofsomeschemes.!4?Y!vފ"!uQ4gFirstffremarksabs3outC=QFirstexampleofattack(withthebirthdayparadox)Qsrc:207ip7long.texFeor2hexample,Uhletusassumethatw!ehaveaMatsumoto-ImaialgorithmwithK=Fz2;1n=64;f-(x)=Qx1+2-:. Qsrc:211ip7long.texSofw!ewillhave64publicpMolynomialsPz1;1Pz2;:::l;Pz64 .Qsrc:213ip7long.texThisfalgorithmcanbMeattac!kedfassho!wnin[8y].Qsrc:215ip7long.texNo!w letusassumethatPz64 iskeptsecret.Decryptionofamessage(withthesecretkey)isstillpMossibleQasfollo!ws:wewilltrythetwopMossibilitiesforPz64 ,,sowewill ndexactlytwosolutionsforthecleartextQx,fandthankstoredundancyinx,therigh!txwillbMefound.Qsrc:221ip7long.texIsfthissc!hemesecure?No.Qsrc:223ip7long.texTeofattac!kthisscheme,wecanproMceedlikethis:8덍1.src:225ip7long.texFind!t!wovdDaluesxandx09,x 6=x0qZsuc!hthatCȁ(x)=C(x09).By!C(x)w!emeantheencryptionofxwithfthealgorithm,i.e.ݹtheoutputofthepMolynomialsPz1;1Pz2;:::lPz63 .(2.src:228ip7long.texLetfPz64 =C1dn ύ C0X 7ʍbi=1C1n ύxC0X 7ʍOjv=1#X zijJxzidxzj+C1n ύnC0X 7ʍ&i=1zixziƹ+nz0.1 Since[oaMatsumoto-ImaialgorithmisapMerm!utation,jmwe[oknowthatPz64 (x)Pz64(x09) =1.It[ogiv!esusfalinearrelationinthecoMecien!ts zijJ;1zidڹ.r3.src:233ip7long.texGoQ@bac!kto1untilwehavefoundsucientlymanylinearrelationsin zijJ;1ziinorderto ndacandidatefPz64 nsothatPz1;1Pz2;:::l;Pz64 narefthecompMonen!tsofaperm!utationofF64g2 .4.src:237ip7long.texA!ttackfPz1;1Pz2;:::lPz64 nasfforausualMatsumoto-Imaialgorithmwiththeattac!kdescribMedin[8y].8덑Qsrc:239ip7long.texFeorfStep1,w!ewillproMceedlikethis:Qsrc:241ip7long.tex1a.6Weewillcomputeandstoreina leFV,sa!y232 pairs(x;1Cȁ(x)).(Ifthisstoragecapacit!yisnotQa!vdDailableIthensometime/memorytradeo arepMossible:mwewillneedlessstoragebutmoretime).TheQstoragefisdoneinaw!ayftoha!vefeasyaccesstoxwhenCȁ(x)isgiv!en.Qsrc:247ip7long.tex1b.ɹNo!wwegenerateandcompute2k Gnewpairs(x09;1Cȁ(x0)),Hwherekisanin!tegerthatwewill xQafterw!ards.$Feor eachofthesepairs,theprobabilitythat9xܷ2FCasuc!hthatCȁ(x)=C(x09) isabMoutQ1=232 .(ThisisbMecausesincetheMatsumoto-Imaialgorithmisaperm!utation,thereisexactlyonex,Qx6=x09,%hso thatCȁ(x)=C(x09),%hit isthevdDaluexwiththesamePz1;1:::l;1Pz63 andtheoppMositePz64 .AndQthe=probabilit!ythatthisxisinFisabMout232 =264 =1=232 =ѹbecausethereareabout232 =ѹvdDaluesinFQandf264 npMossiblevdDaluesforx).Qsrc:261ip7long.texSofthen!umbMerfofx;1x09;x 6=x0,fsothatCȁ(x) =C(x09)fthatw!ewillfoundisabMout2k#=232 = 2k632@.Qsrc:264ip7long.texSofifw!eonlyneedonesuchpair(x;1x09),wecanhavekb' 32.Qsrc:267ip7long.texHereenw!eneedafewofthesepairsandkwillbMeslightlybiggerthan32,0buttheattackwillbMeveryQecien!t.@JQAnattackthatdo`esnotworkQsrc:271ip7long.texInj6ordertoa!voidj6theattac!kgivenabMove,*onecansuggesttohavemessagesofatleast128bits(i.e.Qn 128tifK(= Fz2),~and/ortok!eepsecretmorethanonebitoftheoutput(forexampletokeepsecretQatfleastt!wofpMolynomialsifK(= Fz2).Qsrc:276ip7long.texHo!wever,evenXwiththesetransformations,w!edonotrecommendtousesuchascheme,sincewewillQseeTinsection5ho!wtoattacksuchascheme.©But,ebMeforethis,w!ewillshowhereanideaofattackthatQdoMesfnotw!ork.Qsrc:279ip7long.texInthecryptanalysisofMatsumoto-Imaisc!hemegivenin[8y],thekeyideaistocomputeallthe"equationsQofft!ypMe(1)",i.e.ݹsuchas:g6oC0Xw{i zijJxzidyzj+nC0X zixziƹ+nC0X ziyziƹ+nz0ʫ= 0 ٟ(1):iݍQsrc:284ip7long.texHo!wever,ݰasҡwewillseeinthesimulationsbMelow,ݰwemaynot ndenoughsuchequationsforacrypt-QanalysisfifsomepublicpMolynomialsofMatsumotoandImaiarek!eptsecret.!5YY!vފ W܍Qsrc:288ip7long.texNev!ertheless6'onecansuggest,Zinsteadofcomputingtheseequations(1)tocomputealltheequations Qsuc!hfas:ύ"|C0X2Ȯijvk vxzidxzjf xȮk~+nC0XzijJxzixzj+nC0X zixziƹ+nC0X ziyziƹ+nC0X zijJxziyzj+nz0ʫ= 0:j(1z09): yQsrc:294ip7long.texThese>Jequations(1')willbMecomputedasusual,Csinceeac!hpair(cleartext/ciphertext)giveslinearQequationsfinthecoMecien!tsȮijvk v;1zijJ; zid; zi; zijJ;z0.Qsrc:298ip7long.texSofaftersomeGaussianreductionsallthevdDalidequations(1')willbMefound.Qsrc:301ip7long.texMoreo!verEalltheno!wsecretexpressionsinyziHarepMolynomialsofdegreetwointhexziHvdDariables,}soforQeac!hbNequation(1)oftheoriginalMatsumoto-Imaischemethereisoneequation(1')oftheschemewithQlessfpublicpMolynomials.Qsrc:306ip7long.texSo4}alotoftheseequation(1')alw!ays4}exist."Feromtheseequations(1')onecanthinkthat,Xma!ybMe,aQcryptanalystOwillbMeabletoreco!verOtheexpressionofthesecret(originalypublic)polynomialslinearinQyzidڹ.Qsrc:312ip7long.texHo!wever,2thisģattackdoMesnotwork,2andtheexistenceoftheseequations(109)isnotaproblemfortheQsc!heme,faswewillseebMelow.Qsrc:314ip7long.texThev!ectorspaceoftheequations(109)isofdimensionatleastn2+n,sinceallyzidڹ,1 in,andQallyNxzidyzjf ,1j(in,1j n,canyNbMewrittenaspolynomialsofdegree2or3inthexȮk vdDariables.QMoreo!ver,the4dimensionisexactlyn2`Ϲ+n,sinceifitw!asmorethann2`Ϲ+n,b!yGaussianreduction,Qw!etwouldobtainanequation(109),7sayPV,7withonlytermsinthexȮk vdDariables.SinceP(xz1;1:::;xznP)=0Qforfan!y(xz1;1:::;xznP),fwewouldthushaveP= 0.Qsrc:316ip7long.texItristhereforeeasytoseewhattheequations(109)are:ctheycanbMeseenastheexpressionaspolynomialsQofAdegree3inxȮk doftheyziandxzidyzjf .Asaresult,gtheycanbMeobtainedimmediatelyfromthepublicQk!eyx(i.e.fromtheyzj expressions).Thereisth!usagreatdi erencebMetweenequations(1)and(109):Qequations(1)aretrueonlyforsomev!erysimpleandveryspMeci cquadraticfunctionsy3f(asintheCȁQsc!heme),lkwhereasDequations(109)alwaysexist,lkevenforrandomquadraticfunctionsyd.Therefore,lktheQexistencefoftheseequations(109)(unlik!eequations(1))isnotadangerousthreatfortheschemes."AQ5gTfoyffsimulationsofC=+twithn=17qQsrc:320ip7long.texWeeha!vemadesometoysimulationswithKĺ=9Fz2 andn=17oftheCȁA+algorithm.](TheseareQjust_"to!y"simulationsbMecauseherethevdDalueofnisverysmall.Inrealexamples,^nmustbMeF64ifQK(= Fz2).Qsrc:322ip7long.texIngallthesesim!ulations,tYweghavecomputedtheexactnumbMerofindependen!tequationsbet!weenthe16Qbitsfoftheinputxz1,...,xz16 ,andthe16bitsoftheoutputyz1,...,yz16 nofthefollo!wingform:hɟC0Xy zijJxzidyzj+nC0X zixziƹ+nC0X ziyziƹ+nz0ʫ= 0 ٖ(1)Qsrc:324ip7long.texor #:2,973)anyequationlike(1),97(resp.>:(2),Q(3)).QNote1:src:333ip7long.texInbthesetables,0w!ehavesubtractedthenumbMerofindependen!t"trivial"equations,0suchasQx2|iʫ= xzidڹ,foryzi"yzjf "="yzi"yzj,fwhere"yzi"and"yzjf "arewrittenwiththeirexpressioninthexȮkvdDariables.QNoteXj2:Ksrc:336ip7long.texTheRnotation[ `]meansthat,ώwhentheyȮkvdDariablesaregiv!enexplicitvalues,ώw!eobtaininQa!veragef ƹindepMendentequationsinthexȮkvdDariables.Qsrc:340ip7long.tex(InfthetablesbMelo!w,wealwayshaveK(= Fz2fjandn=17.)!6p͠Y!vފ7s%src:343ip7long.texviff˱E ͤ} ffΟCȁ .: 2f-(x)ۡ ffcezx3Vn} ffx5Vn} ffА*x9Vn} ffx17vp} ff;x33vp} ffr00x65vp} ffx129r} ffzff˱Eͤ} ffΟ냹Equationsf(1)͡ ffYw34f[16] Fg} ff17f[16] Fg} ff@'17f[16] Fg} ff17f[16] Fg} ff3j17f[16] Fg} ffj/17f[16] Fg} ff17f[16] Fg} ffff˱Eͤ} ffΟEquationsf(2)͡ ffVX612f[16]} ff340f[16]} ffÃZ323f[16]} ff340f[17]} ff0 323f[16]} ffgCb374f[16]} ffغ323f[16]} ffff˱Eͤ} ffΟEquationsf(3)͡ ffS578f[153]͟} ff15442f[153]͟} ffƍ476f[153]͟} ff[493f[153]͟} ff-=476f[153]͟} ffd459f[153]͟} ff493f[153]͟} ffff˱Evesrc:349ip7long.tex ʓ*T\able21(%src:353ip7long.texviff˱E ͤ} ffΟCȁg+1Z: 2f-(x)l ffcezx3Vn} ffx5Vn} ffА*x9Vn} ffx17vp} ff;x33vp} ffr00x65vp} ffx129r} ffzff˱Eͤ} ffΟ냹Equationsf(1)͡ ffYw17f[15] Fg} ff$i1f[1]} ff˹1f[1]} ffO1f[1]} ff8q1f[1]} ffoy1f[1]} ff!1f[1]} ffff˱Eͤ} ffΟEquationsf(2)͡ ffVX340f[15]} ff52f[15] Fg} ff@'36f[15] Fg} ff36f[15] Fg} ff3j36f[15] Fg} ffj/87f[15] Fg} ff36f[15] Fg} ffff˱Eͤ} ffΟEquationsf(3)͡ ffS443f[153]͟} ff15307f[152]͟} ffƍ341f[153]͟} ff[358f[153]͟} ff-=341f[152]͟} ffd324f[152]͟} ff358f[153]͟} ffff˱Esrc:359ip7long.texʓ*T\able22(%src:363ip7long.texviff˱E ͤ} ffΟCȁg+2Z: 2f-(x)l ffcezx3Vn} ffx5Vn} ffА*x9Vn} ffx17vp} ff;x33vp} ffr00x65vp} ffx129r} ffzff˱Eͤ} ffΟ냹Equationsf(1)͡ ff^1f[1]} ff$i0f[0]} ff˹0f[0]} ffO0f[0]} ff8q0f[0]} ffoy0f[0]} ff!0f[0]} ffff˱Eͤ} ffΟEquationsf(2)͡ ffYw54f[13] Fg} ff$i0f[0]} ff˹0f[0]} ffO0f[0]} ff8q0f[0]} ffoy0f[0]} ff!0f[0]} ffff˱Eͤ} ffΟEquationsf(3)͡ ffS309f[151]͟} ff15173f[135]͟} ffƍ207f[151]͟} ff[224f[152]͟} ff-=207f[150]͟} ffd190f[152]͟} ff224f[153]͟} ffff˱Esrc:369ip7long.texʓ*T\able23(&)src:373ip7long.texviffq= ͤ} ffΟCȁg+3Z: 2f-(x)l ffcezx3Vn} ff'x5:} ffx9:} ffx17֟} ff0x33<} ffcx65<} ffOx129؟} ffzffq=ͤ} ffΟ냹Equationsf(1)͡ ff^0f[0]} ffQ50f[0]͟} ff@%0f[0]͟} ff0f[0]g} ff-90f[0]͟} ff`)0f[0]͟} ff0f[0]g} ffffq=ͤ} ffΟEquationsf(2)͡ ff^0f[0]} ffQ50f[0]͟} ff@%0f[0]͟} ff0f[0]g} ff-90f[0]͟} ff`)0f[0]͟} ff0f[0]g} ffffq=ͤ} ffΟEquationsf(3)͡ ffS176f[153]͟} ffכ51f[68] s3} ffƋ74f[91] s3} ff{91f[108]͟} ff(w74f[91] s3} ff[f57f[74] s3} ffU91f[108]͟} ffffq=src:379ip7long.texʓ*T\able24( `src:383ip7long.texviffϤ ͤ} ffΟCȁg+4Z: 2f-(x)l ffaFx3:} ffx5} ffijXx9} ffx17} ff$x33} ffUx65} ffx129q} ffzffϡͤ} ffΟ냹Equationsf(1)͡ ff\0f[0]͟} ff30f[0]3} ff0f[0]3} ff0f[0]3} ff"g0f[0]3} ffS0#0f[0]3} ffx0f[0] 0} ffffϡͤ} ffΟEquationsf(2)͡ ff\0f[0]͟} ff30f[0]3} ff0f[0]3} ff0f[0]3} ff"g0f[0]3} ffS0#0f[0]3} ffx0f[0] 0} ffffϡͤ} ffΟEquationsf(3)͡ ffWBC44f[61] s3} ffי0f[17] s3} ffU0f[17] s3} ff0f[17] s3} ff!*0f[17] s3} ffRF0f[17] s3} ffbE0f[17]͟} ffffώsrc:389ip7long.texʓ*T\able257NQsrc:392ip7long.texAs9sho!wninthesetables,ntheattacksof[8y]donotworkdirectlyifwehavelesspublicpMolynomials,natQleastfiff-(x) =x3fjisfa!voidedandiftwoormorepMolynomialsarekeptsecret.!Q6gFirstffcryptanalysisofC=qQPrinciple2oftheattactkDsrc:397ip7long.texWeedenoteb!yP>)thecompletepublicformofCȁ.#WesuppMosethatthe rstrpublicequationsha!veQbMeenfremo!ved.LetP:u(r:(B#s(t)+):src:427ip7long.texSincefx 6=x09,thisimplies:r(s(xz0=%nx)+)z2-:FeromfthecryptanalysisofCȁ,w!eknowthatthereexistequationsoftheformR1C0X 7ʍji;j+ zijJxzidyzj+nC0X 7ʍ5di zixziƹ+nC0X 7ʍ5di ziyziƹ+nz0ʫ= 0: }src:459ip7long.texi.e.ݹ(withfthenotationsabMo!ve):vC0X 7ʍ!Oi;j/* zijJxzi%@~dyzj++nC0X 7ʍ5di zidxziƹ+nC0X 7ʍ5di zi%@~yzi+nz0.+C0X 7ʍ5diC1 r ύEC0X 7ʍjv=1#I zijJxzi 0C0X | kuȮk6j xȮk# b+C1r ύC0X 7ʍ&i=1 zi 0C0X | kuȮk6ilxȮk#'= 0:"эsrc:461ip7long.texIfw!ereplace:~yzj by;jz&~ĖPzjt(xz1;1:::;xznP)andifweconsiderthetermsoftotaldegree3inthexzidڹ,&weobtainn(n1)(n2)ӟʉfe2j؟PAj6>equationsj;onthen2 *?indeterminates zijJ,0whic!hcanthusbMedeterminedbygaussianreductions.ȍsrc:463ip7long.texWeed6thenconsiderthetermsoftotaldegree2inxzidڹ,qsandthatgiv!esin(n1)iʉfeɔPA 2$fequationsontherMnꍹ+nindeterminatesfȮk6j and zidڹ.7.src:466ip7long.texOnce>Pz1,y...,Pznbarecompletelykno!wn,theclassicalattac!konCȁBùcanbMeapplied,sothatCȁA ֶ(whenrisgsmall)isalsobrok!en.ThecomplexityofthiscryptanalysisisinOM޹(qdr)plusthecomplexityofthefcryptanalysisoftheoriginalCȁ .sc!heme.QRemark:src:470ip7long.texThiscryptanalysisusesdeeplythefactthatCȁ isapMerm!utationpolynomial.&AgeneralQtheoryl[abMoutperm!utationpolynomials,wandtherelatednotionoforthogonalsystemsofequations,canQbMeffoundin[6y],c!hapter7."&ٍQ7gTheffC=talgorithmqQsrc:474ip7long.texWhenaqdr 8A264 ,thenthecryptanalysisgiv!eninsection6isnotecient. TheschemeisthencalledQCȁA .TheCȁAιsc!hemecannotbMeusedforencryptionsanymore,7butthisschemeisstillaveryecientQsc!hemefforsignatures,anditssecurityisanopMenproblem.Q8gCryptanalysisffofC=+qQsrc:478ip7long.texThecryptanalysisofCȁA+ (isv!erysimple:qitjustworksexactlyastheoriginalcryptanalysisofCȁ.WeeQwillf rstgeneratealltheequations`hwC0X 7ʍji;jxMq zijJxzidyzj+nC0X 7ʍ5di zixziƹ+nC0X 7ʍj zjf yzj+nz0ʫ= 0:30(1) }Qsrc:480ip7long.texSince/inCȁA+x,!w!ejusthaveaddedsomeequations(andeliminatednone),!wewill ndatleastasmuchQequationsf(1)asintheoriginalCȁ.Qsrc:482ip7long.texThen,Uasexplainedin[8y],fromsuc!hequations(1)wewillbMeableto ndxfromy"(andthustobreakQthefsystem).QRemark1:src:485ip7long.texMoreo!ver,wewillbMeabletoeliminatetherandomaddedequationsandtoreco!veranQoriginal׵Cȁ,bMecauseanequation(1)generallycomesfromonlytheyzi 10.QCan2wterecoverthecorrespYondingCȁA OfromCȁA+}?Dsrc:541ip7long.texThisY5issometimefeasible.IFeorexample,whenw!ehaveequationsoftypMe(2)(thisisgenerallytheQcasezonlywhenrXisv!erysmall:$seethetables),>thentheseequationsgenerallycomefromyȮk vdDariablesQoftheoriginalCȁAx,9andnotfromtheaddedrandomquadraticequations.>Therefore,b!yloMokingattheQtermsinfactorofamonomialxzidxzjainthoseequations(2),Fw!ewill ndthevectorspacegeneratedbyQtheRpublicequationsoftheoriginalCȁA ʹequations.(Theninsuc!hacasetheCȁA+MBalgorithmcanbMeQattac!kedfasaCȁA ޹algorithm.)QRemark:)src:544ip7long.texOneʩcanthinktoalsousethisideaonequationsoft!ypMe(3)insteadofequationsoftypMe(2).QHo!wever,L there5uisatec!hnicalproblemwiththeequationsoftypMe(3):etheseequationsare"mixed"withQ"trivial"iBequationsyzid"yzjf "="yzi"yzj,u|whereiB"yzi"and"yzjf "arewrittenwiththeirquadraticexpressioninQtheaxȮk VvdDariables.Anditisnotclearho!wthese"trivial"equationscanbMeremoved.ThisiswhyweQha!vefusedequations(2)instead.$۸Qsrc:546ip7long.texPartffIs3IQScZhemes withahiddenmatrix $ʍQ10 Theff[C]schemeqQsrc:550ip7long.texInr5thissection,|w!erecallthedescriptionofthe[Cȁ]scheme,|presentedbyH.ImaiandT.MatsumotoinQ[4y].Qsrc:552ip7long.texLetKTA=GFV(2mĹ)bMeapublic nite eldofcardinalit!yqS=2mĹ.?Thebasicideaistousethetransfor-QmationfA 7!A2fjofthesetMz2(Kȁ)ofthe2n2matriceso!verthe eldKȁ.Qsrc:554ip7long.texThistransformationisnotone-to-one,}butitcanbMemadebijectiv!eifwerestrictourselvestomatricesQwithfanon-zerotrace:QLemma21"src:557ip7long.tex/': 3 cmti10LpetE_= fMGFV(2mĹ) !GF(2mĹ) > 7!2m.e-11 Y!vފ QProYof:%src:566ip7long.texLetfBK2 E.lsrc:569ip7long.tex>FeromfCa!yley-Hamiltontheorem(appliedtoB),wehave:CMBz2n(tr 2uB)B+(det۽B)I柹= 0src:571ip7long.texandfth!us(B+n6cp n6cfe ɝdet5W(B)/rZnI)2 ƹ= (tr 2uB)B.Sinceftr(B) 6=0,fw!eobtainB+n6cp n6cfe ɝdet5W(B)/rZnI6= 0.lsrc:574ip7long.texSuppMosethatamatrixAexistssuc!hthatA2u=1qB.#ByapplyingCayley-HamiltontheoremtoA, w!efhave:GAz2.n(tr 2uA)A+(det۽A)I柹= 0src:576ip7long.texi.e.(tr 2uA)nA =B+nPq nPfe Sdet5W(B)/rZnI:\]src:578ip7long.texAsfaresult,w!ehavetr 2u(A) 6=0fandA =n(B+6cp n6cfe ɝdet5W(B)/rZI),fwhichgiveseasily:F荒XbA =v1=ڟȉfe#: ɖ6cp 6cfe9ɝtr(B)+3ngB+nPq nPfe Sdet5W(B)/rZnI: 1src:580ip7long.texReciproMcallye,fthisAisasatis esA2ʫ= B3 andtr(A)6=0.lsrc:583ip7long.texInfconclusion,isabijectiv!etransformationofE,and:!~z1 \|(B) =v1=ڟȉfe#: ɖ6cp 6cfe9ɝtr(B)+3ngB+nPq nPfe Sdet5W(B)/rZnI:&9獑QNote:%src:589ip7long.texTheffunction~xp g~xp f3iseasytocompute,sincew!ehave#p g#p c4 Nݍ4B= 2-:m1(forany 2GFC(2mĹ).Qsrc:593ip7long.texWeefno!wdescribMethe[Cȁ]schemeusedinencryptionmoMde.Qsrc:597ip7long.texTheesetMz2(Kȁ)canbMeconsideredasav!ectorspaceofdimension4overKȁ. Therefore,dwecanchoMose Qs :Kȁ4,!Mz2(Kȁ)fandt :Mz2(Kȁ)!K4 .t!wofsecretflinearbijectionssuc!hthat:lsrc:600ip7long.texsfmapstheh!ypMerplanefxz1ʫ= 0gofKȁ4 .ontothehypMerplaneftr(M1) =0gfofMz2(Kȁ);lsrc:602ip7long.textfmapstheh!ypMerplaneftr(M1) =0gfofMz2(Kȁ)ontothehypMerplanefxz1ʫ= 0gofKȁ4.QRepresenttation2ofthemessagesDsrc:607ip7long.texEac!h{messageMTisrepresentedbya4-uple(xz1;1xz2;xz3;xz4) 2Kȁ4suc!h{thatxz1ʫ6= 0.9ThemessagespaceQisfM =f(xz1;1xz2;xz3;xz4) 2Kȁ4;yxz1ʫ6=0g.QThe2quadraticfunctionfDsrc:611ip7long.texWeefthende nethefollo!wingquadraticfunctiononthemessagespace:䍒!f8c: 񩒫 ]M !M ]x 7!t(B#s(x)2)K:捑Qsrc:613ip7long.texThefh!ypMothesesmadeonsandt,togetherwithlemma1,showthatthefunctionf"isabijection.QPublicktey:xsrc:616ip7long.texThe4-uple(pz1;1pz2;pz3;pz4)of4-vdDariatequadraticpMolynomialso!verKpthatrepresen!tf-.QTheyfarede nedb!y: f-(xz1;1xz2;xz3;xz4) =(Lpz1(xz1;xz2;xz3;xz4);pz2(xz1;xz2;xz3;xz4);pz3(xz1;xz2;xz3;xz4);pz4(xz1;xz2;xz3;xz4))B#:QSecret2ktey:%src:620ip7long.texTheft!wolinearbijectionssandt.QNote:src:623ip7long.texFeor(ss(respMectiv!elyt),AtherearejGLoz3/¹(Kȁ)jsjK3jjKj =(qd3s1)(qd3qd)(q3q2$)q3(qיs1) 'qd13QpMossibilities,8instead-ofjGLoz4/¹(Kȁ)j =(qd4dz1)(qd4qd)(q4q2$)(q4q3$) 'qd16 ȹif-w!eremovetheconditionQ"sfmapsMon!toE"(respMectively"tmapsEontoM").e-12 \Y!vފ QEncryption Dsrc:627ip7long.texTeoencryptthemessageMrepresen!tedbyxR=(xz1;1xz2;xz3;xz4)R2M,computetheciphertexty'=Q(yz1;1yz2;yz3;yz4)fwiththefollo!wingformulas:+YC$y8 y>y>y< y>y>y:뙚9yz1ʫ= pz1(xz1;1xz2;xz3;xz4)9yz2ʫ= pz2(xz1;1xz2;xz3;xz4)9yz3ʫ= pz3(xz1;1xz2;xz3;xz4)9yz4ʫ= pz4(xz1;1xz2;xz3;xz4)/cQDecryptionDsrc:632ip7long.texTeofdecrypttheciphertextyo:2 M,compute:捑\&Bx =sz1 / /1Mȉfe8K 5(īp (ĉfe.Jy>y< y>y>y:뙚9yz1ʫ= pz1(xz1;1xz2;xz3;xz4)9yz2ʫ= pz2(xz1;1xz2;xz3;xz4)9yz3ʫ= pz3(xz1;1xz2;xz3;xz4)9yz4ʫ= pz4(xz1;1xz2;xz3;xz4)*ލQsrc:639ip7long.texUnfortunatelye,*/suc!hܡasystemcanalwaysbMeeasilysolvedbyusinganalgorithmbasedonGrfobnerQbases.8A!t/thepresent,!thebMestimplementationsofGrfobnerbasescansolveanysetofnquadraticQequationsVwithnvdDariableso!verVanyreasonable eldKȁ,fwhenn 16appro!ximately(cf[2y]).Therefore,Qtheforiginal[Cȁ]isnotsecure.Qsrc:641ip7long.texThis rstcryptanalysissho!wsthattheparameternmustnotbMetoosmallifw!ewanttoavoidattacksQbasedonalgebraicmethoMdsforsolvingsystemsofm!ultivdDariatepolynomialequations. =Thatiswh!yweQaregoingtodescribMeageneralizationofthesc!hemetohigherdimensions(forwhichGrfobnerbasesQalgorithmsfwillbMeunecien!t)inthenextsection."AQ12 Theffmoregeneral[C(n]schemeqQsrc:645ip7long.texWeeU}presen!thereageneralizationofthe[Cȁ]schemeofH.ImaiandT.Matsumoto,ewhichinvolvesnnQmatricesfo!verthe eldKȁ,insteadof2n2matrices.ThiscryptosystemwillbMecalled[CznP].Qsrc:647ip7long.texAsfinthecaseof[Cȁ],w!etakeapublic nite eldK(= GFV(2mĹ)ofcardinalityqo:= 2mĹ.Qsrc:649ip7long.texThe}basicideaisstilltousethetransformationA#7!A2uof}thesetMznP(Kȁ)ofthenxn}matriceso!verQthef eldKȁ.Qsrc:653ip7long.texThe;setMznP(Kȁ)canbMeconsideredasav!ectorspaceofdimensionn2overKȁ,a< >:܍yz1ʫ= pz1(xz1;1:::;x_nn2 )䰍...y_nn2 ݞ= p_nn2 (xz1;1:::;x_nn2)*ԍQDecryptionDsrc:682ip7long.texTeo&decrypttheciphertextyE)2M,Fonehastosolv!etheequationsA2=B,FwhereBm:=t1 \|(yd),FandQthenftocomputethecleartextx =s1 \|(A).Qsrc:684ip7long.texItG,isimpMortan!ttonoticethatA 7!A20isG,notabijectionanylonger(contrarytotheoriginal[Cȁ]schemeQdescribMedOinsection10).Asaresult,therema!ybesev!eralpossiblecleartextsforagiv!enciphertext.OneQsolutiontoa!voidthisam!biguousnessistoputsomeredundancyintherepresentationofthemessages,Qb!ymakinguseofanerrorcorrectingcoMdeofahashfunction(fordetails,see[9y]p.ت34,whereasimilarQideafisusedinadi eren!tscheme).Qsrc:686ip7long.texTheԠfeasibilit!yofchoMosingtherightcleartextamongthepMossibleonesisduetothefactthatthenumbMerQoffsolutionsAoftheequationsA2ʫ= B3 remainsreasonable,assho!wnintable6bMelow:H>src:689ip7long.texvkff ͤ} ff͟#fpre-images ffQ`n =2͟} ffx"n =3͟} ffn =4)} ff ffȢ#fpre-images͟} ffFn =2͟} ff;@n =3͟} ffan =4͟} ffzffͤ} ff# 0 ff\t6b} ff}252 G} ffB34440͟} ff ff/13-15} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff# 1 ff\t8b} ff}160 G} ffB22272͟} ff ff$16 N} ff0Z0b} ffE0b} ffgD672 G} ffffͤ} ff# 2 ff\t0b} ffvi42 } ff5040} ff ff/17-21} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff# 3 ff\t0b} ff360b} ff60} ff ff$22 N} ff0Z0b} ffE2b} ffgD240 G} ffffͤ} ff# 4 ff\t2b} ffvi56 } ff2240} ff ffb23-315EI} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff5-11 ff\t0b} ff360b} ff60} ff ffh/316} ff0Z0b} ffE0b} ffl{2b} ffffͤ} ff N12 ff\t0b} ff360b} ff~630 Fg} ff ffڠ> 316ʠ} ff0Z0b} ffE0b} ffl{0b} ffff6vcsrc:699ip7long.texxT\able26:RepartitionofthentumbYer2ofpre-imagesfor[CznP]otver2K(= GFV(2)ҍQNote21:%src:703ip7long.texInfthecasen =4,fthet!wofmatricesha!ving316pre-imagesare0andI.QNoteT2:src:706ip7long.texTheseZ5resultsarejust"to!ysimulations"of[CznP],)bMecauseifKչ=6TGFV(2),nm!ustbMesuch Qthatfn2ʫ 64inrealexamples.Qsrc:710ip7long.texTeofsolv!etheequationA2ʫ= B3 whenBisagiv!enmatrixofMznP(Kȁ),twomethoMdscanbeused:*lsrc:715ip7long.texTheD rstoneisbasedontheJordanreductionofmatrices,nandpro!videsapMolynomialtimealgorithmUtocomputethesquareroMotsofagiv!enmatrix. Feordetails,see[3y](chapterVIMII,Up.231). lsrc:718ip7long.texThefsecondoneisbasedontheCa!yley-Hamiltontheorem.Letusdenoteby*kiM () =zn<+n zn1̹(M1)zn1+:::+ z1(M)+ z0(M)src:720ip7long.texthefc!haracteristicpMolynomialofamatrixMhdescriptionoftheobtainedsc!heme{calledHMm{isexactlythesameasfor[CznP].3Asinsection12,Qthetransformationisgenerallynotone-to-one,butthesc!hemecanbMeusedinapracticalwaybMecauseQ{asinthecaseof[CznP]{,,then!umbMerofpre-imagesofagiv!enmatrixBremainsunderareasonableQlimit.Teablef8bMelo!willustratesthisfact(forarandomlychosenmatrixM):Ísrc:821ip7long.texvoff ͤ} ff͟#fpre-images ffQ`n =2͟} ffx"n =3͟} ffn =4)} ff ffȢ#fpre-images͟} ffFn =2͟} ff;@n =3͟} ffan =4͟} ffzffͤ} ff# 0 ff\t6b} ff}284 G} ffB39552͟} ff ff$16 N} ff0Z0b} ffE0b} ffi72 } ffffͤ} ff# 1 ff\t8b} ff}112 G} ffB12024͟} ff ff$17 N} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff# 2 ff\t0b} ffvi42 } ff6576} ff ff$18 N} ff0Z0b} ffE0b} ffi12 } ffffͤ} ff# 3 ff\t0b} ffvi32 } ff2256} ff ff$19 N} ff0Z0b} ffE0b} ffi24 } ffffͤ} ff# 4 ff\t2b} ffvi34 } ff1868} ff ff$20 N} ff0Z0b} ffE0b} ffi24 } ffffͤ} ff# 5 ff\t0b} ff360b} ff~960 Fg} ff ff$21 N} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff# 6 ff\t0b} ff360b} ff~972 Fg} ff ff$22 N} ff0Z0b} ffE0b} ffi24 } ffffͤ} ff# 7 ff\t0b} ff360b} ff~168 Fg} ff ff/23-25} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff# 8 ff\t0b} ff362b} ff~324 Fg} ff ff$26 N} ff0Z0b} ffE0b} ffi36 } ffffͤ} ff# 9 ff\t0b} ff360b} ffyK484} ff ff$27 N} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff N10 ff\t0b} ff362b} ff~144 Fg} ff ff$28 N} ff0Z0b} ffE0b} ffl{6b} ffffͤ} ff N11 ff\t0b} ff360b} ffyK964} ff ff/29-33} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff N12 ff\t0b} ff364b} ff~162 Fg} ff ff$34 N} ff0Z0b} ffE0b} ffl{4b} ffffͤ} ff N13 ff\t0b} ff360b} ffyK564} ff ff/35-39} ff0Z0b} ffE0b} ffl{0b} ffffͤ} ff N14 ff\t0b} ff360b} ffyK724} ff ff$40 N} ff0Z0b} ffE0b} ffl{8b} ffffͤ} ff N15 ff\t0b} ff360b} ffyK484} ff ff]> 40m} ff0Z0b} ffE0b} ffl{0b} ffffuv^src:840ip7long.tex3T\able28:RepartitionofthentumbYer2ofpre-imagesforHMb;otver2K(= GFV(2)QNote:3)src:844ip7long.texTheseresultsarejust"to!ysimulations"of[CznP],bMecauseifK敹=GFV(2),nm!ustbMesuchthatQn2ʫ 64finrealexamples.e-16[{Y!vފ Qsrc:846ip7long.texInfordertoobtainapracticalsc!heme,onehastobMeabletosolvetheequationAz2.+nM1A =BQsrc:848ip7long.texforfagiv!enmatrixBK2 MznP(Kȁ). Qsrc:850ip7long.texThereD\indeedexistapMolynomialtimealgorithmtoperformthiscomputation(see[3y],kc!hapterVIII).QThefbasicideaofthisalgorithmistousethefactthat:2BK= Az2.+nM1A)gd(A)=0;Qsrc:852ip7long.texwhereɖgd()EM=det(2Fe+aMB)isapMolynomialwithscalarcoecien!ts(noticethatthispropert!yis QangeneralizationoftheCa!yley-Hamiltontheorem).ITheequationgd(A)F=0ncanbMesolvedbyusingtheQJordanfreductionofmatrices.Qsrc:856ip7long.texThedHMDsc!hemeseemstobMelessvulnerabletoattacksbasedonanemultiple(i.e.onequationssuchQasfthoseoft!ypMe(1),(2)or(3)),asshownintable9bMelow:Vqi#@src:868ip7long.texɉffqǍ͟bffesrc:870ip7long.tex+Dbff1$n=2ObffT"n=3s(gbffx[ni=4 ߟbffffe͟xffsrc:871ip7long.texp=2+Dffݍ4$1016 8e391$src:872ip7long.texOxffݍW"311 Z ݲ133s(gxffݍ{[318 )U49x[src:873ip7long.texߟxff]މff͟xff͵p=3+Dffݍ4$11 8e141$src:874ip7long.texOxffݍW"11 \ݲ11s(gxffݍ{[11 )U18x[src:875ip7long.texߟxffff͟xff͵p=31+Dffݍ4$00 ;rf11$src:876ip7long.texOxffݍW"00 _ ޲1s(gxffݍ{[00 V1x[src:877ip7long.texߟxffff͟xff͵p=127+Dffݍ4$00 ;rf01$src:878ip7long.texOxffݍW"00 _ ޲0s(gxffݍ{[00 V0x[src:879ip7long.texߟxffff[" -src:883ip7long.texT\able29:NumtbYerofequationsof)=ݍ 2teyp9eϤ1HtypeϤ4 rzbt9ypQeT2 2src:886ip7long.texJforHMb;overK(= GFV(p)"󍍑Qsrc:890ip7long.texHo!wever,tXweghavemadecomputations(seetable10bMelow)showingthatequationsoftypMe(3)(de nedQinfsection5)stillexist,andalsoequationsof"t!ypMe(5)",de nedby:HC0XY4zijJxzidyzj+nC0Xzijxzixzj+nC0X zixziƹ+nC0X ziyziƹ+nz0ʫ= 0 ٖ(5)*36~6src:894ip7long.texvhff# ͤ} ffΟHM5( ffSn =2͟} ffzAn =3͟} ffan =4͟} ffzff#ͤ} ffΟEquationsf(5)͡ ff^17b} ff17 } ff31 } ffff#ͤ} ffΟEquationsf(3)͡ ff^19b} ff30 } ff58 } ffff#vesrc:899ip7long.texN8^T\able210:NumtbYeroflinearlyindependenttequationsE(after2replacementtoftheyzigvLariablesbyexplicitvLalues)QNote:%src:903ip7long.texItfma!ybMenoticedthatBK= A2fjimpliesthetwofollowingidentities:u,񩒫~ABnBA =AM1AMA28T(t!ypMef(5))~A2BnBA2ʫ= BM1AMAB8T(t!ypMef(3))5WQsrc:905ip7long.texThisfexplains{inpart{theexistenceofsuc!hequationsoftypMe(5)andtypMe(3).Qsrc:909ip7long.texTheJfactthatsuc!hequationsdoexistthreatenstheHM@ܹscheme.InfacttheymakethecryptanalystQableLtodistinguishbMet!weenLarandomquadratictransformationofKȁn-:2 aandaquadratictransformationQcorrespMondingftotheHMsc!heme.Qsrc:911ip7long.texThismfactexplainsthatw!edonotrecommendtheHMscheme. However,oatthepresent,otheexistenceQof 3 cmmi10 Nff cmbx12p0J cmsl10"V cmbx10XQ ff cmr12q% cmsy6K cmsy8;cmmi62cmmi8Aacmr6|{Ycmr8}h!G cmsl12!", cmsy10g cmmi12gG cmmi12XQ cmr12NG cmbx12K`y 3 cmr10 !", cmsy10 O!cmsy7 b> cmmi10K`y cmr10ٓRcmr7u cmex10