vol., r. cramer, ed., springer-verlag. this is the full version. on the impossibility of hi

《vol., r. cramer, ed., springer-verlag. this is the full version. on the impossibility of hi》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Anabridgedversion,reference[1],appearsasAdvancesinCryptology{Eurocrypt'05,LectureNotesinComputerScience,Vol.????,R.Cramer,ed.,Springer-Verlag.Thisisthefullversion.OntheImpossibilityofHighly-EcientBlockcipher-BasedHashFunctionsJ.BlackM.CochranT.ShrimptonyAbstractFixasmall,non-emptysetofblockc

2、ipherkeysK.Wesayablockcipher-basedhashfunctionishighly-ecientifitmakesexactlyoneblockciphercallforeachmessageblockhashed,andallblockciphercallsuseakeyfromK.Althoughafewhighly-ecientconstructionshavebeenproposed,noonehasbeenabletoprovetheirsecurity.Inthispaperweprove,intheideal-ciphermodel,tha

3、titisimpossibletoconstructahighly-ecientiteratedblockcipher-basedhashfunctionthatisprovablysecure.Ourresultimplies,inparticular,thattheTweakableChainHash(TCH)constructionsuggestedbyLiskov,Rivest,andWagner[7]isnotcorrectunderaninstantiationsuggestedforthisconstruction,norcanTCHbecorrectlyinstan

4、tiatedbyanyotherecientmeans.Keywords:Collision-resistanthashfunctions,tweakableblockciphers,provablesecurity.DepartmentofComputerScience,430UCB,Boulder,Colorado80309USA.E-mail:jrblack@cs.colorado.edu,Mar-tin.Cochran@colorado.eduWWW:www.cs.colorado.edu/jrblack/,ucsu.colorado.edu/cochranmyDep

5、artmentofComputerScience,PortlandStateUniversity,Portland,Oregon,97207,USA.E-mail:teshrim@cs.pdx.eduWWW:www.cs.pdx.edu/teshrim/Contents1Introduction12SecurityDenitions43HashFunctionConstructionsandAttacks54TheTweakChainHash105ConclusionandOpenProblems12minhi1>Ef(hi1;mi)nnnnnFigure1:TheMatya

6、s-Meyer-Oseas(MMO)compressionfunction[8].E:f0;1gf0;1g!f0;1gisablockcipher;thehatchmarkdenotesthelocationofthekey.Iteratingthiscompressionfunctionresultsinaprovably-securehashfunction[2],howevernoticethattheabovecompressionfunctionwillberekeyedeachround.1IntroductionBackground.Essentiallyallmod

7、ernhashfunctionsarebuiltbyiteratingacompressionfunctionaccordingtotheMerkle-Damgardparadigm[4,10].Moreover,thesecompressionfunctionsarealmostalwaysbuiltfromablockcipher.ConstructionsliketheMatyas-Meyer-Oseas(MMO)compressionfuncti