; TeX output 2001.08.05:2018o#fܚ5#ffFysrc:72hfesec.texNff cmbx12TheffsecurityofHiddenFieldEquations(HFE)#vK`y cmr10NicolasUUT.Courtoisie {o cmr9SystXemesTInformationSignal(SIS),Univ9ersitXedeT:oulonetduVar BPT132,F-83957LaGardeCedex,F:ranceOߤN cmtt9courtois@minrank.org^http://hfe.minrank.org+a[st : cmbx9Abstract.&src:76hfesec.texW:eIconsiderthebasicv9ersionoftheasymmetriccryptosys-[stemTHFEfromEuroAcrypt96. Z_[ssrc:78hfesec.texW:ecpropAoseanotionofnon-trivialequationsasaten9tativectoaccoun9tfor[sa}:largeclassofattac9ksonone-wayfunctions.W:efoundequationsthat[sgiv9eٟexpAerimentalevidencethatj cmti9basicHFElcanbAebrokeninexpAected[spAolynomialbtimeforan9yconstantdegree5" cmmi9d.IthasbAeenindependen9tly[spro9venTbyShamirandKipnis[Crypto'99].[ssrc:85hfesec.texW:edesignedandimplemen9tedaseriesofnewadv|rancedattacksthatare[sm9uchmoreecien9tthattheShamir-Kipnisattack.Theyarepractical[sfor,HFEdegreed cmsy924,andrealisticuptodػ=128.,The80-bit,500$[sP9atarin'sT1stchallengeonHFEcanbAebrokeninabAout2-=Aacmr662N. [ssrc:92hfesec.texOurVattac9kissubAexponentialVandrequiresnҟ33Zcmr5333 Љfeg M2-=log^-=;cmmi6dcomputations.The P5[soriginalyvShamir-Kipnisattac9kwasinatleastn-=log 2ݟ-=d.W:eshowhowtoim-[spro9vetheShamir-Kipnisattac9k,byusingabAettermethodofsolvingthe[sin9volvedTalgebraicalproblemMinRank.ItbAecomestheninn-=3Glog d+q% cmsy6O1ƿ(1))4.[ssrc:99hfesec.texAlliattac9ksfailformoAdi edversionsofHFE:HFE-= (Asiacrypt'98),[sHFEv8(EuroAcrypt'99),Quartz(RSA'2000)andev9enforFlash(RSA'2000).!^卑?': cmti10KeyqWor}'ds:src:107hfesec.texasymmetricP|cryptography*, nite elds,one-wayfunctions,Hidden ?FieldLEquation,HFELproblem,basicHFE,MinRankproblem,shortsignatures.!ۍ?N cmbx121S@Intro`ductionۍ?src:117hfesec.texTheHFEtrapGdoorfunctionEurocrypt96[14],de nedin4,isoneofthemost?seriousalternativetrapGdoorfunctions.ItgeneralizesthepreviousMatsumoto-?ImaiUUcryptosystemfromEuroGcrypt88[10]brokenbyPatarinin[13,14]. Z_Nsrc:122hfesec.texHFEBopGeratesBover nite elds.InthispapGerwerestricttotheb}'asicversion?ofiBHFE,andto eldsofcharacteristic2.ThuswestudyatrapGdooriBfunction? b> cmmi10Fز:IGFc(2^ 0ercmmi7n q) !", cmsy10!GF(2^n q).^W*efoGcusonthecr}'ackingproblem^ofcomputingthe?inverse oftheb}'asicHFEencryptionfunction,withouttryingtorecover it'ssecret?key*.Nsrc:132hfesec.texIn9thesection2weattempttobaseanotionofaone-wayfunctiononalgebraic?criteria.3W*epropGosea"boostingmodel"whichisnothingelsethatakindofse-?mantics; ofalldeterministiccryptographicattacks.Thisapproach,subsequently*o#fܚ5#fܚ?narrowed&down,provesparticularlyrelevqanttoHFEattacks.Thesecurityisex- ?pressednintermsofpropGertiesofimplicitequationsthatrelatetheinputsxiNand?the+outputsyiofafunction.Anequationsubstitutedwithagivenoutputvqalue?may*,Rormaynot,proGduceanewnon-trivialequationonxiTL.Newequationsboost?thesetofknownlinearlyindepGendentequationsonthexiTL,andatsomepGoint?theyUUshouldallowtocomputetheactualvqaluesofthexiTL.N3Nsrc:149hfesec.texThereisnodoubtthatourproblemiscloselyrelatedtopGolynomialelimi-?nationJ(Grobnerbases,XLJalgorithm[21]).Thusinsection3westudytheNP-?complete|problemofsolvingmultivqariatequadraticequationscalledsometimes?MQ.;A;simpleideaoflinearizingandapplyingGausseliminationcanindeedbGe?seenaseliminatingequations(simplecaseofGrobnerbasesalgorithm),however?weUUreinterpretitinsection3intermsofimplicitequations.Nsrc:157hfesec.texW*e+distinguishbGetween+this'eliminationparadigm'andourapproachcalled?'implicitequationsparadigm'.ThosemethoGdsardi erentandcomplementary*.?W*edon'tcombineequationsformally,tryingtoeliminateamongallequations?thatIwecouldconstructwithinsomesizelimitation.Insteadofthat,theproblem?isto ndspGecialsubsetsofsuchequations,thatforalgebraicalreasonsmightbGe?related.7W*earenotlimited(atall)bythesizetheequations,butonlythesize?ofUUthesubsetweselected(!).Nsrc:166hfesec.texThe!wholeideathatitisinterestingtodoso,istheob8jectofthispapGer.W*e?maygobacktothecryptanalysisoftheMatsumoto-ImaicryptosystemdescribGed?brie yyin4.1,tounderstandthatalgebraicalreasonsmaysuggest(orprove)the?existenceofsometypGeofequations.Theideahadseveralgeneralizations,such?as#theanemultipleattackbyJacquesPatarin[13,9]andotherdescribGedhere?andin[4].Itwasalreadyknownsince[14]thatsomesuchequationswillexist?forb}'asicHFE.InthepresentpapGerweshowpreciselywhatkindofequations?existUUandhowtousetheminrealisticattacks.Nsrc:176hfesec.texThough]itisveryclearthattheequationswehavefoundinthepresent?papGer,existforalgebraicalreasons,wewerenotabletoexplainthem.They?havebGeenfoundonmuchmoreexperimentalbasis,anditremainsanopen?problem"V cmbx10glossary?/ofwordsthathavespGecialmeaninginthispaper,usually"double-?quoted",UUalongwithcommonnotations,iscompiledattheendofthepapGer.Nsrc:194hfesec.texThesection5showspreciselyseveralclassesofequationswehavefoundand?theirimmediateapplicationsinanattack.ThuswegetastrongexpGerimental?evidenceqthatb}'asicHFE?canbGebrokeninexpectedpolynomialtimeifthedegree(o#fܚ5#fܚ?dвisconstant.ThesameresulthasjustbGeenindependentlyfoundbyShamirand ?KipnisUUatCrypto'99[23]. Nsrc:206hfesec.texW*ebshowthatb}'asicHFENisnotsecurefordegreedEظ24,bwhiletheoriginal?papGerE[14]suggestedtheHFEEdegreed=17Eassecureenough.Therefore,aswe?showLin5.10,inordertobreakthe500$HFE8challengewithd=96Lweneed2^ٓRcmr762?computationsUUand33Tbofmemory*.Nsrc:211hfesec.texW*eintroGducedsuccessiveimprovementstothisattack.First,itisinfact?pGossibleatorecover,arecomposeanduseonlypartsoftheequations("reconcilia-?tion@attack")-section6.1.Secondly*,the"distillationattack"ofsection6.1-6.3?manages&nap(na]L1)=2.Thusthesocalledline}'arizationputszir=xiTLxkand?eliminatesthenewvqariables.W*esayratherthatitimpliestheexistenceofat?leastUUnb=$8nap(naP1)=2equationsoftheform:pu cmex10Xe iTLyid=X㉵ ixi,+8 0[o#fܚ5#fܚNsrc:340hfesec.texW*e|callitequationsof"typGeX+Y"lateron,andtheimportantpointis ?thatthefactthatnbG>C^nap(naAj1)=2impliestheirexistence,butthereverseis?obviously˜false.Theymayexistevenifforsmallnbܲandit'salwaysinteresting?toUUcheckiftheydo. ȍ?4S@TheHFEProblemȍ?src:364hfesec.texW*e giveasimplemathematicaldescriptionofthesocalled"HFEproblem".?MoreUUdetailsonvqariousaspGectsofHFEcanbefoundin[14,5,4,15,18]. &(Nsrc:367hfesec.texThetHFEYproblemde nedbGelowisde nedas ndingonereverseimagefora?basicversionoftheHFEcryptosystemexactlyasinitiallypropGosedatEurocrypt?1996UU[14].Firstwerecalltwobasicfactsfrom[14]:ȍ?F actT4.0.4.x%src:372hfesec.texLetUUPbGeapolynomialoverUUGFc(q[ٟ^nW)ofthespecialform:Nsrc:375hfesec.tex rx践Pc(a)=X t״i㉵ i,8aq@Lrs1iE +q@Lrt1i:X(1)VۍNsrc:379hfesec.texThen!PcanbGewrittenasnmultivqariatequadraticequationsequationsover?theUUaid2GFc(q[ٲ).?F actT4.0.5t_src:382hfesec.tex(HFEtrapQdoor).вIf\P[isapGolynomialofdegreeatmostdthat?Pc^ O!cmsy71 (fbg)QcanbGecomputedintimed^2|s(ln d)^O7(1)JԵn^2GFc(q[ٲ)operations,see[14,8].?De nitionT4.0.6Wsrc:391hfesec.tex(HFEProblem).DzLetASFandTHbGetwoArandomsecretbijec-?tiveUUandanemultivqariatevariablechanges.Let &(Nsrc:394hfesec.tex rx̎F*=To8PST:X(2)Nsrc:398hfesec.texW*ejSbGelievethatit'sdiculttocomputeFc^1Vasfarasit'sdecomposition?Fc^1=S^1 8Pc^1XTc^1uXremainsUUsecret.ȍ?4.1Y1ExamplesTofHFEProblem?src:410hfesec.texThe?msimplestnon-linearcaseofb}'asicHFE>isP[u=a^q@Lr QX+q@Lr ?.Itiscalledthe?Matsumoto-Imaiqcryptosystem(orC^P)[10]fromEuroGcrypt'88.ATtoyexample?ofUUpublicequationscanbGefoundin[13].Nsrc:414hfesec.texItV-hasbGeenbroken7yearsafterthepropGosal[13].Thecryptanalysis([13,9,?14])a1showsthatthereexistatleast2=3nofwhatwedescribGelaterasequations?ofl"typGeXY8",andwhataresimplyimplicitbi-aneequationsinvolvinginput?andUUoutputvqariablesxiandyiTL:Nsrc:422hfesec.tex rxj/X ij xiTLyjo+8XUQ ixi,+8X j6yjo+8'=0C?src:425hfesec.texTheAttackisasfollows: rstwerecovertheseequationsbyGaussianelimination?onUUtheircoGecients.Thenwerecoverxsubstitutingy.intheseequations.?o#fܚ5#fܚ?4.2Y1HFETChallenge1~?src:434hfesec.texItUUhasbGeenproposedbyJacquesPatarinintheextendedversionof[14]. XNsrc:436hfesec.texThe]HFE]RpGolynomialisofdegreed=80]overGFc(2^n q)withn=80bits. ?Thepriceof500$ispromisedforbreakingthesignatureschemethatamounts?toUUcomputingFc^1uXthreetimes.AnexampleofFcanbGedownloadedfrom[5]. ~?5S@ImplicitEquationsAttack~?5.1Y1T9ypQesTofequations?src:458hfesec.texW*eUUhaveaconventiontodescribGeanequationtypGe:~C81.Psrc:462hfesec.texTheequationtypGeisaunionoftermsinformalvqariablesx;y[;X:;Y8,forPexample:UUXYqĸ[8x^2|s. XC82.Psrc:464hfesec.texA1termTx^k됵y[ٟ^l8denotesallthetermsofdegreeexactlykinallthexiTL;i=1::naPandUUofdegreeexactlylinyiTL;i=1::nbD.PImpGortant:UUIfthevqariablesareinGFc(q[ٲ),thedegreesmustbGein[0::q81].C83.Psrc:468hfesec.texTheqcapitalX:;YdescribGeequationsetsthatincludeallthelowerqdegreePterms.UUF*orexample:XYqĸ[8x^2 m1[x[y[xy[x^2|s.C84.Psrc:472hfesec.texIf!necessarywedistinguishbyfXY][yx^2|sgthesetoftermsusedinthecorre-PspGondingequationtype,while[XY-[Ix^2|s]denotesthesetofequationsofthisPtypGe.~?5.2Y1In9v\rariantTEquations~?De nitionT5.2.1Wsrc:496hfesec.tex(In9v\rariantequations).SetMofequationswiththeirsetof?termsUUinvqariantmoGduloanybijectiveaneSandTvqariablechanges.eaNsrc:501hfesec.texF*or[example[X^2EUY8]isinvqariant[butnot[x^2|sy[ٲ].Thede nitionstatesthatthe?setsoftermsinvolvedareinvqariant,thatimpliesthatthenumbGerofequations?thatUUexistforagiventypGeisinvqariant(buteachoftheequationsisinvqariant).Nsrc:506hfesec.texIf{theequationsareinvqariant,{thenumbGer{ofequationsofagiventypGewill?bGethesameforanyoutputvqalue.Thuswecanassumethatwearesolving?Fc^1 (y[ٲ)Uwithy=X0withoutlossofgenerality*.Wemakethisassumptionforall?subsequenthattacks.Theproblemoftheinvqariantequationsofhigherdegreeis?thatUUtheyarestillatleastquadraticaftersubstitutingy[ٲ.~?5.3Y1"Biased"TEquations~?De nitionT5.3.1Wsrc:526hfesec.tex(Biased).zequationsaretheequationsthataftersubstitution?ofUUy"=0reducetoaaneequationofthexi(typGeX).?PropQositionT5.3.2.src:533hfesec.texIf8thereis"enough"invqariant8equations,thereexist"enough"?biasedUUequations.Mo#fܚ5#fܚNsrc:536hfesec.texEnoughmeanstheequaltothenumbGeroftermsremainingaftersubstitution ?of;yo=0.ThepropGositionistrivial,weeliminateinasetofimplicitequations?all\thetermsoffX^1 **cXgbGeforethesubstitutionofyٸ=}0.Theimportant?pGointmlthatbiasedequationsmayexistevenifitisnotguaranteedbytheabGove?propGosition.UUOurexperiencesin5.6hasindeedshowntheydo.Nsrc:543hfesec.texAnotherÁimpGortantpropertyofthebiasedequationsisthattheyallowa?single'Qroundattack.Theresultofsubstitutionofy"=0arelinearinthexiTL.The?drawbackpisthattheyaremadeforasingley̮vqalue.ThewholeattackmustbGe?re-iteratedUUtocomputeseveralFc^1 (y[ٲ)fordi erenty[ٲ.Nsrc:548hfesec.texImpQortan9t:sThe"biased"equationsdoGesnotneedtobecomputedcom-?pletelycyinanattack.OnlythecoGecientsofthetermsinxiŲaswellasconstant?partsUUareneeded(!)?5.4Y1TheTDF cmmib10sizkeoftheEquations?src:553hfesec.texW*e]callsizpethenumbGer]oftermsoftypexiTLxj6ykIcetc..thatareusedinthetype?of&equationsconsidered.Theimplicitequationsattackrequireshugequantities?ofmemory*,bGecausethelengthsizpeoftheequationsispolynomialinnofdegree?atUUleast384,UUandtheattackmemoryrequirementsarequadraticstillinsizpe.Nsrc:558hfesec.texW*eexpresssizpeasafunctionofthenumbGerofinputandoutputvqariables,?respGectivelynaXandnbD.In[4]onecan ndacompletereferencetablethatallows?toUUcomputesizevqalues.F*orexample,for eldsofcharacteristic2:Nsrc:563hfesec.texp?sizpePȈXb9Yc 0ncmsy5[x2 y-[xy2 [x3y[x2y2R=<$zL7Kwfe  (֍12-napnb+<$1wfe (֍4((nan2፴b>*n2፴anb+n2፴an2፴b|s)+<$1wfe (֍6(n3፴anb+na'+nb+1:d?5.5Y1T rivialTEquations?src:571hfesec.texSincetheyiTarequadratic,thereforewehavenbLequationsofthetypGe[1wW[x[?x^2n[y[ٲ].1Alltheequationsthataretheconsequenceoftheseequationsarecalled?trivial.-Inpractice,whennaѝisbiggerthansomeinitialthreshold,thenumbGer-of?trivial5equationsisalways5thenumbGer5thatwegetwhenwepickallquadratic?equationsUUatrandom.Example:Nsrc:577hfesec.texInUU[XYqĸ[8x^2|s]therearentrivialequations,thesameasin[1[x[x^2S[y[ٲ].Nsrc:579hfesec.texT*rivialequations,thoughtheymixwith"non-trivial'equations"usedin?cryptanalysis,arepredictableandharmless.Whentheyi6vqaluessubstitutedto?thelinearmixofthenon-trivialandtrivialequations,weeliminatetheinterfer-?enceUUastrivialequationsalwaysUUreduceto0.Nsrc:583hfesec.texThe7exactnumbGer7triv[ialtyp7eoftrivialequationsisnotobvioustocompute.?Thosethatcomefromtheinteractionofdi erentcompGonentsofthe'typGe'ex-?pression,rmayoverlapandthustypGeh7!HtrGiv[ialtyp7eisnotanadditivefunction.?InUU[4]wecomputetrGiv[ialtyp7e!˲foralltheequationtypGesweconsider.?5.6Y1Results?src:597hfesec.texInthefollowingtableonpage8,weshowthenumbGerofequationsofdi erent?typGesUUfoundforb}'asicHFE.W*edidmuchmoresuchcomputationsin[4].[o#fܚ5#fTable1.TNon-trivialequationsfoundforbasicHFE.R]*src:626hfesec.tex^8#cffꎎ ffn=21#R0 ΄,?ff#R0 ΄,?ff3233src:629hfesec.tex}n$EquationTt9ypAe y,?ff 34ff~#cffꎎͤ9rffzYƎdff#R19rff4Xb9Y39rffRfpsrc:634hfesec.texXb9YT[ijxt2 y~G~9rffsrc:635hfesec.texXb9Y[\cxt2 yO[6Rxy-t2%9rfflXb9t2IYY?q9rffesrc:637hfesec.texXb9t2IYY[Xb9Yct2e[Xb9t3s9rffQ src:638hfesec.texXb9Y[\cxt2 yO[6RQ xy-t2]d[HXxt3 yvD[Q xt2 y-t2429rff؍ff~#cffꎎ ͤ΄7ff 3237ff#R0΄7ffc*FM42!19$src:639hfesec.texPן΄7ffcUp693!19~G~΄7ffc1995!19%΄7ffcD882!210<̟΄7ffc@2688!484s΄7ff...42΄7ff34ff~#cffꎎͤ΄7ff 3247ff#R0΄7ffc*FM21!21$src:640hfesec.texPן΄7ffcUp441!21~G~΄7ffc1995!21%΄7ffcD630!210<̟΄7ffc@2688!484s΄7ff...42΄7ffff~#cffꎎͤ΄7ff 3257ff#R0΄7ffc.K1!1$src:641hfesec.texPן΄7ffcUp232!18~G~΄7ffc1177!18%΄7ffcD357!144<̟΄7ffc@1806!484s΄7ff...42΄7ffff~#cffꎎͤ΄7ff 3287ff#R0΄7ffc.K1!1$src:642hfesec.texPן΄7ffcUp170!20~G~΄7ffc1094!20%΄7ffcD336!184<̟΄7ffc@1764!484s΄7ff...42΄7ffff~#cffꎎͤ΄7ff 3297ff#R0΄7ffc.K0!0$src:643hfesec.texPן΄7ffcUp126!18~G~΄7ffc672!18%΄7ffcD231!124<̟΄7ffc@1134!337s΄7ff...42΄7ffff~#cffꎎͤ΄7ffl!32167ff#R0΄7ffc.K0!0$src:644hfesec.texPן΄7ffcW43!20~G~΄7ffc568!20%΄7ffcD168!144<̟΄7ffc@1092!379s΄7ff...42΄7ffff~#cffꎎͤ΄7ffl!32177ff#R0΄7ffc.K0!0$src:645hfesec.texPן΄7ffc\`0!0~G~΄7ffc;63!16%΄7ffcB84!84<̟΄7ffcې357!169s΄7ff...42΄7ffff~#cffꎎͤ΄7ffl!32247ff#R0΄7ffc.K0!0$src:646hfesec.texPן΄7ffc\`0!0~G~΄7ffc;22!18%΄7ffcB84!84<̟΄7ffcې315!311s΄7ff...42΄7ffff~#cffꎎͤ΄7ffl!32327ff#R0΄7ffc.K0!0$src:647hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcB64!64<̟΄7ffcې315!315s΄7ff...42΄7ffff~#cffꎎͤ΄7ffl!32337ff#R0΄7ffc.K0!0$src:648hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcV@0!0<̟΄7ffcې147!147s΄7ff...42΄7ffff~#cffꎎͤ΄7ffl!32647ff#R0΄7ffc.K0!0$src:649hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcV@0!0<̟΄7ffcې147!147s΄7ffc 4739!2042΄7ffff~#cffꎎͤ΄7ffl!32657ff#R0΄7ffc.K0!0$src:650hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcV@0!0<̟΄7ffc042!42s΄7ffc 1911!1742΄7ffff~#cffꎎͤ΄7ffl!32967ff#R0΄7ffc.K0!0$src:651hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcV@0!0<̟΄7ffc042!42s΄7ffc 1638!2142΄7ffff~#cffꎎͤ΄7ff"321287ff#R0΄7ffc.K0!0$src:652hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcV@0!0<̟΄7ffc042!42s΄7ffc 1547!2042΄7ffff~#cffꎎͤ΄7ff"321297ff#R0΄7ffc.K0!0$src:653hfesec.texPן΄7ffc\`0!0~G~΄7ffcۙ0!0%΄7ffcV@0!0<̟΄7ffc0!0s΄7ffcK0!042΄7ffff~#cffꎎ(?Legend:?src:663hfesec.texW:eTwritetheequationn9umbAerTfoundasA!Bwith:?AL 9src:667hfesec.texis&Dthen9umbAer&Dofnon-trivialequationsfound,whic9hmeanswehavesubtractedthe Pn9umbAeroftrivialequations.Thiscon9ventionallows,atleastaslongasnisnottoAoPsmall,\toha9ve\0atplaceswhereHFE8bAeha9ves\exactlyasarandomm9ultiv|rariatePquadraticTfunction(MQ).?BKfsrc:672hfesec.texIsjthen9umbAerjoftheabo9vejequationsthatremainlinearlyindependen9taftersub-Pstitution ofarandomlyc9hosenyNv|ralue.W:eapplyananalogousconventionforthePorigin,Ttrivialequationsaresubtracted.?src:678hfesec.texThe7memoryneededtodothesecomputationsw9asupto1.2Gbyteandforthisreason?w9eThadtoskipsomeirrelev|rantcases. ?Interpretationintermsofsecurity:?src:683hfesec.texIf w9egetsomewheremorethat0equations,itisaweakness,butnotnecessarilya?w9orkingTattack.?src:685hfesec.texTheyonlyHFExthatcanpretendtobAesecure,shouldgiv9e0non-trivialequationsfor?allTthet9ypAeswecancomputewithinrealisticmemorylimits. mUo#fܚ5#fܚ?5.7Y1In9terpretationToftheResults5?src:702hfesec.texIn#thecomputationsonpage7moreandmorecomplexequationsexistwhen ?dcincreases.In[4]weconsidermanymoredi erentequationtypGesandother?qA 6=42..ThesubtypGesoftypGes[X^lڪY8]provethebGestbecauseatconstantsizpe,?theirUUdegreeinxissmaller. ㍑Nsrc:708hfesec.texW*e`observedthatthedegreesdٻ=q[ٟ^k+@T1::q[ٟ^k+B+1bGehave`almostthesameway?and8thatthenumbGer8ofnon-trivialequationsfoundbehaves8asO(n^ (dlog ꬟qƴqde;ty[pe)?withUUaconstant z(dlog ꬟qƴqde;ty[pe).W*epGostulatethat:toatmostr븲=1{+dlog ꬟qƴqde,>withG^k ޲bGeingnpublicmatricesn{n?overUUGFc(q[ٟ^n D().Nsrc:1010hfesec.texTheunderlyingproblemwearesolvingiscalledMinRank[6].Shamirand?KipnisDsolveditbywhatiscalled'relinearization',see[21]forimprovementson?it.|W*edonotuseit,andinsteadwesolveMinRankdirectly*.OurmethoGdis?identicalUUaspreviouslyusedbyCoppGersmith,SternandV*audenayin[1,2]. &o#fܚ5#fܚNsrc:1018hfesec.texW*ewriteequationsinthet0|s;:::;tn1sayingthatevery(r9+Q1)x(r+1) ?submatrixhasdeterminant0.Eachsubmatrixgivesadegree(r+b1)equation ?on)pthet0|s;:::;tn1bover)pGFc(q[ٟ^n D().Thereareasmuch)pasb L۴n⾍r7+1lbaß߱2$suchequations $?andwehopGethatatleastaboutb ?n⾍r7+1boofthemarelinearlyindependent.W*eget?abGout'Пb K;n⾍'r7+1̟bequations'whichhaveb K;n⾍'r7+1̟bterms,andaresimplylinearizedand?solvedUUbyGaussianreduction. tmNsrc:1029hfesec.texTheUUsizpeoftheequationstosolveisZsizpem^<$zn 卑 xr+81#{ԟ^0nr7+O(1)!xsnlog Xpqd+O7(1)+G;X(15)Nsrc:1040hfesec.texwhichUUgivessimilarresultsasourattacks:ۍbsecurGity"nO7(log Xqqd)!' :X(16)"F#?9S@IsbKasicHFElikelytob`epolynomial?F#?src:1050hfesec.texTheAUMinRankisanNP-completeproblemfore.g.r=Pkn41AU[24,6].Itseems?therefore1 unlikelythatourattackforMinRankinn^O7(r)m#couldeverbGeimproved?toUUremainpGolynomiallyboundedwhenrrgrows.Nsrc:1055hfesec.texThesameremarkappliestoourequationalattacks.Whendgrows,theHFE?problem%(i.e.b}'asicHFE)%tendstotheNP-completeMQproblemofsolvingran-?domUUquadraticequations,see[14,15,4]."F#?10ZConclusionF#?src:1064hfesec.texThe<4bGestknownHFE;attackisourdistillationattackforb}'asicHFE.It'snot?proventoworkford2>>129butreliesonanextensiveexpGerimentalevidence.?we-havealsotheShamir-Kipnisattack,andratherourimprovedversionofit,?thatUUthoughworseinpracticecomeswithaproGof[23].Nsrc:1069hfesec.texTheybGothgivethecomplexitiesinnO7(log Xqqd)$tobreaktheb}'asicHFExversion.?It6ispGolynomialwhendis xedandsubexponentialingeneral.Bothpresented?attacksUUonHFEaremuchbGetterthatanypreviouslyknown.Nsrc:1076hfesec.texEvenwiththesigni cantprogresswehavemade,theattacksstillhavethe?complexityuandmemoryrequirementsthatcanquicklygoout-of-range.Though?it5 iscertainthatattackswillbGeimprovedinthefuture,HFE5canbGeconsidered?secureUUford>128UUandn>80. F#?P9erspQectivesF#?src:1086hfesec.texTheFb}'asicversionofHFEFisbrokenfortheinitiallypropGoseddegreed17F[14]?andEevenford24.EOurattackshasbGeentestedtoworkford128,Eandthus?theUUHFEChallenge1isbrokenin2^62x.So#fܚ5#fܚ?HFETmoQdi cationsthatresisttoallkno9wnattacks.p܍?src:1107hfesec.texSeveralΉHFEgproblem-basedcryptosystemsavoidalltheattacksdescribGedinthe ?presentUUpapGer.W*everi edthatourattacksrapidlycollapsefortheseschemes:p܍?HFE^:eisrc:1113hfesec.texItUUisabasicHFEwithseveralpublicequationsremoved,see[16]. Iƍ?HFEv:e-src:1115hfesec.texDescribGedinapaperpresentedatEurocrypt'99,[17].ItconsistsofPadding;newvqariablestoHFE,asintheOilandVinegaralgorithmpartiallyPbrokenUUatCrypto'98[22].?HFEv-:hsrc:1117hfesec.texCombinesbqbGothabovebqideas.TherearemanyothervqariantsofHFEPpropGosedUUbyJacquesPatarinintheextendedversionof[14]andin[15,18].?Quartz:j!src:1120hfesec.texPresented-atRSA'2000[19]andsubmittedtotheeuropGeanNessiecallPforSprimitives.Anunique128-bitlongsignaturescheme,basedonHFEv-,Pdesignedoforlong-termsecurity*.OurbGestattackappliedtotheb}'asicHFEPsubsystem^ofQuartz,withd=129^andn=103,^givesabGout2^114 uY.HoweverPitUUdoGesnotapplyatalltothewholeQuartz.?Flash,TS ashD)src:1127hfesec.texAlsoatRSA'2000[20]andsubmittedtoNessie.AsignaturePscheme{0basedonC^ ,designedforspGeed.ThesecurityisanopGenprob-Plem.-͍?Referencesp܍C1.Osrc:1152hfesec.texDonCoppAersmith,JacquesStern,SergeV:audena9y:'q[ cmsl9AttacksonthebirationalpAer- Om9utationTsignatureschemes;Crypto93,Springer-V:erlag,pp.435-443. IƍC2.Osrc:1156hfesec.texDonoCoppAersmith,JacquesStern,SergeV:audena9y,oTheSecurityoftheBirationalOP9ermutationISignatureSc9hemes\,inJournalofCryptology:,10(3),pp.207-221,1997.C3.Osrc:1160hfesec.texDonCoppAersmith,Sam9uelWinograd:"Matrixmultiplicationviaarithmeticpro-Ogressions";TJ.Sym9bAolicComputation(1990),9,pp.251-280.C4.Osrc:1164hfesec.texNicolasCourtois:LasXecuritedesprimitiv9escryptographiquesbaseessurlesOproblXemesm6algebriquesm6m9ultiv|rariablesMQ,IP:,MinRank,etHFE,PhDm thesis,ParisO6TUniv9ersity:,toappAearin2001,partlyinEnglish.C5.Osrc:1167hfesec.texNicolaseCourtois:TheHFEGcryptosystemhomepage.DescribAesallaspectsofHFEOandTallo9wstodownloadanexampleofHFEchallenge.http://hfe.minrank.orgC6.Osrc:1170hfesec.texNicolasCourtois:TheMinrankproblem.MinRank,anewZero-kno9wledgeschemeObasedontheNP-completeproblem.Presen9tedattherumpsessionofCrypto2000,Oa9v|railableTathttp://www.minrank.orgC7.Osrc:1178hfesec.texMic9haelLGarey:,DavidJohnson:ComputersandIntractability:,aguidetothetheoryOofTNP-completeness,F:reeman,p.251.C8.Osrc:1181hfesec.texJ.v9onzurGathen,VictorShoup,"ComputingF:r`obAeniusmapsandfactoringpoly-Onomials",ProAceedingsofthe24thAnn9ualACMSympAosiuminTheoryofCompu-Otation,TA9CMPress,1992.C9.Osrc:1189hfesec.texNealVKoblitz:"AlgebraicaspAectsofcryptograph9y";Springer-V:erlag,ACM3,1998,OChapterT4:"HiddenMonomialCryptosystems",pp.80-102.?10.Osrc:1203hfesec.texTsutom9u2Matsumoto,HidekiImai:"PublicQuadraticPolynomial-tuplesforef-O cien9tsignature-veri cationandmessage-encryption",EuroAcrypt'88,Springer-OV:erlagT1998,pp.419-453.o#fܚ5#fܚ?11.Osrc:1207hfesec.texTsutom9u%Matsumoto,HidekiImai:"Aclassofasymmetriccryptosystemsbasedon OpAolynomialsAo9ver niterings";1983IEEEAInternationalSympAosiumonInformationOTheory:,TAbstractofP9apAers,pp.131-132,SeptembAer1983.?12.Osrc:1215hfesec.texP9eter5L.Montgomery:A/BloAckLanczosAlgorithmforFindingDepAendenciesoverOGF(2);TEuroAcrypt'95,LNCS,Springer-V:erlag.?13.Osrc:1228hfesec.texJacquesq~P9atarin:"CryptanalysisoftheMatsumotoandImaiPublicKeySchemeOofTEuroAcrypt'88";Crypto'95,Springer-V:erlag,pp.248-261.?14.Osrc:1231hfesec.texJacqueswP9atarin:"HiddenFieldsEquations(HFE)3andIsomorphismsofOP9olynomials(IP):twonewfamiliesofAsymmetricAlgorithms";Euro-Ocrypt'96,|SpringerV:erlag,pp.33-48.Theextendedv9ersioncanbAefoundatOh9ttp://www.minrank.org/courtois/hfe.ps?15.Osrc:1235hfesec.texJacquesP9atarin:LaCryptographieMultiv|rariable;MXemoired'habilitation`adirigerOdesTrec9herchesdel'UniversitXeParis7,1999.?16.Osrc:1252hfesec.texJacquesP9atarin,NicolasCourtois,LouisGoubin:"C*-+andHMu-V:ariationsOaround$t9woschemesofT.MatsumotoandH.Imai";Asiacrypt1998,Springer-OV:erlag,Tpp.35-49.?17.Osrc:1255hfesec.texJacquesbP9atarin,AviadKipnis,LouisGoubin:"UnbalancedOilandVinegarSig-OnatureTSc9hemes";EuroAcrypt1999,Springer-V:erlag.?18.Osrc:1257hfesec.texJacquesP9atarin,LouisGoubin,NicolasCourtois,+papAersofEliBiham,AviadOKipnis,ST.T.Moh,etal.:AsymmetricCryptograph9ywithMultiv|rariatePolyno-Omials3o9veraSmallFiniteField;knownas`orangescript',compilationofdi erentOpapAersTwithaddedmaterials.Av|railablefromJ.P9atarin@frlv.bull.fr.?19.Osrc:1262hfesec.texJacques!P9atarin,LouisGoubin,NicolasCourtois:Quartz,128-bitlongdigitalsig-Onatures;ACryptographers'T:rac9kRsaConference2001,SanFrancisco8-12AprilO2001,TLNCS2020,Springer-V:erlag.?20.Osrc:1266hfesec.texJacquesP9atarin,LouisGoubin,NicolasCourtois:Flash,afastmultiv|rariatesigna-Oturealgorithm;Cryptographers'T:rac9kRsaConference2001,SanFrancisco8-12OAprilT2001,LNCS2020,Springer-V:erlag.?21.Osrc:1277hfesec.texNicolasCourtois,AdiShamir,JacquesP9atarin,AlexanderKlimov,EcientAlgo-Orithms?1forsolvingOv9erde nedSystemsofMultiv|rariatePolynomialEquations\,InOAdv|rancesinCryptology:,EuroAcrypt'2000,LNCS1807,Springer-Verlag,pp.392-O407.?22.Osrc:1281hfesec.texAdiU]Shamir,AviadKipnis:"CryptanalysisoftheOilandVinegarSignatureOSc9heme";TCrypto'98,Springer-V:erlag.?23.Osrc:1283hfesec.texAdikShamir,AviadKipnis:"CryptanalysisoftheHFEMPublicKeyCryptosystem";OCrypto'99.TCanbAefoundath9ttp://www.minrank.org/courtois/hfesubreg.ps?24.Osrc:1287hfesec.texJ.O.Shallit,G.S.F:randsen,J.F.Buss,Thecomputationalcomplexit9yofsomeprob-Olemswoflinearalgebra,BRICSwseriesrepAort,Aarh9us,Denmark,RS-96-33.Av|railableOatTh9ttp://www.brics.dk/RS/96/33/o#fܚ5#fܚ?11ZCommonTermsandNotationsڍ?abQoutTequations:src:1307hfesec.texW*e8considermultivqariateequationsoverGFc(q[ٲ),usuallywith Pq3=$Z2.~nap/nb²arethenumbGers~ofinput/outputvqariablesxiTL/yi.~W*enotePsizpetyp7ev(nap;nbD)thelengthofequationsofagiven"typGe".The"typGe"isPspGeci edbyaconventionusingexpressionsinvqariablesx;y[;X:;Y#ddetailedinPtheUUsection5.1.퍍?arti cial^rsrc:1314hfesec.texequationsYMareduetothesmalldimensionna/ofthexsub-spaceandPthesmalldegreeofyi expressions.TheybGecomevisibleiftheyaremorePthattrivial+non-trivialequations.TheirnumbGerartificialtyp7ev(nap;nbD)canPbGeUUcorrectlycomputedanddoesnotdependontheHFEdegree.?biasedc^src:1319hfesec.texequationsUU-foroneparticularvqaluey"=0theybGecomeaneinxiTL.?bQoostingnބsrc:1322hfesec.tex--generalnotionofanopGerationthatstartingwithsomeequationsonPtheEunknowns, ndssomeotherequationsonthemthatarenottrivial(e.g.Plinear)UUcombinationsoftheinitialequations.?cast^\Nsrc:1326hfesec.texequations\arenon-trivialequationswithsomexin xedto0,usuallyforPi=naP+81;:::;n.?distillationy src:1329hfesec.tex-teliminatingarti cial"interference"equationsbGetweendi erentPcastsUUofthesameequation,see6.1-6.3.?HFE[ʢsrc:1333hfesec.texstandsfortheHiddenFieldEquationscryptosystem[14].P denotesthePhiddenkunivqariateHFEVpGolynomialoverkGFc(q[ٟ^n D().S9andT areanemulti-PvqariateUUbijectivevariablechangesoverGFc(q[ٲ)andF*=To8PS.?in9terference^ src:1338hfesec.texequations"-anycomplementaryspaceofcastequationsinarti -PcialUUequations.?in9v\rariantpXsrc:1341hfesec.texequations-equationsthatarestillofthesametypGeafterananePvqariableUUchangebGecausetheirsetoftermsisinvqariant.?non-trivial^}hsrc:1345hfesec.texequations5-anycomplementaryspaceoftrivialequationsfoundPimplicitlybyGaussianreduction.Theimplicitequationsweareabletore-PcovermustbGeofsmalldegreeinboththeyijSandxiTL.AnimplicitequationinPtheԵxi2 andyimaybGeviewedasapGointsuchthat,anexpressionintheyiPandUUxiTL,re-writtenasasapGolynomialinxi,hasunusuallysmalldegree. SPsrc:1351hfesec.texF*orjcryptanalysisweloGokforequationsthathavesmalldegreeinthexiPafterVFsubstitutionofonevqaluey(orallpGossibley[ٲ).TheequationsmixedPwithtrivialequationsarestillusefulforcryptanalysis.TheirexistenceisaPde niteUUweaknessofanyone-wayfunctioncandidate.?reconciliationXsrc:1355hfesec.tex-UUrecompGosingdi erent"casts"ofthesameequations,see6.1.퍍?trivialbssrc:1358hfesec.texequationsCN-explicitsmalldegreecombinationsofgivenequationsandPtheY3vqariablesthatareduetothequadraticcharacterofyiTL.TheirnumbGerisPtrGiv[ialtyp7ev(nap;nbD).}Dsrc:1362hfesec.tex-!",q cmsy10骲-informalcategories,doGesn'tmakesenseforequationsregardlesshowtheyPhaveUUbGeencomputed.;o#f -!",q cmsy10'q[ cmsl9&F C cmbxti10"Ɍ cmbsy10DF cmmib10"V cmbx10N cmbx12': cmti10q% cmsy6 cmsy9;cmmi65" cmmi9Aacmr6j cmti9t : cmbx9ߤN cmtt9o cmr9Nff cmbx12 !", cmsy10 O!cmsy7 0ncmsy5 b> cmmi10 0ercmmi7O \cmmi5K`y cmr10ٓRcmr7Zcmr5u cmex10V