Lecture Notes in Computer Science 6673 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 Serge Fehr (Ed.) Information Theoretic Security 5th International Conference, ICITS 2011 Amsterdam, The Netherlands, May 21-24, 2011 Proceedings 1 3 VolumeEditor SergeFehr CentrumWiskunde&Informatica(CWI) SciencePark123,1098XGAmsterdam,TheNetherlands E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-20727-3 e-ISBN978-3-642-20728-0 DOI10.1007/978-3-642-20728-0 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2011926693 CRSubjectClassification(1998):E.3,D.4.6,F.2.1,C.2,K.4.4,K.6.5 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 ICITS2011,the5thInternationalConferenceonInformationTheoreticSecurity, was held in the city of Amsterdam, The Netherlands, during May 21–24, 2011. TheconferencetookplaceatCWI,theDutchCenterforMathematicsandCom- puter Science, and at the Trippenhuis, the headquarters of the Royal Dutch Academy of Arts and Sciences. Thegoalofthisconferenceseriesistobringtogethertheleadingresearchersin the field of information-theoretic cryptography.This area of cryptography aims atunderstandingthepossibilityandimpossibilityofcryptographicschemesthat offer information-theoretic security. Such a strong level of security, sometimes alsoreferredtoasunconditionalsecurity,isveryattractiveasitdoesnotrelyon unprovencomputationalhardnessassumptions,andinparticularalsowithstands attacks by quantum computers. The price for this level of security often comes in the form of less efficiency and/or some physical assumption. Understanding the minimal requirements for information-theoretic security is a central part of this line of research.Personally,what I find very attractive is the mathematical neatnessofthefield,anditsrichconnectionstootherareasofmathematics,such asprobabilityandinformationtheory,algebra,combinatorics,codingtheory,and quantum information processing, just to mention the most prominent ones. Therewere 27submitted papersofwhich10wereselected.Eachcontributed paper wasreviewedby atleastthree members ofthe ProgramCommittee. Sub- missionsco-authoredbyProgramCommitteememberswerereviewedbyatleast five members. The Program Committee worked hard to review and discuss the submissions,andtofinally selectthe bestpapersamongthem.Itwasapleasure to work together with such a motivated and professional Program Committee. I would like to thank each member for his/her contribution. I also thank the external reviewers who assisted the Program Committee members during the reviewing process. In addition to the accepted papers, the conference also featured nine invited speakers.Eachinvitedspeakerprovidedasummaryofhispresentationasacon- tribution to these proceedings. The invited speakers were: Benny Applebaum, Alexander Barg, Imre Csisz´ar, Ivan Damg˚ard, Yuval Ishai, Renato Renner, Leonid Reyzin, Amin Shokrollahi, and Ronald de Wolf. Asanewcomponent,ICITS2011featuredaRumpSession:aninformalafter- noonprogramthatgavealltheattendeesthepossibilityforashortpresentation on a topic of their choosing. I hope that this turns into a tradition for future ICITS conferences. I would like to thank the two GeneralChairs,Ronald Cramerand Krzysztof Pietrzak,fororganizingtheconferenceandforensuringasmoothrunningofthe event. I would also like to thank Niek Bouman for chairing the Rump Session, and Joachim Schipper for his work behind the scenes. Furthermore, my thanks VI Preface go to the local support staff at CWI, in particular to Susanne van Dam for her unwavering organizational assistances, and to Maarten Dijkema and Chris Wesseling for setting-up and maintaining the submission system. I used Shai Halevi’s Web Submission And Review Software; this is a very handy system which was of great help to me to perform my work as ProgramChair, and Shai was always very prompt in answering questions. Lastbutnotleast,Iwouldliketothankalltheauthorswhosubmittedpapers to the conference and all the attendees of the conference; you are the ones that make ICITS possible. May 2011 Serge Fehr ICITS 2011 The 5th International Conference on Information Theoretic Security CWI Amsterdam, The Netherlands May 21–24,2011. Supported by an NWO1 VICI grant General Chairs Ronald Cramer CWI Amsterdam, and Mathematical Institute Leiden University, The Netherlands Krzysztof Pietrzak CWI Amsterdam, The Netherlands Program Chair Serge Fehr CWI Amsterdam, The Netherlands Program Committee Amos Beimel Ben-Gurion University, Israel Nishanth Chandran UCLA, USA Hao Chen East China Normal University, China Paolo D’Arco University of Salerno, Italy Stefan Dziembowski La Sapienza, Italy Serge Fehr, Chair CWI, The Netherlands Juan Garay AT&T Labs – Research, USA Vipul Goyal Microsoft Research, India Maria Isabel Gonza´lez Vasco University Rey Juan Carlos, Spain Kaoru Kurosava Ibaraki University, Japan Eyal Kushilevitz Technion, Israel Keith Martin Royal Holloway, UK Jesper Buus Nielsen Aarhus University, Denmark Carles Padro´ Nanyang TechnologicalUniversity, Singapore Reihaneh Safavi-Naini University of Calgary, Canada Louis Salvail University of Montreal, Canada Christian Schaffner CWI, The Netherlands Berry Schoenmakers TU Eindhoven, The Netherlands Adam Smith Pennsylvania State University, USA Tamir Tassa The Open University, Israel Dominique Unruh Saarland University, Germany Daniel Wichs New York University, USA Ju¨rg Wullschleger Universit´e de Montr´ealand McGill, Canada 1 NetherlandsOrganisation for ScientificResearch. VIII ICITS 2011 Steering Committee Carlo Blundo University of Salerno, Italy Gilles Brassard University of Montreal, Canada Ronald Cramer CWI and Leiden University, The Netherlands Yvo Desmedt, Chair University College London, UK Hideki Imai AIST and Chuo University, Japan Kaoru Kurosawa Ibaraki University, Japan Ueli Maurer ETH, Switzerland C. Pandu Rangan IIT, Madras and IIT, Hyderabad, India Reihaneh Safavi-Naini University of Calgary, Canada Doug Stinson University of Waterloo, Canada Moti Yung Google and Columbia University, USA Yuliang Zheng UniversityofNorthCarolinaatCharlotte,USA External Referees Hadi Ahmadi Matthias Fitzi Gil Segev Mohsen Alimomeni Goichiro Hanaoka Ashraful Tuhin Gilad Asharov Michael Langberg Severin Winkler Seung Geol Choi Steve Lu He Xiang Ashish Choudhury Hemanta Maji Vassilis Zikas Stelvio Cimato Ilan Orlov Fr´ed´eric Dupuis Anat Paskin Sebastian Faust Angel L. Perez del Pozo Table of Contents CorrelationExtractors and Their Applications (Invited Talk).......... 1 Yuval Ishai Characterization of the Relations between Information-Theoretic Non-malleability, Secrecy, and Authenticity ......................... 6 Akinori Kawachi, Christopher Portmann, and Keisuke Tanaka Randomly Encoding Functions: A New Cryptographic Paradigm (Invited Talk) ................................................... 25 Benny Applebaum MinimalConnectivityforUnconditionallySecureMessageTransmission in Synchronous Directed Networks ................................. 32 Manan Nayak, Shashank Agrawal, and Kannan Srinathan Quantum-Resilient Randomness Extraction (Invited Talk) ............ 52 Renato Renner Homogeneous Faults, Colored Edge Graphs, and Cover Free Families ... 58 Yongge Wang and Yvo Desmedt On Information Theoretic Security: Mathematical Models and Techniques (Invited Talk) ......................................... 73 Imre Csisza´r Common Randomness and Secret Key Capacities of Two-Way Channels ....................................................... 76 Hadi Ahmadi and Reihaneh Safavi-Naini LT-Codes and Phase Transitions for Mutual Information (Invited Talk) ................................................... 94 Amin Shokrollahi Unconditionally Secure Signature Schemes Revisited.................. 100 Colleen M. Swanson and Douglas R. Stinson Bell Inequalities: What Do We Know about Them and Why Should Cryptographers Care? (Invited Talk) ............................... 117 Ronald de Wolf Efficient Reductions for Non-signaling Cryptographic Primitives ....... 120 Nico D¨ottling, Daniel Kraschewski, and J¨orn Mu¨ller-Quade X Table of Contents Some Notions of Entropy for Cryptography (Invited Talk)............. 138 Leonid Reyzin The Round Complexity of Perfectly Secure General VSS .............. 143 Ashish Choudhury, Kaoru Kurosawa, and Arpita Patra Graceful Degradation in Multi-Party Computation ................... 163 Martin Hirt, Christoph Lucas, Ueli Maurer, and Dominik Raub Quantum Communication Attacks on Classical Cryptographic Protocols (Invited Talk) .......................................... 181 Ivan Damg˚ard Using Colors to Improve Visual Cryptography for Black and White Images ......................................................... 182 Roberto De Prisco and Alfredo De Santis Digital Fingerprinting under and (Somewhat) beyond the Marking Assumption (Invited Talk) ........................................ 202 Alexander Barg and Grigory Kabatiansky Communication Optimal Multi-valued Asynchronous Byzantine Agreement with Optimal Resilience ................................ 206 Arpita Patra and C. Pandu Rangan Author Index.................................................. 227