; TeX output 2001.08.05:2028Y!vފDፑ:src:46Ip6long.texNG cmbx12ImprouvedzAlgorithmsforIsomorphismsofPuolynomialslύXQ ff cmr12{/ExtendedV4ersion{5XQ cmr12JacquesPratarin,LouisGoubinBullSmartCardsandTVerminals68routedeVVersailles-BP45278431LouvreciennesCedex-FVrancere-mail:8!", cmsy10fJ.Pratarin,L.Goubing@frlv.bull.frENicolasCourtois[SystrsemesInformationSignal(SIS)vUnivrersitsedeTVoulonetduVar-BP132papGerisaboutthedesignofimproved>algorithmstosolveIsomorphismsofPolynomials(IP) problems.N;These&problemswere rstexplicitlyrelatedtotheproblemof ndingthesecretkeyofsome Casymmetriccryptographicalgorithms(suchasMatsumotoandImai's b> cmmi10C^ O!cmsy7 ZCschemeof[13 ],7~orsomevqariationsofPatarin'sHFEschemeof[15 ]).۔Moreover,in[15 ],itwasshownthatIPcanbGeused+inordertodesignanasymmetricauthenticationorsignatureschemeinastraightforwardway*.W*eJalsointroGducethemoregeneralMorphismsofPolynomialsproblem(MP).AsweseeinthispapGer,Tthese!problemsIP andMPhave!deeplinkswithfamousproblemssuchastheIsomorphismofUUGraphsproblemortheproblemoffastmultiplicationofn8 !", cmsy10nUUmatrices.src:51Ip6long.texTheFcomplexitiesofouralgorithmsforIParestillnotpGolynomial,buttheyaremuchFmoreecienththanthepreviouslyknownalgorithms.F*orexample,mfortheIPhproblemof ndingthetwosecret$matricesofaMatsumoto-ImaiC^$schemeoverK=9F v6 0ercmmi7q˲,Xthecomplexityofouralgorithmsis ⍑OG(q[ٟ^n=ٓRcmr72 ⮲)insteadofO(q[ٟ^(nrZcmr52 )y)forpreviousalgorithms./ (In[14 ],theC^ 9schemewasbroken,butthe ؍secretdkeywasnotfound).0Moreover,wehavealgorithmstoachieveacomplexityOG(q  3 #&feg 2)_^n ݲ)onanysystemŖofnquadraticequationswithnvqariablesoverŖK9J=.F qȲ(notonlyequationsfromC^P).ŠW*ealsoDshowthattheproblemofdecidingwhetherapGolynomialisomorphismexistsbetweenDtwosetsofequations@isnotfeqʎJNP-complete(assumingtheclassicalhypGothesisaboutArthur-Merlingames),{butsolvingnIPnisatleastasdicultastheGraphIsomorphismproblem(GI)(andpGerhapsmuchnmoredicult),'sothatIP!isunlikelytobGesolvqableinpolynomialtime.jMoreover,'themoregeneralMorphisms5ofPolynomialsproblem(MP)5isNP-hard.g@Finally*,<wesuggestsomevqariationsoftheIPproblemUUthatmaybGeparticularlyconvenientforcryptographicuse.Q"V 3 cmbx10KeynW\ords:ͣsrc:58Ip6long.texK`y 3 cmr10MorphismsYofP!olynomials,iIsomorphismsofPolynomials,iGraphIsomorphisms,Zero-QKno!wledgefAuthentications,AsymmetricSignatures.QNote:asrc:61Ip6long.texThisfpapMeristheextendedv!ersionofthepaperwiththesametitlepublishedatEurocrypt'98."dQNff cmbx121gIntros3ductionqQsrc:65Ip6long.texThispapMerpresen!tsnewalgorithmsfortheIsomorphismofPolynomials(IP)problem.eIPwasexplicitlyQdescribMed>in[15 4],#whereitw!asshownthatifsomeecientalgorithmexistsforIPe,thenthesecretkeyofQsomeasymmetriccryptosystems(suc!hasthe b> 3 cmmi10CȁK cmsy8 ,kschemeof[13 4]orsomevdDariationsoftheHFEschemeQof[15 4])w!ouldbMefound.Qy(ThecryptanalysisofCȁ Utgivenin[14 4]breakstheschemewithout ndingQthe secretk!ey). ;NopMolynomialalgorithmisknownforIPe.Ontheotherside,x6in[15 4],itw!asalsoQsho!wnthatifnoecientalgorithmexistsforIPe,thenthisIPeproblemcanbMeusedtodesignsomeQzero-kno!wledgeaauthenticationschemes.0TheseschemescanalsobMetransformedinordertohaveanQasymmetricfsignaturesc!heme.!1*Y!vފ Qsrc:67Ip6long.texThis9papMerisdividedin!totwoparts.InpartI,wepresentdi erentvdDariationsofIP9~andwestudya Qcloselyrelatedproblem,^calledMPfor"MorphismsofP!olynomials".WeethenshowthattheseproblemsQarecloselyrelatedtootherandmorefamousproblemssuc!hastheGraphIsomorphismproblem, andQFeast/MatrixMultiplication.yInpartIMI,w!epresentourimprovedalgorithmsforIPe.ThesealgorithmsQareXnotpMolynomial(sothesc!hemesbasedonIPX~arenotbroken),h#buttheyaremuchmoreecientthatQthefpreviouslykno!wnschemes.5ٍQPuartvI:Presentationandgeneralprop=ertiesoftheIPsand\'QMPzproblems 5src:71Ip6long.tex"BQ2gTheffIPandMPproblemsqQsrc:73Ip6long.texIP߫w!asߺpresentedin[15 4].Letusrecallwhatthisproblemis,intheparticularcaseofquadraticformsQ(thefproblemcanbMegeneralizedwithoutdicultiestocubicforms,asw!ellasformsofhigherdegree).Qsrc:75Ip6long.texLetvuandnbMet!wovintegers. LetFz2cmmi8qAtbMea nite eld.Let(!!", 3 cmsy10A)bMeapublicsetofuquadraticequationsQwithfnvdDariablesaz|{Ycmr81,...,azn No!verfthe eldFzq.Weecanwritetheseequationsasfollo!ws:f?bȮk.9= C0u cmex10X 7ʍiOC0X 7ʍj# Ȯijvk vazidazj+nC0X 7ʍ5diȮiklaziƹ+nȮk"V¹(1 kbu):+ȹ(A) ؍Qsrc:77Ip6long.texNo!wSletsbMeabijectiveandanetransformationofthevdDariablesazidڹ,d41 in,andSlettbMeabijectiv!eQandfanetransformationofthevdDariablesbȮk#,1 kbu.Qsrc:79Ip6long.texWeefdenotes(az1;1:::;aznP) =(xz1;1:::;xznP)fandt(bz1;1:::;bznP) =(yz1;1:::;yznP).Qsrc:81Ip6long.tex>Feromf(A)w!eobtainanotherset(BU@)ofkequationsthatgivetheyȮkvdDaluesfromthexzi @values:ō>yȮk.9= C0X 7ʍiOC0X 7ʍj# z0:jijvk vxzidxzj+nC0X 7ʍ5diz0:jiklxziƹ+nzj0:jk"V¹(1 kbu):+ȹ(BU@)!sQsrc:83Ip6long.texWeefsa!ythat(s;1t)isan$p0J 3 cmsl10isomorphismfrom(A)to(BU@),andwesaythat(A)and(BU@)areisomorphic.Qsrc:85Ip6long.texTheAnIPAFproblemisthefollo!wing:if(A)and(BU@)aretwopublicsetsofuquadraticequations,h/andifQ(A)fand(BU@)areisomorphic, ndanisomorphism(s;1t)from(A)to(B).Qsrc:87Ip6long.texWhendsandtarenotnecessarybijectiv!e,wedcallthecorrespMondingproblemthe"MorphismofP!oly-Qnomials"fproblem(MP).Q3gExamplesqQsrc:91Ip6long.texWeeW4no!wpresentthree"toyexamples"inordertobMecomemorefamiliarwiththeIPW andMPproblems.cQExample2ofIPwithttwo2secretsDsrc:94Ip6long.texLetfK(= F z2]{bMethe eldinwhic!hallthevdDariablesxz0,...,xz4,yz0,...,yz4,az0,...,az4,bz0,...,bz4fjlie.Qsrc:96Ip6long.texLet:#4=5(A)C 18 1>1>1>1>1< 1>1>1>1>1:  bz1ʫ= az1.+naz1az5+az2az3+az2az4+az3az4 bz2ʫ= az3.+naz4+az5+az1az2+az1az4+az4az5 bz3ʫ= az5.+naz1az2+az1az3+az1az5+az2az3+az3az5+az4az5 bz4ʫ= az2.+naz3+az4+az5+az1az5+az3az4+az3az5 bz5ʫ= az4.+naz1az3+az1az5+az2az3+az2az4+az2az5+az3az4+az3az5+az4az5+l:Qsrc:98Ip6long.texandflet:#2"/Td(BU@)C 18 1>1>1>1>1< 1>1>1>1>1:1 yz1ʫ= xz1.+nxz3+xz4+xz5+xz1xz2+xz1xz3+xz1xz5+xz2xz4+xz3xz5+xz4xz5 yz2ʫ= xz1xz4.+nxz1xz5+nxz2xz3+nxz2xz4+nxz1xz5+nxz4xz5 yz3ʫ= xz1.+nxz3+xz4+xz1xz2+xz1xz5+xz2xz3+xz3xz4 yz4ʫ= xz3.+nxz4+xz1xz2+xz1xz5+xz3xz4+xz3xz5+xz4xz5 yz5ʫ= xz2.+nxz4+xz5+xz1xz3+xz1xz4+xz2xz3+xz2xz4+xz2xz5+Qsrc:100Ip6long.texThe˘problemisto ndt!wo˘bijectiveandlineartransformationssandtsuchthat(xz1;1:::;xz5)=Qs(az1;1:::;az5),j(yz1;:::;yz5) =t(bz1;1:::;bz5)[andsuc!hthat(A)bMecomes(BU@)withthesetransformations.(ThisQis]sometimescalledan"IP]problemwitht!wo]secrets"sinceheretherearet!wofedsecretanetransforma-Qtionsfto nd:sandt).!2YY!vފΜ٩r\src:135Ip6long.tex/0&0O line1090&0C0&0I0%0&0H0&0H0&0H ПH ПCfdHVI0@?0@50@/0@.&06Afepf1G0->2,(3pV4Ybfd+g@3&09fePɾP>PľP>ÇPfPB&0&0&0&0&0PGxPӾBܥݾB1BOB%VB\S1i2PS3ӟ4#SFiguref1:Graph(I)bGraph(II)p%QNotew1:jsrc:102Ip6long.texThis"to!yexample"comesfromthe"toyexample"givenin[13 4]forCȁ,$Ywhenthe8vdDariables QarezQseparatedin3+5zQvdDariables,"asexplainedin[14 4].+Theequation(A)comefromtheequationb =a3QinfF П_n2Aacmr65}{.cQNote02:#7src:104Ip6long.texIt0ispMossibletosho!wthat,whensisfound,thentiseasyto nd. Ho!wever,an0exhaustiveQsearc!hlonswouldrequire2n-:2[Q=Z225 tcomputationsinthistoyexample.OuraimistoimprovethisQcomplexit!ye.QExample2ofIPwithonesecretDsrc:141Ip6long.texLetfusconsidertheproblemof ndinganisomorphismbMet!weenfgraphs(I)and(II)of gure1.Qsrc:143Ip6long.texLetfKnbMethe nite eldF Пz2RԹ.Qsrc:145Ip6long.texLetf(A)and(BU@)bMethet!woffollowingsetsofequations:P=3(A)1񩒫C &cyz1ʫ= az1az3.+naz1az4+naz2az3+naz2az4+naz3az4 &cyz2ʫ= a2g1.+na2g2+a2g3+a2g4andYp(BU@)1񩒫C &cyz1ʫ= xz1xz2.+nxz1xz3+nxz2xz3+nxz2xz4+nxz3xz4 &cyz2ʫ= x2g1.+nx2g2+x2g3+x2g4P@Qsrc:147Ip6long.texThehproblemisto ndabijectiv!eandlineartransformationssuchthat(xz1;1:::;xz4) =s(az1;1:::;az4),andQsuc!h,that{withthischangeofvdDariables{thesystem(A)bMecomesthesystem(BU@)(i.e..suchthatyz1QbMecomesfaswrittenin(BU@),andyz2fjalsobecomesaswrittenin(BU@)).Qsrc:149Ip6long.texIfUw!eareableto ndallthesolutionsofthisIPUproblem(thisissometimescalledan"IPproblemwithQonezsecret"sinceherethereisonefelΎbfanetransformationsto nd),thensomeofthesesolutionswillbMeQGraph}IsomorphismsfromGraph(I)toGraph(II).&!Thiscomesfromthefactthat{in(A){yz1~w!asQwrittensuc!hthatthemonomialazidazjisinyz1ۆifandonlyifthepMointiislinkedwiththepMointjingraphQ(I).Similarly{in(BU@){yz1lw!aswrittensuchthatthemonomialxzidxzjisinyz1lifandonlyifthepMointiQis link!edwiththepMointjingraph(II).Moreover,wyz2was chosentobMeasymmetricalpolynomialofQthevdDariables,sothatan!ygraphisomorphismbMetweengraph(I)andgraph(II)willbMeasolutiontoQthisparticularIPproblemwithonesecret.Insection4,w!ewillgeneralizethisconstructiontostudyQmorefpreciselythelinksbMet!weenfGraphIsomorphismandIPwithonesecret.QExample2ofMPDsrc:152Ip6long.texThe.vdDariablesbMelongtoaringortoa eldKȁ.Let(A)and(BU@)bethet!wo.followingsetsofequations:>l*(A)C18 1>1>1>1>1>1>1>1>1>1< 1>1>1>1>1>1>1>1>1>1:G؍ bz1ʫ= az1a0g1 bz2ʫ= az2a0g2 bz3ʫ= az3a0g3 bz4ʫ= az4a0g4 bz5ʫ= az5a0g5 bz6ʫ= az6a0g6 bz7ʫ= az7a0g7Gandd;%(BU@)C$18 1>1>1< 1>1>1:? yz1ʫ= xz1x0g1.+nxz3x0g2 yz2ʫ= xz2x0g1.+nxz4x0g2 yz3ʫ= xz1x0g3.+nxz3x0g4 yz4ʫ= xz2x0g3.+nxz4x0g4>AQsrc:154Ip6long.texTheproblemisto ndt!wo(nonbijectiv!e)lineartransformationssandtsuchthat(az1;1:::;az7;a0g1;:::;a0g7) =Qs(xz1;1:::;xz4;x0g1;:::;x0g4),(yz1;:::;yz4)=t(bz1;1:::;bz7),s)ofrank8,tofrank4,andsuc!hthatwhen(A)isQsatis edfandwhentheset!woftransformationssandtaredone,then(BU@)issatis ed.Qsrc:156Ip6long.texWeefcannoticethatthesystem(BU@)isthesystemofequationsofaproMductoft!wof2n2matrices:P?} .yz1&yz3 yz2&yz4⅟!ع=  .Sxz1$rxz3 Sxz2$rxz44!?S)n .Yx0g1$[x0g3 Yx0g2$[x0g44]֟!!3/Y!vފ W܍Qsrc:159Ip6long.texIn9thesystem(A),]w!ehaveexactlysevenmultiplications,]sothatsolvingtheMP8problemissolving Qtherproblem:v"Ho!wtomultiply2$2rmatriceswith7(insteadof8)multiplications".B(ThenumbMerQofadditions," subtractionsandm!ultiplicationswithconstantsofKcanbMehigh," butthenumbMerofQm!ultiplicationsfoftermsofthematricesisatmost7).Qsrc:161Ip6long.texV.Strassenfoundin1969ho!wtomultiply2S2matriceswith7multiplications(cf[17 4]).OHissolutionQisfthefollo!wing:?DCC(8 (>(>(>(>(>(>(>(>(>(< (>(>(>(>(>(>(>(>(>(:38az1ʫ= xz3.nxz438az2ʫ= xz1.+nxz438az3ʫ= xz1.nxz238az4ʫ= xz1.+nxz338az5ʫ= xz138az6ʫ= xz438az7ʫ= xz2.+nxz4Cu8 u>u>u>u>u>u>u>u>u>u< u>u>u>u>u>u>u>u>u>u:G؍,\a0g1ʫ= x0g2.+nx0g4,\a0g2ʫ= x0g1.+nx0g4,\a0g3ʫ= x0g1.+nx0g3,\a0g4ʫ= x0g4,\a0g5ʫ= x0g3.nx0g4,\a0g6ʫ= x0g2.nx0g1,\a0g7ʫ= x0g1">"< ">">":뙙-]yz1ʫ= bz1.+nbz2bz4+bz6-]yz2ʫ= bz4.+nbz5-]yz3ʫ= bz6.+nbz7-]yz4ʫ= bz2.nbz3+bz5bz7G)ٍQ4gIPffwithonesecretisatleastasdicultasGraphIsomorphismQ%N cmbx12Firstlinksb`etweenthetwoproblemsQsrc:168Ip6long.texWeex rstgeneralizetheconstructionofsection3abMoutIPwwithonesecret.RLet(I)and(II)bMet!woQn-v!erticesfgraphs,andlet(A)and(BU@)thefollowingsystems:'2aȂ(A)C&18 1>1< 1>1:j yz1ʫ= C0P 7ʍi;jl zijJxzidxzj yz2ʫ=C1W*n ύ5C0P 7ʍ i=1.x2|idandu(BU@)C&18 1>1< 1>1:j yz1ʫ= C0P 7ʍi;jlzijJazidazj yz2ʫ=C1W*n ύ5C0P 7ʍ i=1.a2|i;'3Qsrc:170Ip6long.texwherefallthe zij JandzijcoMecien!tslieinf0;11gandsatisfy:B[ zij U= 1,TheifandjFvderMticesof"grMaph(I)arel7)inkX?edtogdether=Czij U= 1,TheifandjFvderMticesof"grMaph(II)farel7)inkX?edtogdether":Qsrc:173Ip6long.texItԃiseasytoseethateac!hgraphisomorphismbMetween(I)and(II)correspMondstoamorphismof QpMolynomialsbet!ween(A)and(BU@).ThismorphismofpMolynomialsisaveryspMecialone,sinceitcanbeQde nedfb!yazio= x:u'(i)L,where'issomepMermutationoff1;1:::;ng.Qsrc:175Ip6long.texReciproMcallye,lcannan!yxisomorphismofpolynomialsbet!weenn(A)and(BU@)bec!haracterizedbyazio= x:u'(i)QforsomepMerm!utation'off1;1:::;ng?Ofcoursenot,andexplicitexamplescanbebuilttobecon!vinced.QNev!ertheless,wecanconsiderthefollo!wingargument:_thereexistqdn(n+1)XpMossibleanetransformationsQbMet!ween(thexziչandtheazidڹ,Iamongwhic!hqdn (qdn1)(qdnqd)(qnq2$):::(qnqn1_)(arebijectiv!e.eTheQprobabilit!y1thatsuchatransformationleavesyz1 E5invdDariantisaprioriKײ1*fe( Sq|;cmmi6n(n+1)|LʉfeJDB O2|,+13(bMecausethereare獍n(n+1)ϟʉfeɔPA 2 Cmonomials xzidxzj q(i^jv),dandaconstan!tterm). ThesamepropMertyisapriori0trueforyz2.QMoreo!ver,fsince Wkqdzn (qdzn{n1)(qdznqd)(qzn{qz2$):::(qzn{qzn1_) < q`n(n+1)ƟLʉfeJ O2z+1&r,jmڽ21*;Qsrc:177Ip6long.texw!eMcanthinkthat{"mostofthetime"{thereareveryfewsolutionsfortheIPKproblembMetween(A)Qand(BU@)thatdonotcorrespMondtoasolutionofGraphIsomorphism.Ofcourse,itisaroughevdDaluation.QNev!ertheless,lFitDsuggeststhatifamethoMdisfoundtosolvetheIPDproblemwithonesecret,lFthenweQshouldcbMeabletousethismethodtoalsosolv!etheGraphIsomorphismproblem.WeenowstudyhowQtofobtainarealproMofofthispropert!ye.RQPossibleimprovementsQsrc:182Ip6long.texNoticevthatsev!eralpracticalsolutionscanbMethoughtoftobMettereliminatethe"unwanted"solutionsQofftheIPproblembMet!weenf(A)and(BU@)(i.e.ݹthosewhic!hdonotcorrespondtoagraphisomorphism).Qsrc:184Ip6long.texFeorinstance,:-w!ecanaddtheequationyz3ʫ= xz1 c+`_xz2+:::+xznoto(A),:-andsimilarlyyz3ʫ= az1 c+az2+:::+aznQto(BU@).Moregenerallye,an!ysymmetricalpMolynomialcanbeadded,forexampleyz4ʫ= x3g1X+>Tx3g2+:::+x3An!4IgY!vފ!BQto`y(A)andyz4ʫ= a3g1+a3g2+:::+a3An ɹto`y(BU@).Ǝ(Inthatcase,nuw!emustsuppMosethatwecansolveIP`gnotonly Qforfquadraticsystems,butalsoforsystemsofhigherdegree).Qsrc:186Ip6long.texAnotherxadhoMc"solutionconsistsinaddingtheequationyz3ʫ= x2g18to(A)andyz3= a2'͍kto(BU@),wherek8isQrandomlyfc!hosenbMetween1andn.șThiswaye,s]wecanexpMect{forsomeofthesekڹvdDalues{toeliminateQthe"un!wanted"solutions,whilekeepingatleastonesolutionoftheGraphIsomorphismproblem(butQthisfisnotaproMof).{5Qsrc:190Ip6long.texAbMetter!idea,Pinordertoobtainrealproofs,Pistoin!troducet!wo!newvdDariables,Psa!yXandX01,andtoQconsiderfthet!woffollowingsystems: Xl(A)1(E yz1ʫ= C0P 7ʍi;jl zijJxzidxzji yz2ʫ= (XJnxz1)(Xxz2):::(XxznP)andي|(BU@)1(* yz1ʫ= C0P 7ʍi;jlzijJazidazj1 yz2ʫ= (X0naz1)(X0az2):::(X0aznP)f;Qsrc:192Ip6long.texwherefthe zij JandzijvdDaluesarede nedasbMefore. Qsrc:194Ip6long.texNo!w,hsinceYdKȁ[X@<;1X01;az1;:::;aznP;xz1;:::;xznP]Ydisafactorialring,han!ysolutionoftheIPYPproblembMetween(A)Qand](BU@)isindeedasolutionoftheGraphIsomorphismproblem(notethatthet!wo]equationsin(A)Qandܞ(BU@)canalsobMecom!binedinoneequationlikethis:JMyz1%=e(Xo xz1):::(XxznP)(XC0P !L8i;j zijJxzidxzjf )).QHo!wever,there\8isstillaproblemwiththisconstruction:Itheequationsyz2 kQTheorem24.15[3src:201Ip6long.tex&': 3 cmti10A\nyppermutationO}off1;1:::;ngcanbewritteninauniquewayasfolFlows:>k3:o:= zin7;nvnziqnq% cmsy61;n1&:::ziq1*;1+;Qsrc:203Ip6long.texwherpeDiȮkFh2"f1;1:::;kX?gforalFlk,1"k{n,andDwherpezi;j isthepermutationthatexchangesiandj(by Qcponvention,zi;i Ϲ=Id).ˍQProYof:%src:207Ip6long.texWeefproMceedb!yinductiononn.Qsrc:209Ip6long.texItiseasytoc!hecktheresultfornԸ=1andnԸ=2.ILetussuppMosethattheresultistrueforagiv!enQin!tegerfn,andletusconsiderapMermutation off1;1:::;nn+1g.Qsrc:211Ip6long.texLetizn+1=#d(nx+1),Handletd0V=#ziqn+1eL;n+1&dd. /Thefactthat02̹(nx+1)#=nx+1sho!wsthatd0MinducesQafpMerm!utationoff1;1:::;ngf(thatwealsodenotebyd02̹).Qsrc:213Ip6long.tex>Feromtheinductionh!ypMothesis,thereexistindicesiz1,...,iznJsatisfyingiȮk.92 f1;1:::;kX?gforallk,1 kbn,Qandfsuc!hthat:dz0=s= zin7;nvn:::ziq1*;1+:Qsrc:215Ip6long.texAsfaresult,w!ehave:o:= ziqn+1eL;n+1&Rn:::ziq1*;1+;Qsrc:217Ip6long.texwithfiȮk.92 f1;1:::;kX?gforallk,1 kbnn+1.Qsrc:219Ip6long.texWeefha!vethusprovedtheexistenceoftheabMovedecompMositionofd.Qsrc:221Ip6long.texThe,[unicit!yisaconsequenceofthefollowingcombinatoricargument./LetusdenotebySznԫthesetofallQpMerm!utationsŧoff1;1:::;ngŧandbyTJthesetofallpMermutationsthatcanbMewrittenaszin7;n:::ziq1*;1+.QThereareatmostnpMossibilitiesforiznP,n1possibilitiesforizn1̹,...,and1possibilit!yforiz1.Therefore,QT+con!tainsf n!elements.Moreover,wehavejustproventhatthefunctionAF: 񩒫ύ ]T! Szn ]ٹ(zin7;n;1:::;ziq1*;1+) 7!zin7;nvn:::ziq1*;1BSQsrc:223Ip6long.texisfsurjectiv!e.SincejTVj jSznPj,fwecanconcludethatF+isbijective.Theunicityisthusproven.{5Qsrc:227Ip6long.texWeeno!wseehowtousethistheoremto"translate"thefactthatthetransformationsinvolvedintheQNP-problemJcorrespMondingtoaGraphIsomorphisminstanceisc!haracterizedbyazi=x:u'(i)1forsome!5eY!vފ QpMerm!utation'n*2SznP.Accordingtotheorem4.1, suc!hapMermutationcanbMewrittenastheproductof Q(atfmost)npMerm!utationszi;j X.Qsrc:229Ip6long.texTeosimplify,9letus rstgiv!ea"translation"ofthefactthatananetransformations$<:x7!aisQc!haracterizedeitherbys =Id,=orbyazio= x:u'(i)+?(foralli),=with'=zij ׹fort!wogivenindicesiandjv.۷ItQisfequivdDalen!ttosayingthatsisanisomorphismofpMolynomialsbet!weenfthet!woffollowingsystems:#ϓ(A)C(18 1< 1:䍍 yz0ʫ= (XJnxzidڹ)(Xxzjf ) yȮk.9= xȮkc(1kbn;yk6=i;1jv) yzn+1s= XȹandЛ@(BU@)C(18 1< 1:䍍 yz0ʫ= (Anazidڹ)(Aazjf ) yȮk.9= aȮkc(1kbn;yk6=i;1jv) yzn+1s= A#ϔQsrc:231Ip6long.texBy-usingthisargumen!tseveraltimes,*weobtainthefollowing"translation"ofaGraphIsomorphismQproblemHin!toanIPHVproblem:"scorrespMondstoanisomorphismofthegraphs(i.e.)inparticularisofQtheVformazio= x:u'(i)forsome'2SznP)i itisanisomorphismofpMolynomialsbet!weenVthet!woVfollowingQsystems:q~č(A)B18 1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1< 1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1:_ yz0ʫ= C0P 7ʍi;jl zijJxzidxzj<퍍 8i;1j;y1 iL>L>L>L>L>L>L>L>L< L>L>L>L>L>L>L>L>L>L:ܪ;y:u(2n1)8:ijM+14 ]=  XJxא(8:ijM) FaijN2Xxא(8:ijM) Fajjky:u(2n1)8:ijM+k6+1?Mg= xא(8:ijM) k$!h(1kb > > > > < > > > > > :\@y:u(2n1)(n2)(n+1)=2+1_ =  XJnx:u((n2)(n+1)=2)|i<BHXx:u((n2)(n+1)=2)|j<ō@y:u(2n1)(n2)(n+1)=2+k6+1jK= x:u((n2)(n+1)=2) '͍kO(1kb1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1< 1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1>1:n yz0ʫ= C0P 7ʍi;jlzijJxzidxzj<퍍 8i;1j;y1 iL>L>L>L>L>L>L>L>L< L>L>L>L>L>L>L>L>L>L:ܪ;y:u(2n1)8:ijM+14 ]=  Aaא(8:ijM+1) Fai"ʟ(Aaא(8:ijM+1) Fajky:u(2n1)8:ijM+k6+1?Mg= aא(8:ijM+1) k.(1kb > > < > > > :ō@y:u(2n1)(n2)(n+1)=2+1_ = (Anazidڹ)(Aazjf ) @y:u(2n1)(n2)(n+1)=2+k6+1jK= aȮkc(1kb1+q(jv1)(j2)qʉfe*PA>23`andX, A,asw!ellasthex:u() '͍kkanda:u() '͍k ,arein!termediatevdDariables."EachͯQofftheset!wofsystemscon!tainsKٙ2n-:3*3n-:2n+4ٙfe8cPA2Bequationsoverٙ(n+1)(n-:2*2n+2)ٙʉfeAqPA2K%-vdDariables.QConclusion:.src:238Ip6long.texBysolvingIPwithonesecretonasetofOM޹(n3)quadraticequationsw!ecansolveany QGraphfIsomorphismproblemwithnv!ertices.Therefore,IPisatleastashardasGI.QRemark:%src:241Ip6long.tex1.src:243Ip6long.texInrtheparticularcasewhere(A)and(BU@)con!tainonlyoneyquadraticequationwithnvdDariables,therefexistapMolynomialalgorithmto ndtheisomorphism(see[15 4]).!6~Y!vފ 2.src:245Ip6long.texWeedonotpretendthatthisconstructiongiv!esanewandmoreecientwaytosolvetheGraph Isomorphismeproblem.Infact,yalthoughnopMolynomialalgorithmiskno!wnfortheGraphIso-morphismproblem, `inpracticev!eryecientalgorithmsareknown:|:forexampleitisfeasibleto ndanisomorphismforgraphsev!enfor"hard"instancesof1000verticesgraphsinlessthan10min!utes4onapMersonalcomputer(see[6y]p.22).So4themaininterestofthisconstructionistosho!w|thattheIP|problemwithonesecretisprobablynotsolvdDablewithaprobabilisticalgorithmoffpMolynomialcomplexit!ye.(BecauseGIOwascarefullystudiedandmanypMeoplethinkthatGIOisnotfsolvdDableinpMolynomialcomplexit!y).!%Q5gMPffisNP-hardqQsrc:250Ip6long.texInthissection,7w!eprovethattheMorphismofPolynomials(MP)problem,7de nedinsection2,isQNP-hardfforan!y nite eld,andfortherationalnumbMers.Qsrc:252Ip6long.texThefproMofusessomepropertiesofthree-dimensionaltensors.Letus rstrecallsomebasicde nitions:%QDe nitions:%src:255Ip6long.texy1.src:257Ip6long.texAfthree-dimensionaltensoroisathree-dimensionalarra!yT= (tȮijvk v)ofnumbMers.B2.src:259Ip6long.texIt?hasrank1xi itcanbMewrittenastheouterproductofthreev!ectors(i.e.Xhi thereexistthreev!ectorsfx,y andz!suchthatmȮijvk= xzidyzjf zȮkforallindicesi,jv,kX?).3.src:261Ip6long.texThefrankofageneraltensorT+istheminimaln!umbMerfofrank1tensorsTzsuc!hthatT= C0PC8lTz3.Qsrc:264Ip6long.texTheQfollo!wingresultabMoutthecomplexityof ndingtherankofathree-dimensionaltensorwasprovedQb!yfJohanH(astadin[11 4]:QTheorem25.1(HL-astad)jN#src:267Ip6long.texT)ensorrpankisNP-completeforany nite eldandNP-hardfortherationalQnumbpers.Qsrc:270Ip6long.texLetfusno!wseehowthisfundamentalpropMertycanbMeappliedtoourMPproblem.Qsrc:272Ip6long.texLet}ussuppMosew!ehaveanalgorithmthatsolvestheMP-probleminpMolynomialtime(inparticular,QthisMalgorithmcanbMeusedtokno!wwhetherthereexistasolutionornotforsomegiveninstanceoftheQMP-problem).Qsrc:274Ip6long.texLetT= (tȮijvk v)bMeamdn`(three-dimensional)tensor.Itisw!ellknown(seeforinstance[18 4])thattheQrank3ofTvisexactlyequaltotheminimaln!umbMer3ofm!ultiplicationsneededtocomputethefollowingQcorrespMondingfsetofbilinearformsb!yabilinearnon-commutativealgorithm:.sai(BU@)C18 1>1>1>1>1>1< 1>1>1>1>1>1:? yz1ʫ=C1(m ύ5C0P 7ʍ i=1C1lIn ύTC0P 7ʍ.jv=1#4tzijv1 xzidx0|j獍.... yȮ`=C1(m ύ5C0P 7ʍ i=1C1lIn ύTC0P 7ʍ.jv=1#4tȮijv` xzidx0|jf :/Qsrc:276Ip6long.texLetr^f(= rMankX?(TV))bethisminimalvdDalue.Byde nition,.r^fcanbethough!tasthesmallestintegerusuchQthatLt!wolineartransformationss]й:6(xz1;1:::;xzm;x0g1;:::;x0AnP)]7!(az1;1:::;azuk;a0g1;:::;a0Auk޹)Landt]й:6(bz1;1:::;bzuk޹)]7!Q(yz1;1:::;yȮ`)fexist,thattransformNnS~(A)C&18 1>1< 1>1:h bz1ʫ= az1.na0g1 #.#.#. bzuv= azuna0Auk: T썑Qsrc:278Ip6long.texin!tof(BU@).Qsrc:280Ip6long.texThis@isaparticularinstanceoftheMP@gproblem.XFeoru =mn,g nding@asolution(s;1t)isquiteeasy.QNamelye,fw!ecande nesandtbythefollowingformulas:ݍja8i;y1 im;8j;1jn;Lȟ񩒫a:u(i1)n+j'G=xzia0(i1)n+j'G=x0|jf :!~ˍ~=8kX?;y1 kb`;yȮk.9=C1*m ύC0X 7ʍbi=1C1n ύxC0X 7ʍOjv=1#XtȮijvk vb:u(i1)n+j$:!7٠Y!vފ QNote:src:285Ip6long.texMoreo!ver,anya!symmetryofagiv!enthree-dimensionaltensorleavesitsrankunchanged,so Qthatfw!ehaveinfact:rX minJ(mn;1nkX?;km);8Qsrc:287Ip6long.texwhic!hsistheanalogueoftheclassicalinequalityrMankX?(M1)Ymin(m;1n)sfora(two-dimensional)mJnQmatrixfM1.Qsrc:289Ip6long.texThenalgorithmcanno!wbMeusedtobuildapolynomialalgorithmthatcomputestheexactvdDalueofr:8L1.src:292Ip6long.texLetfu =mn.r2.src:294Ip6long.texWith thehelpof,tryto ndt!wo lineartransformationss :(xz1;1:::;xzm;x0g1;:::;x0AnP) 7!(az1;1:::;azuk;a0g1;1:::;a0Auk޹)fandt : (bz1;1:::;bzuk޹) 7!(yz1;1:::;yȮ`)fthattransform&(A)C&18 1>1< 1>1:h bz1ʫ= az1.na0g1 #.#.#. bzuv= azuna0Auk:&٬src:296Ip6long.texin!tof(BU@).3.src:298Ip6long.texIffgiv!esasolution,thenreplaceubyun1fandgobacktostep2,elseoutput"rX= un+1".8LQsrc:301Ip6long.texIt>9iseasytoseethatthisalgorithmoutputsthecorrectvdDalueofrafteratmostmncallstotheQ(pMolynomial)]algorithm,tsothatw!ehavebuiltanalgorithmthatcomputestherankofathree-Qdimensional%tensorinpMolynomialtime.AccordingtotheresultofJohanH(astadmen!tionedabo!ve,weQcanfth!usconcludethattheMP-problemisNP-hardforany nite eld,andfortherationalnumbMers.ƍQRemarks:%src:304Ip6long.tex1.src:306Ip6long.texMoreNpreciselye,`Zw!ehavejustproventhatthe"DecidingMP"problem(i.e.theproblemof ndingwhetherPthereexistamorphismbMet!weenPtogiv!ensetsofmultivdDariatepMolynomialequations)isNP-complete.Asw!ewillseeinsection6,JthispropMertybMecomesfalseifwereplace"MP"by"IP".r2.src:308Ip6long.texMPTisTclearlyav!eryimpMortantprobleminmathematics::anecientalgorithmwouldgivethecomputationxSoftheminim!umnumbMerofstandardmultiplicationstocomputetheproMductoftwo33,O44TorkkJmatrices,forsmallkX?,and{fromthis{impro!vedTalgorithmsforGaussianreductionsandrelatedproblemsma!ybMefound.(Thebestkno!wnasymptoticalgorithmsareatthepresen!tNinOM޹(nc.y),wherec\*'2:3755,seeN[4y].pItisalsoin!terestingtoseewhatkindofbrute-forcecomputationsfha!vebMeendonesofartosolvesuchproblems,see[10 4].)3.src:310Ip6long.texThefactthatMPisNP-hard,andmoreo!verthefactthatMPisav!eryimpMortantproblemthatseems$tobMev!erydicultevenwithverysmallparameters,arestrongmotivdDationstodesigncryptographicfalgorithmsbasedonthisproblem.Ferom[2y]and[7],itiskno!wnthatanyproblemofUNPUcanbMeusedtodesignanasymmetricauthen!ticationscheme(withthehelpof"goMod"Uhashfunctions).(TheproMofisextendabletodesignasymmetricsignaturesc!hemes.againwiththehelpof!"goMod"hashfunctions).SinceMP!_isinNPe,w!ecanapplythesegeneralresults.Ho!wever,<thesev!ery9generalconstructionsarenotverypractical,anditmaybMemorediculttodesignecientsc!hemesffromMPthanfromIPe."m荍Q6gDecidingffIPisnotNP-completeqQsrc:315Ip6long.texWeey3call"DecidingIP"theproblemof ndingwhetherthereexistanisomorphismbMet!weeny3twosetsQofm!ultivdDariatepMolynomialsequations.GInthissection,=weprovethattheDecidingIPproblemisnotQNP-complete,dunder>theclassicalh!ypMothesisthattheso-called"polynomial-timehierarc!hy">doesnotQcollapse.Qsrc:317Ip6long.texThefproMofisbasedonthefollo!winggeneralresults(see[9y]and[3]forproMofs):$֍QTheorem26.1(Goldwtasser,Sipser)src:320Ip6long.texIfaprpoblemhasaconstant-roundinteractiveproof,DzthenitalsoQhasacponstant-roundA\rthur-Merlinprpotocol.!8 Y!vފ W܍QTheorem26.2(Boppana,HL-astad,Zacthos)πsrc:324Ip6long.texIfthecpomplementofaproblemhasanA\rthur-Merlin QprpotocolEwithacponstantnumberofrounds,fandifisNP-complete,fthenthepolynomial-timehierarchyQcpolFlapses.QNote:src:328Ip6long.texArth!ur-Merlin]protoMcolshavebMeenstudiedbyBabaiandMoranin[1y],lbutwedonotneedtoQgofin!tofurtherdetailsforourproMof.Qsrc:332Ip6long.texWhat~remainstodoisbuildingaconstan!t-roundinteractiveproMofforthe"NonIsomorphismofPoly-Qnomials")(Non-IP)problem.'FeorthatpurpMose,w!eusetechniquesdiscoveredbyGoldwasser,MicaliQandSiRac!ko ([8y])fortheanalogous"QuadraticNon-Residuosity"problem,dandalsousedbyGoldreich,QMicalirandWigderson([7y])for"GraphNon-Isomorphism",5andb!yPetrankandRoth([16 4])for"CoMdeQNon-EquivdDalence".Qsrc:334Ip6long.texAs?usual,TFw!esuppMosethattwosets(Uz0)and(Uz1)ofpMolynomialequationsarepublic,TFandanin nitely-QpMo!werfulGprover(calledMerlin)wantstoconvinceapMolynomial-timeveri er(calledArthur)that(Uz0)Qandf(Uz1)arenotisomorphic.TheycanproMceedasfollo!ws:QFirst`round:Ssrc:337Ip6long.texArth!urtakesKAnumbMers z1,H..., K +randomlyc!hoseninf0;11g.FeoreachkX?,H1 kbKȁ,QArth!ur9buildsaset(VȮk#)whichisisomorphicto(Uz i?k ), bychoMosingtworandomsȮk"˹andtȮkbijectiv!eaneQpMerm!utationsfandcomputing(VȮk#) =tȮk~n(Uz i?k )sȮk.Hefsends(Vz1);1:::;(VK;¹)ftoMerlin.QSecondjround:]Hsrc:340Ip6long.texFeor֯eac!hkX?,1[ k_Kȁ,Merlin֯triestoguess Ȯk#,i.e.nhetriesto ndwhether(VȮk#)Qisfisomorphicto(Uz0)or(Uz1).Hesendshisguesses( z1;1:::; K;¹)ftoArth!ur.QFinal2vteri cation:%src:343Ip6long.texArth!urfacceptstheproMofi Ȯk.9= ȮkforallkX?,1kbKȁ.Qsrc:347Ip6long.texItfiseasytoseethat:1.src:350Ip6long.texIff(Uz0)and(Uz1)arenonisomorphic,Merlinnev!erfailsinconvincingArthur.2.src:352Ip6long.texIf(Uz0)and(Uz1)areisomorphic,theprobabilit!ythatArthurisconvincedthat(Uz0)and(Uz1)are non-isomorphicfisatmost2K:.sQPuartzI=I:NewalgorithmsforIP 5src:357Ip6long.texQsrc:361Ip6long.texWeeBusethesamenotationsasinsection2(foru,Vn,qd,(A)Band(BU@)).hInsections7and8,Vw!ewilldesignQsome1impro!vedalgorithmsfortheIP0problemontwosetsofuquadraticequationswithnvdDariables.QThen,finsection10,w!ewillconcentrateonthespMecialcaseu =n."AQ7gAff rstalgorithmforIPSQsrc:365Ip6long.texLet[ z1;1:::l;1 zu bMeuvdDaluesrandomlyc!hoseninK3=7F $zq.Thereisaprobability1=qdu +xthatC1u ύC0P 7ʍi=1 zidbzi=n0Qyz1.nsL̹().Qsrc:368Ip6long.texMoreo!ver[when()oMccursitisv!eryeasyto ndananebijectionStransformingaintoxsuchthatQ()fdoMesoccur(when()iswritteninaandxinsteadofbandyd).Qsrc:372Ip6long.texTheΪreasonforthisisthatthereisa"canonical"represen!tationofeachequationofdegreetwooveraOQ nite eld(cf.f[12 4],Wc!hapter6forexample),andfromthecanonicalrepresen!tationsofC1>u ύmC0P 7ʍi=1h{ zidbzi8ιandyz1,tQwhen=Jtheseequationsarewritteninaandx,citwillbMeeasyto ndsuc!habijectionS.WhatistheQprobabilit!yfthatthisSGisindeedtherights?Qsrc:377Ip6long.texIfuq6=1,~inthematrixofthesecretanefunctionsw!ehaven(np+1)coMecien!tsand()givesonlyQ1n+n(n+1)=2&AquadraticequationsonthesecoMecien!tsifK(= Fz2Eandn(nn+1)=2+n+1&AisK6= Fz2.&SoQtheprobabilit!ythatwewillrecovertherightsthiswayisexpMectedtobeappro!ximately1=qdu1:q@1n{q2*+nƟfen2Qif4K(= Fz28andappro!ximately1=qdu1wVq@1n{q2*nƟfe..ľ2[ifK6= Fz2."Then,6>whensisfounditistheneasytoreco!ver Qtfb!ygaussianreductionsonthecoMecientsoft.!9 Y!vފ&CQsrc:383Ip6long.texThecomplexit!yofthisalgorithmtorecoverthesecretsisexpMectedtobeOFq@1n{q2*+n+2uƟfe 12$-ifK=K(Fz2andeuQOMޟFq@1n{q2*n+2uƟfe ᴟ2$,-ifcK(6= Fz2Sg(bMecausew!etryagainanotherS4untilwe ndavdDalidsolution).ׇThisisbMetterQthanfthecomplexit!yOM޹(qdn-:2*+nR)ofexhaustivesearchons.gQNote(q1. 5src:387Ip6long.texIfu =1thenthe rstpartofthealgorithmwilleasily ndanssolution(notnecessarythe Qrigh!tfs)soumustbMe6= 1.!/QNote?2. 5src:390Ip6long.texItislogicaltotrytoimpro!vethisalgorithm,~forexampleb!yusingtwoequationsC1hu ύK:C0P 7ʍi=1F3 zidbziL=f`Qyz1ʷsTKandC1u ύٟC0P 7ʍi=1  `0|idbzio= yz2ʷs.Ho!wever,ditTKisnotclearho!wtocombinetheseequationsinordertoimprovetQthealgorithm.Morepreciselye,/whenu(2,w!edonotknowanypMolynomialalgorithmfortheIPQproblem.ҋEv!enpforu =2,; ndingpsuchanalgorithmappMearstobeasdicultas ndingaprobabilisticQpMolynomialfalgorithmfortheGraphIsomorphismproblem,asw!esawinsection4."QQ8gAfsecondoalgorithmforIP(foundbyH.Gilbs3ertandF.Cherbon-gnier)qQsrc:396Ip6long.texAsbMefore,letAbethequadratictransformationthatgiv!esbfroma,andB8bethequadratictransfor-Qmationfthatgiv!esy fromx:b =A(a)f; cyo:=BU@(x):Qsrc:398Ip6long.texLetfsandtbMethet!wofsecretanetransformationssuc!hthata =s(x)fandyo:= t(b).Therefore:pNb =tz1 hnBU@(x)=As(x):Qsrc:400Ip6long.texTheideaistousethefactthatthecompMonen!tsofAq,sarealwayslinearcombinationsofthecompMonents QoffBU@.Moreo!ver,thisisofcoursealsotrueifweconsiderAnsonlyonasmalln!umbMerofvdDariables.QExample 5src:402Ip6long.texLetf(A)and(BU@)bMethefollo!wingtwosetsofequations:0#,(A) :C >8 >>>>>>>>>< >>>>>>>>>: :bz1ʫ= az1.+naz1az5+az2az3+az2az4+az3az4:bz2ʫ= az3.+naz4+az5+az1az2+az1az4+az4az5:bz3ʫ= az5.+naz1az2+az1az3+az1az5+az2az3+az3az5+az4az5:bz4ʫ= az2.+naz3+az4+az5+az1az5+az3az4+az3az5:bz5ʫ= az4.+naz1az3+az1az5+az2az3+az2az4+az2az5+az3az4+az3az5+az4az51 ÍQsrc:404Ip6long.tex((A)fcomesfromb =a3)./Ţ'(BU@) :C >8 >>>>>>>>>< >>>>>>>>>:1:yz1ʫ= xz1.+nxz3+xz4+xz5+xz1xz2+xz1xz3+xz1xz5+xz2xz4+xz3xz5+xz4xz5:yz2ʫ= xz1xz4.+nxz1xz5+nxz2xz3+nxz2xz4+nxz2xz5+nxz4xz5:yz3ʫ= xz1.+nxz3+xz4+xz1xz2+xz1xz5+xz2xz3+xz3xz4:yz4ʫ= xz3.+nxz4+xz1xz2+xz1xz5+xz3xz4+xz3xz5+xz4xz5:yz5ʫ= xz2.+nxz4+xz5+xz1xz3+xz1xz4+xz2xz3+xz2xz4+xz2xz5/ŤQsrc:406Ip6long.texThefproblemisto ndt!woflineartransformationssandtsuc!hthata =s(x)fandyo:= t(b).QRemark 5src:408Ip6long.texThiskexamplecomesfromatransformationmadein[14 4]ofthe"to!yexample"givenin[13 4].hQsrc:414Ip6long.texWeewillc!hoMosexz4-Ϲ=m0andxz5=m0(sothatw!eobtainavectorspaceofdimension6m>5generatedbyQthefmonomialsxz1,xz2,xz3,xz1xz2,xz1xz3,xz2xz3).(BU@)bMecomes:/ŢN(BU@) :C >8 >>>>>>>>>< >>>>>>>>>:1:yz1ʫ= xz1.+nxz3+xz1xz2+xz1xz3:yz2ʫ= xz2xz3:yz3ʫ= xz1.+nxz3+xz1xz2+xz2xz3:yz4ʫ= xz3.+nxz1xz2:yz5ʫ= xz2.+nxz1xz3+xz2xz3e-10 7Y!vފ W܍Qsrc:416Ip6long.texSo',thev!ectorspacegeneratedbytheequationsof(BU@)isthevectorspacegeneratedbythe5vectors Qfxz1,fxz2,xz1xz3,xz2xz3,xz3.+nxz1xz2g.Qsrc:418Ip6long.texLetfsbMe:$⍑e(s) :C>8 >>>>>>>>>>>< >>>>>>>>>>>:͍:az1ʫ= z1xz1.+n z2xz2+n z3xz3fj(+ z4xz4+n z5xz5):az2ʫ= z1xz1.+n z2xz2+n z3xz3fj(+ z4xz4+n z5xz5):az3ʫ= z1xz1.+n z2xz2+n z3xz3fj(+ z4xz4+n z5xz5):az4ʫ= z1xz1.+nz2xz2+nz3xz3fj(+z4xz4+nz5xz5):az5ʫ= "z1xz1.+n"z2xz2+n"z3xz3fj(+"z4xz4+n"z5xz5)-yQsrc:420Ip6long.texWee\thenpMerformanexhaustiv!esearchonthe zidڹ, zi, zi,zi,"zij(1:Ai3)\vdDalues,i.e.[thereare215QpMossibilitiesfforthesevdDalues.zQExample2ofvLalue: 5src:422Ip6long.texWeeftry&󍍍C8 >>>>>< >>>>>:͍uaz1ʫ= xz1fj(+ z4xz4.+n z5xz5)uaz2ʫ= xz2fj(+ z4xz4.+n z5xz5)uaz3ʫ= xz3fj(+ z4xz4.+n z5xz5)uaz4ʫ= 0f(+z4xz4.+nz5xz5)uaz5ʫ= xz1.+nxz2fj(+"z4xz4+"z5xz5)+Qsrc:424Ip6long.texThen:bz1ʫ= xz1xz2.+nxz2xz3:Qsrc:426Ip6long.texHo!wever,Wthis41bz15isnotinthev!ectorspacegeneratedbyfxz1;1xz2;xz1xz3;xz2xz3;xz3w+sxz1xz2g.=As41aresult,Qthisfc!hoiceforthevdDalues zidڹ, zi, zi,zi,"zi @(1 i3)fcanbMeeliminated.!*QComplexitty: 5src:430Ip6long.texFeorԆabMoutonetryamong32,the v!evdDaluesbzi9`(1Wi5)Ԇwillbeinthev!ectorspaceQgeneratedb!yfxz1;1xz2;xz1xz3;xz2xz3;xz3_+ xz1xz2g(bMecauseeac!hvdDaluebziSmhasaprobabilityabMoutK!ƽ1!Ɵfe@PA2tobeinQthisv!ectorspace).nThenforthesecases,wewillconsiderxz4I6=[E0andwewilltryallthevdDaluesfor z4,Q z4,f z4,z4,"z4.Qsrc:432Ip6long.texThisfw!aye,wemaythushopMeto ndthegoods(andt)afterabout215 ntriedvdDalues.QGeneralcomplexittyofthealgorithm 5src:436Ip6long.texIngeneral,(A)and(BU@)aret!wosetsofthefollo!wingtypMe:$|D s(A) :C&>8 >>>< >>>:܍:bz1ʫ= Pz1(az1;1:::;aznP)䰍%z.%z.%z.:bzuv= Pzuk޹(az1;1:::;aznP)wnandS(BU@):C&>8 >>>< >>>:Ձ:yz1ʫ= PV0g1(xz1;1:::;xznP) %z.%z.%z.:yzuv= PV0Auk޹(xz1;1:::;xznP)#Qsrc:438Ip6long.texWeefwillc!hoMoseallthevdDaluesxzio= 0,i>,whereissuc!hthat:1n+(1)ȉfe(&f tVf20_> u(&b(i.e.E'm&p *m&p P ڍ2u)6Qsrc:440Ip6long.texTherefore,the v!ectorspacegeneratedbyx2g1,x2g2,...,x2'͍uZ,xz1xz2,...,xzidxzj(1#i u.Qsrc:442Ip6long.texWeeeywillthenpMerformanexhaustiv!esearchonthepartofsthatgivesaz1,ru...,azn ɹfromeyxz1,...,xȮuZ,i.e.9onQnfvdDalues.Thecomplexit!yofthispart1isthusexpMectedtobeaboutqdn = qdnZ,p\Z,\)@ԍ2 U`52pj52\)ޟ΍uc}.CLQsrc:444Ip6long.texThenforabMoutonetryamong q@1{q2*+Ɵfegx2g`u!o'hmu,x,3theuvdDaluesbzi ~(1aiu)willbeintherigh!tvector䍑Qspace.Then7forthesecasesw!ewillcontinuebyintroMducingthevdDaluexȮ+1Qֹ.ThisintroMducesqdn DnewQpMossibilities,Ksothatthet!ypicalvdDalueforthecomplexityofthispart2ofthealgorithmissuchthatK-:2*+ϟfeӟPA82nu K=n=ڟfe(PPA9u?ù(i.e.'7p *7p y ɍ2BīqCĉfe5 (nB+1)(n+2)=2.As=aQmatterK4offactitbMecomeseasyassoonassome(n+1)(n+2)=2K4equationsareindependen!t(asaformalQsum.ofxzidxzjZ8coMecien!ts),sothattheuquadraticequationsformageneratingset.6TheprobabilityofQbMeingOsorapidlytendsto1asugro!ws.Inthatcaseantyinvertiblesallowto ndatleastonetbyQGaussianfreductionandevteryt!wofgeneratingsetsofequationsareisomorphic.Qsrc:511Ip6long.texWeealsofoundin!terestingtoseparatetheanepartofapplicationssandt,,qasthelinearcaseseemsQaw(biteasier.P"Ho!wever,Xsincew(itisalw!aysw(pMossibleto ndtheconstan!ttermsbyexhaustivesearchinQOM޹(qdn ),an!yalgorithmfortheIPproblemwithlinearsandtwithcomplexityOM޹(qd n z)canobviouslybMeQtransformedfin!toageneralalgorithmforanesandtwithcomplexityOM޹(qd( +1)nn).Qsrc:516Ip6long.texSofromno!wonandthroughoutthepresentsectionweexclusivelyconsidertheIPproblemwithtwoQsecretflinearsandttransformations.Qsrc:519Ip6long.texAsaconsequenceofseparationbMet!weenaneandlinearparts,w!eshouldsupposethatA(0)?y=0andQBU@(0)VY=0.fOtherwisew!ewouldhaveacompletelyarti cialweakness,,asweknowthatt(A(0))VY=BU@(0)Qandfitgiv!esanapriori:knowledgeont.Qsrc:526Ip6long.texThepresen!tsectionisdividedintothreeparts(inthesethreeparts,VsandtareassumedtobMelinear).QFirst,w!ewillseeasimplealgorithmsolvingmostcasesoftheIPinnO+x(0) \|)u=a>+a(0).PQThereforeQw!epclassifyanotonlybytheinversiondegreeofitsimageA(a)asbMefore,{butwewillalsoconsidertheQclassfofan+a(0) \|.Thefn!umbMerofclasseswillsystematicallyincrease.Qsrc:574Ip6long.texThisattac!kwillworkforanysensiblenon-bijective(> 2classes)quadraticequationsset.YeetwecannotQsolv!eBatoyexamplegivenatthebMeginningofthearticle,.ysinceitisbijective.$qInordertosolvetheseQcasesfw!ehitupMonanotherapproach. ύQ10.2ќThe"toandfro"attackQsrc:581Ip6long.texWeefwilldescribMetheattac!konthetoyexamplefromthechapter2,showingdirectlyhowitworks.Qsrc:584Ip6long.texLetfqo:= 2andn=5.Weeconsider1"B0A :C8 >>>>>< >>>>>:Q6bz0ʫ=az0.+naz0az4+az1az2+az1az3+az2az3 6bz1ʫ=az2.+naz3+az4+az0az1+az0az3+az3az46bz2ʫ=az4.+naz0az1+az0az2+az0az4+az1az2+az2az4+az3az46bz3ʫ=az1.+naz2+az3+az4+az0az4+az2az3+az2az46bz4ʫ=az3.+naz0az2+az0az4+az1az2+az1az3+az1az4+az2az3+az2az4+az3az4Qsrc:594Ip6long.texand%ˍ+ټB_:C 8  > > > > > <  > > > > > :Q6yz0ʫ= xz0.+nxz2+xz3+xz4+xz0xz1+xz0xz2+xz0xz4+xz1xz3+xz2xz4+xz3xz4 6yz1ʫ= xz0xz3.+nxz0xz4+nxz1xz2+nxz1xz3+nxz1xz4+nxz3xz46yz2ʫ= xz0.+nxz2+xz3+xz0xz1+xz0xz4+xz1xz2+xz2xz36yz3ʫ= xz2.+nxz3+xz0xz1+xz0xz4+xz2xz3+xz2xz4+xz3xz46yz4ʫ= xz1.+nxz3+xz4+xz0xz2+xz0xz3+xz1xz2+xz1xz3+xz1xz4-Qsrc:607Ip6long.texasffunctionsF_n25 R! F_n25꫹. Qsrc:609Ip6long.texWee|ha!vemadeatableoffunctionsAandBU@,whereforsimpli cationpurpMoseswedenoteF_n25 felementsQb!yintegers,ڎsothattox=(xz4;1xz3;xz2;xz1;xz0)correspMondsx=C1n ύ?C0P 7ʍi=0: xzidڹ2i.pThereforeifw!ereadinthen0QtablethatA(5)=31itmeansthatifa=(az4;1az3;az2;az1;az0)=(0;0;1;0;1)thenx=s(a)equalstoQ(1;11;1;1;1).Rsrc:619Ip6long.texYff\dٛ͟ ff ff н0ٛ ffm@1ٛ ff!Z23ٛ ff.h&33ٛ ff;u43ٛ ffH53ٛ ffU63ٛ ffb73ٛ ffoj83ٛ ff|93ٛ ffP10ٛ ff11ٛ ff812ٛ ffά13ٛ ff 14ٛ ff15ٛ ff16ٛ ff|17ٛ ff18ٛ ffd19ٛ ff ,20ٛ ff:L21ٛ ff$G22ٛ ff1U423ٛ ff>b24ٛ ffKp25ٛ ffX}26ٛ ffe27ٛ ffrx2X8ٛ ff{D29ٛ ff30ٛ ff,31ٛ ff@ff\ff\ꡍͤٛ ff&eA ff н0ٛ ffm@1ٛ ff!Z83ٛ ff,H$15ٛ ff9U10ٛ ffFc 31ٛ ffSp23ٛ ffb43ٛ ffmh26ٛ ffz25ٛ ffR33ٛ ff63ٛ ff:93ٛ ffά30ٛ ff"53ٛ ff20ٛ ff14ٛ ff|18ٛ ff22ٛ ffd12ٛ ff ,24ٛ ff:L16ٛ ff$G21ٛ ff1U427ٛ ff@23ٛ ffKp28ٛ ffX}11ٛ ffe19ٛ fft$13~/ٛ ffF73ٛ ff17ٛ ff,29ٛ ffff\ꡍͤٛ ffe&eBͤ ff н0ٛ ffm@5ٛ ff:16ٛ ff,H$24ٛ ff9U13ٛ ffFc 25ٛ ffSp11ٛ ff`}18ٛ ffmh29ٛ ffz10ٛ ffP30ٛ ff43ٛ ff828ٛ ffά26ٛ ff"93ٛ ff 23ٛ ff17ٛ ff|27ٛ ff19ٛ ffd20ٛ ff ,21ٛ ff:L14ٛ ff&g13ٛ ff1U423ٛ ff@73ٛ ffKp31ٛ ffX}22ٛ ffg33ٛ fft$15~/ٛ ffF63ٛ ff83ٛ ff,12ٛ ffff\ꎎ*/Qsrc:635Ip6long.texIntherealapplicationw!ewillnotconstructanytable,:andwewillproMceedwithexhaustivesearchatQev!eryftimeweneedtocomputeA1orBU@1X"whichhappMensO(n)timesinthisattac!k.Qsrc:641Ip6long.texThefmainideaistosa!ythatifwehavekequationsons:'"SC$*8 *>*>*< *>*>*:?Gs(x(1) \|)#=ia(1)>k┹andUtheattackcomplexityisabMoutnO9< 9>9:aꍍos(1) =1 os(2) =7os(3) =6$Qsrc:700Ip6long.texasf{inFz32 n{1n+2 =3fand1n+7 =6.Qsrc:704Ip6long.texThenfw!eusethetableto`transfer'equationsontheotherside:C&W#8 W#>W#< W#>W#:aꍍ:t(1) =5 :t(4) =16:t(23) =24%}Qsrc:707Ip6long.texFeorfexamplewiths(2) =7,fw!egetA(7) =4fandBU@(2) =16fandallthatimpliesthatt(4) =16.Qsrc:712Ip6long.texNo!wfwecombinethemagaintoget23.n1 =7depMenden!tequations:?CW#8 W#>W#>W#>W#>W#>W#>W#>W#>W#>W#>W#< W#>W#>W#>W#>W#>W#>W#>W#>W#>W#>W#:.:t(1) =5 :t(4) =16:t(5) =21:t(18) =13:t(19) =8:t(22) =29:t(23) =24e-15dnY!vފ!BQsrc:715Ip6long.texAndfusingA1andBU@1X"w!eget7equationsons:@CF8 F>F>F>F>F>F>F>F>F>F>F< F>F>F>F>F>F>F>F>F>F>F:.ɣs(1) =1 ɣs(2) =7ɣs(3) =6ɣs(4) =17ɣs(8) =18ɣs(20) =14ɣs(30) =27@Q6VPfromthose7equationareactuallyindepMenden!t,JandyetitisenoughtorecoversbyGaussian Qreduction.Similarlyfw!egettandverifythecorrectnessofoursolution.9܍WtO(az0;1az1;az2;az3;az4) =Щ|2666666666fi4QS1.1-1="!0L1S0.1-0="!1L1S0.1-0="!0L1S0.0-0="!0L1S0.0-1="!1L1Щ|WU3WU7WU7WU7WU7WU7WU7WU7WU7WU7fiWU5_2(xz0;xz1;xz2;xz3;xz4)c\fq(yz0;1yz1;yz2;yz3;yz4) =Щ|2666666666fi4QS1.1-0="!0L0S0.1-0="!1L1S1.0-0="!0L1S0.0-0="!1L1S0.1-1="!1L1Щ|WU3WU7WU7WU7WU7WU7WU7WU7WU7WU7fiWU5_2(bz0;bz1;bz2;bz3;bz4):]܍Qsrc:733Ip6long.texIf;w!eloMokcloselyatthe"toandfro"attackwecanseethatitcanbMetransformedintoan`birthdayQparado!x'kor`meetinthemiddle'attackwithalltherelatedspMeed-memorytradeo s.ThisispossibleQbMecausefinourattac!kwecanopMerateasfollows:1.src:740Ip6long.texFirst,&w!esstartwithgiven2or1vdDaluesonentriesofAwewriteontheoneside,&andthecorrespMondingfen!triesforBwewriteontheotherside.2.src:745Ip6long.texThen=oneac!hsidewecomputenewvdDaluesasbMeforebysuccessivelineartransformations,yapplyingAorA1 andBorBU@1 ,againlineartransformationsetc.Th!usweobtainnewvdDalueswhichstillmatc!hxtherespMectivevdDaluesontheotherside.ΫWeecallthisphenomenon"bMoosting"xastheinitialinformationfisampli ed.3.src:752Ip6long.texA!tftheendweloMokforalinearsthatmapsthesetwo(ordered)sets.Qsrc:755Ip6long.texNo!wCinordertotransformtheattackintothe`birthdayparadox'-basedattack,WweneedonlytomoMdifyQpart23.Letusassumew!ehaven-+"2relatedentriesa(i) 3XforAandontheothersiden-+"2relatedentriesQx(i) hforgJBU@.Weedonotneedtocomputestokno!wtheyarereallyrelatedbys.Thereisadi erentway:Qw!e{ ndseparatelyhowthenO+"{relatedentriesa(i) ͹arelinearlydepMendentbMetweenthemselvtesandQw!e/dothesameforthenʁ+"/ƹentriesx(i)1ofBU@.yTwosetswhicharerelatedbysmusthavethesameQlinearYdepMendencies..No!wwecaneasilydetectacollisionintwohugelistsofsetsloMokingforthesameQdepMendencies.Qsrc:768Ip6long.texTheprobabilit!yoferrorcanbMemadeassmallaswewantsincen+"ǹhaveatleast"lineardepMendencies,QandǾtheprobabilit!yofthembMeingalltrueforalinearlynon-relatedsetofdatagrowsverysmallwithQ":1=qd"n .Qsrc:775Ip6long.texOurGnextattac!kexploresthis`birthday'approachwithseveralimprovements,aswewanttoinsureQtheMpMossibilit!yofstartingallcasesof"toandfro"withoneequationandwedonotwanttodoanyQexhaustiv!efsearchforinversionofAorBU@.e-16vY!vފ vʍQ10.3ќCombinedp`owerattack.Qsrc:782Ip6long.texInIordertofurtherimpro!veIourattac!kswefoundoutthatitwouldbMenicetohaveafunctionwhichwe Qcall"bMoostingfunction"withthefollo!wingproperties:vonanen!tryxwecomputeinpMolynomialtimeQx0= FV(x)fsuc!hthatF+ispreservedbytheisomorphismofpMolynomials:VzIfas(x) =a;yFBE(x)=xz0tandfFAK(a)=az09;thenfs(xz0) =az09:Qsrc:787Ip6long.texHo!wever:QTheorem210.1;src:789Ip6long.texTherpeTisnonon-trivialboostingfunctionwhichworksforalFlthequadraticequations Qsets.QProYof:~src:793Ip6long.texThe"toandfro"attac!kswillalmostalways,*apartfromimprobablecases,allo!wtorecoverQinf`aunique,^deterministicw!aye,thef`entiresandtstartingfrom2equationsons.Yeet,^anon-trivialQbMoosting functionw!ouldallow,withsomenon-zeroprobabilitye,todothesamestartingwithonlyoneQequation.Qsrc:799Ip6long.texNo!w,>inStheverypreciseequationssetderivedfromb+ǹ=a3 itSisnotpMossible.KFeromthestructureofQbù=a3 |automorphismsKxsho!wninthelastchapterwecaneasilyseethatthereareatleastnpMossibleQsolutionsfsandtsatisfyingan!ygivenequationons.Qsrc:806Ip6long.texThefsituationisnotthatbadthough,sinceinmostqo:6= 2casesthev!erysimplefunction:kuFV(z{I) =BU@(rMz);ywithjrX2FzpQsrc:809Ip6long.texcanfgiv!efewequationsontwithoneequationons.Qsrc:813Ip6long.texThereforew!emustloMokforlesspo!werfulfunctionsandinsomew!ayrelaxitsaxioms.Weeha!vefound Qfewfw!aysofdoingso:1.src:818Ip6long.texWee7ma!yconsidermoregeneralfunctions,Mdealingwithdi erentsetsofinformationonentriesandresultsfofafunction.2.src:821Ip6long.texMoreo!verfwemayusedi erentbMoostingfunctionsdependingontheparticularitiesA.3.src:824Ip6long.texWeex:&جQsrc:867Ip6long.texIt=w!orks neforp 6=2,Rbut=itfailsforp =2.The=problemisthatifaisasolution,a+c=isasolutionasQw!ell,andOwecannoteithereasilytellthemapart,eithersumthemup,sinceao+(a+c)giv!esa,whichQisnotanewdata. Weewilltak!eoneofthesevdDalues,atrandom,inev!erypair(x;1x{ٹ+z{I). ThesumwillQbMefkno!wnwithpossible(+z{I),andexactlywithprobabilit!y1=2whichisnotbad.Weeput: FBE(z{I) =|C0XPN/xsuc9hthat08mB (x+zlognn+OM޹(1)fnewvdDaluesw!enotet(i;jv)Cй,j= 1::(lognn+O(1)).src:949Ip6long.texWee-ncansuppMosethatatleastlog%ln|+O(1)-nareindependen!t,Eandwetakecaretohavethemalwayswrittenfinthesame xedorder.src:952Ip6long.texWeefdothesameforAandw!egetthed(i;jv)6list.4.src:955Ip6long.texExpansionf(lognn+OM޹(1)outputvdDalues7!n+OM޹(1)inputvdDalues):FeorTev!erycandidateiweapplyagainthe`di erentialsolving'principleforBU@.Theinputdi erencewillalw!aysbMethesamez{I(i;0).bFeortheoutputdi erenceswewilltakeallthepMossiblelinearcom!binationsfofthet(i;jv)Cй,j= 1::(lognn+OM޹(1)).src:964Ip6long.texTh!usfwegetabMoutqdlog n+O nn+OM޹(1)vdDaluesde nedasfollo!ws:C0X -n:˾thexsuc9hthat؄GB (x+zFeromX7thesevdDaluesw!ekeepnw+","32OM޹(1)X7whichagainneedtobMetakenalwaysinthesameordering.Weefcallthemz{I(i;jv),j= 1::(nn+").src:977Ip6long.texWeefdothesameforAanditgiv!esc(i;jv)Cй,j= 1::(nn+").5.src:981Ip6long.texLabMelfdistribution.Feor#eac!hlistz{I(i;jv),B0jzչ=_1::(n+")#wearegoingtodetectbyGaussianreductionallthepMossiblelineardepMendencies. BInordertoeasilymanagethesetofdependenciesw!ewillproceedinaw!ay=togetonlyindepMenden!tlinearequations,cbasfollows: =forj=1;12;:::*we=seekallthelineardepMendencieshbet!weenz{I(i;jv)andthoseofthez{I(i;k6)|,k<j޹whicharenon-zeroandhavenotbMeenfoundflinearlydepMenden!tbefore.src:989Ip6long.texThisclistoflineardepMendencies,ha!vingbet!weenc2andn+"cmem!bersisalabel,asignaturew!egiv!eftothelistz{I(i;jv),j= 1::,andactuallytothesolevdDaluez{I(i;0).src:995Ip6long.texAskw!eexplainedbMefore(5.2),liftwolists,loneforAandanotherforBU@,arerelatedb!ythelinearapplications,theywillha!vethesamelabMel.Iftheyarenot,theerrorprobabilit!yisassmallas1=qd"n .Feurthermoref" =2isenough.e-19!Y!vފ 6.src:1001Ip6long.texCollisionfdetection. Iffp 6=2w!esimplyloMokfortwosamelabMels.src:1006Ip6long.texIfp3j=2,t!wolistsz{I(i;k6)|,k=3j1::andc(j$;k6),k=3j1::canbMestillpresumedtocorrespondthroughsfor'somei,@jtobMefound,butimpMerfectlykno!wn:ywithpossible+z{I(i;0)@forthe rstlistand+c(i;0)forfthesecond.src:1013Ip6long.texTheprobabilit!yofan+"+1elementslisttohavethesamelabMelasifsomerandomlychosenelemen!tswouldhavebMeenaddedthesamevdDaluez{I(i;0)isquitebig:# aboutKý10feE*PA2"=asw!eexpecttoha!ve"linearrelationsinalistanditis1=2foronerelation.cThereforew!eexpMectthatwiththeprobabilit!y]abMoutKh1џfe џ^22"swecandetectiftwoz{I(i;0)vandc(j$;0)arerelatedbys.ŚAgain" =2isenoughandcw!ehaveKn1fe џ^22"`=K]ܽ1=ڟfePA16 .ǑItmeansthatforp =2conein16sfunctionswe ndinthepresentattackisfcorrect.src:1025Ip6long.texFinallye,OinG!allcasesw!esimplysearchforiandj痹suchthatz{I(i;k6)|,Oko=00::(n+")G!andc(j$;k6),kb= 0::(nn+")fha!vethesamelabMel.7.src:1030Ip6long.texComputingfofs.Weecanthencomputesb!yGaussianreductionon>nequationsons:s(z{I(i;k6)|)=c(j$;k6),Jk=0::(nn+").8.src:1035Ip6long.texEndingfstep.>Feromssw!eeasilygettandweverifythesolution.Eventuallye, ifp =2,w!esneedtotryabMout16collisions.Qsrc:1041Ip6long.texWeePdonotkno!wanyexampleofquadraticequationsforwhichallthethreevdDariationsoftheattackQw!ouldD0failaltogether.:Weedidnotprogramthewholeattacksofar,kbutwedidtestingonparticularQpMoin!tsfthatseemedtobeuncertain."AQ11 SuggestionsffofIPvariationsQIPwithonesecretQsrc:1050Ip6long.texAsKw!ehaveseenabMove,9someimprovedalgorithmsexistforIP-withtwosecrets.?Therefore,9whenIPQis usedforauthen!ticationorsignatureasexplainedin[15 4],:itmightbMesuggestedtouseIPwithoneQsecretinsteadofIPwitht!wosecretsinordertoha!veamoreecien!tscheme.ItmayloMoksurprisingQthaty-IPxwithonesecretmigh!tbMeamoredicultproblem(withpracticalvdDaluesoftheparameters)QthanSIPSwitht!woSsecrets.LHowever,d>thisisnotsosurprising:inIPSwithtwosecrets,d>wehaveabMout2n2Qunkno!wnPcoMecientsofK(thesecretvdDaluesofthesandtmatrices)andabMoutK4n-:34fe RPAz2Y_quadraticequationsQon{theseunkno!wnvdDalues(whenweformallyidentifythetwosetsofequations(A)and(BU@)),i.e.muchQmoreBUequationsthanunkno!wns.However,VYinBUIPB 3 cmmi10Nff cmbx12"V 3 cmbx10"V cmbx10XQ ff cmr12q% cmsy6K cmsy8!", cmsy10;cmmi62cmmi8g cmmi12Aacmr6|{Ycmr8XQ cmr12NG cmbx12K`y 3 cmr10 !", cmsy10 O!cmsy7 b> cmmi10 0ercmmi7K`y cmr10ٓRcmr7Zcmr5O line10u cmex10s