Foundations of Cryptography: Volume 2, Basic Applications

Cryptography is concerned with the conceptualization, definition, and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. Building on the basic tools presented in the first volume, this second volume of Foundations of Cryptography contains a rigorous and systematic treatment of three basic applications: Encryption, Signatures, and General Cryptographic Protocols. It is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful. Also available: Volume I: Basic Tools 0-521-79172-3 Hardback $75.00 C Foundations of Cryptography II Basic Applications......Page 4 Contents II Basic Applications......Page 8 List of Figures......Page 12 Preface......Page 14 Acknowledgments......Page 22 5 Encryption Schemes......Page 24 5.1. The Basic Setting......Page 25 5.2. De.nitions of Security......Page 29 5.3. Constructions of Secure Encryption Schemes......Page 54 5.4.* Beyond Eavesdropping Security......Page 73 5.5. Miscellaneous......Page 125 6 Digital Signatures and Message Authentication......Page 148 6.1. The Setting and De.nitional Issues......Page 149 6.2. Length-Restricted Signature Scheme......Page 158 6.3. Constructions of Message-Authentication Schemes......Page 174 6.4. Constructions of Signature Schemes......Page 188 6.5.* Some Additional Properties......Page 226 6.6. Miscellaneous......Page 235 7 General Cryptographic Protocols......Page 250 7.1. Overview......Page 251 7.2.* The Two-Party Case: De.nitions......Page 266 7.3.* Privately Computing (Two-Party) Functionalities......Page 285 7.4.* Forcing (Two-Party) Semi-Honest Behavior......Page 301 7.5.* Extension to the Multi-Party Case......Page 344 7.6.* Perfect Security in the Private Channel Model......Page 392 7.7. Miscellaneous......Page 398 C.1. Enhanced Trapdoor Permutations......Page 416 C.3. On Strong Witness Indistinguishability......Page 419 C.4. On Non-Interactive Zero-Knowledge......Page 423 C.5. Some Developments Regarding Zero-Knowledge......Page 426 C.6. Additional Corrections and Comments......Page 434 C.7. Additional Mottoes......Page 435 Bibliography......Page 436 Index......Page 446 Cambridge University Press Foundations of Cryptography II Basic Applications 4 Contents II Basic Applications 8 List of Figures 12 Preface 14 Acknowledgments 22 5 Encryption Schemes 24 5.1. The Basic Setting 25 5.2. De.nitions of Security 29 5.3. Constructions of Secure Encryption Schemes 54 5.4.* Beyond Eavesdropping Security 73 5.5. Miscellaneous 125 6 Digital Signatures and Message Authentication 148 6.1. The Setting and De.nitional Issues 149 6.2. Length-Restricted Signature Scheme 158 6.3. Constructions of Message-Authentication Schemes 174 6.4. Constructions of Signature Schemes 188 6.5.* Some Additional Properties 226 6.6. Miscellaneous 235 7 General Cryptographic Protocols 250 7.1. Overview 251 7.2.* The Two-Party Case: De.nitions 266 7.3.* Privately Computing (Two-Party) Functionalities 285 7.4.* Forcing (Two-Party) Semi-Honest Behavior 301 7.5.* Extension to the Multi-Party Case 344 7.6.* Perfect Security in the Private Channel Model 392 7.7. Miscellaneous 398 Appendix C: Corrections and Additions to Volume 1 416 C.1. Enhanced Trapdoor Permutations 416 C.2. On Variants of Pseudorandom Functions 419 C.3. On Strong Witness Indistinguishability 419 C.4. On Non-Interactive Zero-Knowledge 423 C.5. Some Developments Regarding Zero-Knowledge 426 C.6. Additional Corrections and Comments 434 C.7. Additional Mottoes 435 Bibliography 436 Index 446 9780521119917 Cryptography is concerned with the conceptualization, definition and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. Foundations of Cryptography presents a rigorous and systematic treatment of foundational issues, defining cryptographic tasks and solving cryptographic problems. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems, as opposed to describing ad-hoc approaches. This second volume contains a thorough treatment of three basic applications: Encryption, Signatures, and General Cryptographic Protocols. It builds on the previous volume, which provided a treatment of one-way functions, pseudorandomness, and zero-knowledge proofs. It is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful. Annotation Cryptography is concerned with the conceptualization, definition, and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. Building on the basic tools presented in the first volume, this second volume of Foundations of Cryptography contains a rigorous and systematic treatment of three basic applications: Encryption, Signatures, and General Cryptographic Protocols. It is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful. Also available: Volume I: Basic Tools 0-521-79172-3 Hardback $75.00 C