Lecture Notes in Computer Science 6558 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Aggelos Kiayias (Ed.) Topics in Cryptology – CT-RSA 2011 The Cryptographers’Track at the RSA Conference 2011 San Francisco, CA, USA, February 14-18, 2011 Proceedings 1 3 VolumeEditor AggelosKiayias NationalandKapodistrianUniversityofAthens DepartmentofInformaticsandTelecommunications Panepistimiopolis,Ilisia,Athens15784,Greece E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-19073-5 e-ISBN978-3-642-19074-2 DOI10.1007/978-3-642-19074-2 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2010943110 CRSubjectClassification(1998):E.3,D.4.6,K.6.5,C.2,K.4.4 LNCSSublibrary:SL4–SecurityandCryptology ©Springer-VerlagBerlinHeidelberg2011 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface The RSAconferencewasinitiatedin1991andisamajorinternationaleventfor cryptographyandinformationsecurityresearchersaswellastheindustryrelated to these disciplines. It is an annual event that attracts hundreds of vendors and thousands of participants from industry and academia. Since 2001, the RSA conference has included the Cryptographers’Track(called the CT-RSA), which enablestheforefrontofcryptographicresearchtobepresentedwithintheformal program of the conference. CT-RSA has become a major publication venue for cryptographers worldwide. This year the RSA conference was held in San Francisco, California, during February14–18,2011.TheCT-RSAconferenceserverswererunninginthe Uni- versity of Athens, Greece, and we received 82 submissions out of which 3 were withdrawn.Everypaperwasreviewedbyatleastthreecommitteemembers.The ProgramCommitteememberswerealsoallowedtosubmituptoonepaperforin- clusionintheprogram.Suchpaperswerereviewedbyatleastfivecommitteemem- bers.Thereviewingofthesubmissionsproceededintwostages:inthefirststage paperswerereadindividuallybycommitteememberswithoutknowledgeofother committeemembers’opinions.Inthesecondstage,allreviewsweremadeavailable tocommitteemembersanddiscussionthroughaWebbulletinboardensued.After atotalofsevenweeksthecommitteeworkconcludedandaselectionof24papers wasmadeforinclusionintheconferenceprogram.Inasmallnumberofcasesafinal roundofreviewingtookplaceassomeofthepaperswereacceptedconditionallyon specificchangesthatwererequestedbytheProgramCommittee.Thefinalrevised versionsoftheacceptedpapersiswhatyouwillfindinthisvolume. WewereverypleasedthisyeartohavethreekeynotetalksincludedintheCT- RSA program. Dan Boneh from Stanford University gave a talk on computing with signed data. Dickie George of the Information Assurance Directorate at NSA spoke on NSA’s role in the development of DES. Adi Shamir from the Weizmann Institute of Science gave a talk on the role of academia and industry in the designand analysis of DES. The talk also featured a mini-talk by Martin Hellman on that subject. Anumberofpeopleplayedkeyrolesinthesuccessoftheconferencethisyear. First and foremost I would like to thank the authors of all submitted papers; withouttheircontributionstheconferencewouldnothavebeenpossible.Second, a special thanks is due to the members of the Program Committee and the subreviewersthat invested a lot of their time in carefully reading the submitted papers and contributing to the discussion of each paper. The submission and review process was supported by the Web submission software written by Shai Halevi. I would also like to thank Bree LaBollita and Amy Szymanski, who worked very hard to properly organize the conference this year. December 2010 Aggelos Kiayias CT-RSA 2011 The 11th Cryptographers’ Track – RSA 2011 San Francisco, California, USA February 14–18,2011 Program Chair Aggelos Kiayias University of Athens, Greece Steering Committee Masayuki Abe NTT, Japan Ari Juels RSA Laboratories,USA Tal Malkin Columbia University, USA Josef Pieprzyk Macquarie University, Australia Ron Rivest MIT, USA Moti Yung Google, USA Program Committee Giuseppe Ateniese Johns Hopkins University, USA Sasha Boldyreva Georgia Tech, USA Xavier Boyen Universit´e de Li`ege, Belgium Christophe De Canni`ere KU Leuven, Belgium Jung Hee Cheon Seoul National University, Korea Joo Yeon Cho Nokia, Denmark Orr Dunkelman Weizmann Institute, Israel Steven Galbraith University of Auckland, New Zealand Craig Gentry IBM Research, USA Philippe Golle Google, USA Louis Goubin Universit´e de Versailles, France Iftach Haitner Tel Aviv University, Israel Amir Herzberg Bar Ilan University, Israel Dennis Hofheinz Karlsruhe University, Germany Stanislaw Jarecki UC Irvine, USA Marc Joye Technicolor, France Ralf Ku¨sters University of Trier, Germany Anna Lysyanskaya Brown University, USA VIII Organization Alexander May Ruhr University Bochum, Germany Daniele Micciancio UCSD, USA Tal Moran Harvard University, USA Antonio Nicolosi Stevens Institute of Technology, USA Tatsuaki Okamoto NTT, Japan Rafail Ostrovsky UCLA, USA Josef Pieprzyk Macquarie University, Australia David Pointcheval ENS, France Berry Schoenmakers TU Eindhoven, The Netherlands Alice Silverberg UC Irvine, USA Martijn Stam Royal Holloway, University of London, UK Franc¸ois-Xavier Standaert UCL, Belgium Berk Sunar WPI, USA Nikos Triandopoulos RSA LaboratoriesandBostonUniversity,USA Huaxiong Wang NTU, Singapore Bogdan Warinschi University of Bristol, UK External Reviewers Onur Aciicmez Dimitar Jetchev Kahraman Akdemir Deniz Karakoyunlu Martin Albrecht HongTae Kim Gilad Asharov Jihye Kim Roberto Avanzi Jinsoo Kim Foteini Baldimtsi Minkyu Kim Lejla Batina Taechan Kim Carl Bosley Mikkel Krøig˚ard Ran Canetti Ranjit Kumaresan Sherman S.M. Chow Hyung Tae Lee L´eonardDallot Anja Lehmann Yevgeniy Dodis Helger Lipmaa Gwena¨el Do¨err David M’Raihi Nelly Fazio Ilya Mironov Nicolas Gama Daisuke Moriyama Hossein Ghodosi Erdinc Ozturk Yossi Gilad Charalampos Papamanthou Choudary Gorantla Olivier Pereira Jian Guo Ludovic Perret Ghaith Hammouri Christophe Petit Malin Md Mokammel Haque Nicolas Prigent Mathias Herrmann Tal Rabin Susan Hohenberger Francesco Regazzoni Yin Hu Andy Rupp Xinyi Huang Jae Hong Seo Malika Izabachene Elaine Shi Organization IX Haya Shulman Max Tuengerthal Radu Sion Nicolas Veyrat-Charvillon Ron Steinfeld Andreas Vogt Hung-Min Sun Liang Feng Zhang Stefano Tessaro Hong-Sheng Zhou Tomasz Truderung Vassilis Zikas