Lecture Notes in Computer Science 3796 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Nigel P. Smart (Ed.) Cryptography and Coding 10th IMA International Conference Cirencester, UK, December 19-21, 2005 Proceedings 1 3 VolumeEditor NigelP.Smart UniversityofBristol DepartmentofComputerScience WoodlandRoad,Bristol,BS81UB,UK E-mail:[email protected] LibraryofCongressControlNumber:2005936359 CRSubjectClassification(1998):E.3-4,G.2.1,C.2,J.1 ISSN 0302-9743 ISBN-10 3-540-30276-XSpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-30276-6SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springeronline.com ©Springer-VerlagBerlinHeidelberg2005 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11586821 06/3142 543210 Preface The10thintheseriesofIMAConferencesonCryptographyandCodingwasheld atthe RoyalAgriculturalCollege,Cirencester,during19–21December2005.As usual, the venue provided a relaxed and informal atmosphere for attendees to discuss work and listen to the collection of talks. The program consisted of four invited talks and 26 contributed talks. The invitedtalkswheregivenbyTuviEtzion,UeliMaurer,AlfredMenezesandAmin Shokrollahi, and three of these invited talks appear as papers in this volume. Special thanks must goto these four speakersasthey helped to set the tone,by coveringalltheareasthemeetingaimedtocover,fromcryptographythroughto coding. In addition the best speakers are often the hardestto persuade to come to a meeting, as they are usually the most busy. We therefore feel privileged to have had a meeting with four such distinguished speakers. The contributedtalkswereselectedfrom94submissions.This isnearlytwice thenumberofsubmissionsforthepreviousmeetingin2003.Thisisanindication of the strength of the subject and the interest in the IMA series of meetings as a venue to present new work. The contributed talks rangedover a wide number of areas,including informationtheory, coding theory,number theory and asym- metric and symmetric cryptography. Subtopics included a number of current “hot topics,” such as algebraic cryptanalysis and cryptographic systems based on bilinear pairings. Assembling the conference program and these proceedings required the help of a large number of individuals. I would like to thank them all here. Firstly,thanksmustgotothe ProgramCommittee andtheirsubrefereeswho aided in evaluating the contributed papers and coming to a difficult decision as to what to include and what to exclude. We had to reject a number of papers simply due to lack of space. ForthefirsttimetheIMAProgramCommitteeusedtheWebReviewsoftware fromK.U. Leuven.This is an excellentprogram,whichgreatly helped myselfas Program Chair in collating and mediating the referee reports. Thanks must go to the authors and maintainers of this program.Particular thanks must also go to Richard Noad, one of my Research Assistants at Bristol, who dealt with all the technical issues with mounting the servers and generally acted as a right- hand-man throughout the process. Thanksmustalsogototheauthorsofthesubmittedpapers,andinparticular to those whose papers were accepted. The authors of the accepted papers co- operated in compiling this volume, often meeting very tight deadlines imposed by the publication schedule. Thanks must also go to the staff of Springer, in particular Alfred Hofmann who helped in a large number of ways. Valuable sponsorshipof the meeting was providedby Hewlett-PackardLabo- ratories and Vodafone. We thank them for their contributions. VI Preface Finally,thanksmustgotothestaffoftheIMA,inparticularPamelaByeand Lucy Nye, who dealt with all the day-to-day issues and allowed the Program Committee to concentrate on the science. A conference such as this could not take place without their help. September 2005 Nigel Smart ProgramChair Cryptography and Coding 2005 December 19–21, 2005, Cirencester, United Kingdom Sponsored by the The Institute of Mathematics and its Applications (IMA) in cooperation with Hewlett-Packard Laboratories and Vodafone Ltd. Program Chair Nigel Smart ..................................University of Bristol Program Committee Steve Babbage..................................Vodafone Group Services Ltd. Bahram Honary ......................................University of Lancaster Steven Galbraith .......................Royal Holloway,University of London Chris Mitchell ..........................Royal Holloway,University of London David Naccache ....................................E´cole Normale Sup´erieure Matthew Parker .........................................University of Bergen Kenny Paterson ........................Royal Holloway,University of London Ana Salagean .......................................LoughboroughUniversity Frederik Vercauteren ............................................K.U. Leuven Mike Walker ...................................Vodafone Group Services Ltd. Gilles Zemor ....................................................ENST, Paris External Referees Claude Barral Nicolas Gresset Dan Page Eric Brier Helena Handschuh Havard Raadum Alister Burr Marc Joye Vincent Rijmen Julien Cathalo Caroline Kudla Jasper Scholten BenoitChevallier-Mames Arjen Lenstra Martijn Stam Carlos Cid John Malone-Lee Emmanuel Thom´e Mathieu Ciet Keith Martin Claire Whelan Gerard Cohen Philippe Martins Andreas Winter Nicolas Courtois Jean Monnerat Christopher Wolf Alex Dent David M’Raihi Jean-Franc¸ois Dhem Gregory Neven Eran Edirisinghe Katie O’Brien Table of Contents Invited Papers Abstract Models of Computation in Cryptography U. Maurer .................................................... 1 Pairing-BasedCryptography at High Security Levels N. Koblitz, A. Menezes ......................................... 13 Improved Decoding of Interleaved AG Codes A. Brown, L. Minder, A. Shokrollahi ............................. 37 Coding Theory Performance Improvement of Turbo Code Based on the Extrinsic Information Transition Characteristics W.T. Kim, S.H. Kang, E.K. Joo................................. 47 A Trellis-Based Bound on (2,1)-Separating Codes H.G. Schaathun, G.D. Cohen.................................... 59 Tessellation Based Multiple Description Coding C. Cai, J. Chen ............................................... 68 Exploiting Coding Theory for Collision Attacks on SHA-1 N. Pramstaller, C. Rechberger, V. Rijmen......................... 78 Signatures and Signcryption Hash Based Digital Signature Schemes C. Dods, N.P. Smart, M. Stam .................................. 96 A General Construction for Simultaneous Signing and Encrypting J. Malone-Lee ................................................. 116 Non-interactive Designated Verifier Proofs and Undeniable Signatures C. Kudla, K.G. Paterson ....................................... 136 X Table of Contents Symmetric Cryptography Partial Key Recovery Attacks on XCBC, TMAC and OMAC C.J. Mitchell .................................................. 155 Domain Expansion of MACs: Alternative Uses of the FIL-MAC U. Maurer, J. Sj¨odin ........................................... 168 Normality of Vectorial Functions A. Braeken, C. Wolf, B. Preneel ................................. 186 Related-Key Differential Attacks on Cobra-H64 and Cobra-H128 C. Lee, J. Kim, J. Sung, S. Hong, S. Lee, D. Moon ................ 201 Side Channels The Physically Observable Security of Signature Schemes A.W. Dent, J. Malone-Lee ...................................... 220 On the Automatic Construction of Indistinguishable Operations M. Barbosa, D. Page ........................................... 233 Efficient Countermeasures for Thwarting the SCA Attacks on the Frobenius Based Methods M. Hedabou ................................................... 248 Algebraic Cryptanalysis Complexity Estimates for the F Attack on the Perturbed 4 Matsumoto-Imai Cryptosystem J. Ding, J.E. Gower, D. Schmidt, C. Wolf, Z. Yin ................. 262 An Algebraic Framework for Cipher Embeddings C. Cid, S. Murphy, M.J.B. Robshaw ............................. 278 Probabilistic Algebraic Attacks A. Braeken, B. Preneel ......................................... 290 Table of Contents XI Information Theoretic Applications Unconditionally Secure Information Authentication in Presence of Erasures G. Jakimoski .................................................. 304 Generalized Strong Extractors and Deterministic Privacy Amplification R. Ko¨nig, U. Maurer ........................................... 322 On Threshold Self-healing Key Distribution Schemes G. Sa´ez ...................................................... 340 Number Theoretic Foundations Concrete Security of the Blum-Blum-Shub Pseudorandom Generator A. Sidorenko, B. Schoenmakers .................................. 355 The Equivalence Between the DHP and DLP for Elliptic Curves Used in Practical Applications, Revisited K. Bentahar .................................................. 376 Pairings on Elliptic Curves over Finite Commutative Rings S.D. Galbraith, J.F. McKee ..................................... 392 Public Key and ID-Based Encryption Schemes A Key Encapsulation Mechanism for NTRU M. Stam ...................................................... 410 Efficient Identity-Based Key Encapsulation to Multiple Parties M. Barbosa, P. Farshim ........................................ 428 Security Proof of Sakai-Kasahara’sIdentity-Based Encryption Scheme L. Chen, Z. Cheng ............................................. 442 Author Index................................................... 461 Abstract Models of Computation in Cryptography Ueli Maurer(cid:2) Department of Computer Science, ETH Zurich, CH-8092 Zurich,Switzerland [email protected] Abstract. Computationalsecurityproofsincryptography,withoutun- proven intractability assumptions, exist today only if one restricts the computational model.Forexample,onecan provealowerboundon the complexityofcomputingdiscretelogarithmsinacyclicgroupifonecon- sidersonlygenericalgorithmswhichcannotexploitthepropertiesofthe representation of thegroup elements. Weproposeanabstractmodelofcomputationwhichallowstocapture such reasonable restrictions on the power of algorithms. The algorithm interactswithablack-boxwith hiddeninternalstatevariableswhichal- lowstoperformacertainsetofoperationsontheinternalstatevariables, andwhichprovidesoutputonlybyallowingtocheckwhethersomestate variablessatisfycertainrelations.Forexample,genericalgorithmscorre- spond to the special case where only the equality relation, and possibly also an abstract total order relation, can be tested. We consider several instantiation of the model and different types of computational problems and prove a few known and new lower bounds forcomputationalproblemsofinterestincryptography,forexamplethat computing discrete logarithms is generically hard even if an oracle for thedecisional Diffie-Hellman problemand/or other low degree relations were available. 1 Introduction and Motivation 1.1 Restricted Models of Computation Proving the security of a certain cryptographic system means to prove a lower bound on the hardness of a certain computational problem. Unfortunately, for generalmodelsofcomputationnousefullowerboundproofsareknown,anditis therefore interesting to investigate reasonably restricted models of computation if one can prove relevant lower bounds for them. In a restricted model one assumes that only certain types of operations are allowed.Forexample,inthemonotonecircuitmodeloneassumesthatthecircuit performingthecomputationconsistsonlyofAND-gatesandOR-gates,excluding NOT-gates. Such a restriction is uninteresting from a cryptographic viewpoint since it is obvious that an adversary can of course perform NOT-operations. (cid:2) Supportedin part bytheSwiss National Science Foundation. N.P.Smart(Ed.):CryptographyandCoding2005,LNCS3796,pp.1–12,2005. (cid:2)c Springer-VerlagBerlinHeidelberg2005