logo资料库

Introduction to Modern Cryptography - Jonathan Katz & Yehuda Lindell.pdf

发布时间：2022-06-26 发布人：admin 分类：说明书 资料大小：2.64M 资料格式：pdf 举报 版权申诉
第1页 / 共512页
第2页 / 共512页
第3页 / 共512页
第4页 / 共512页
第5页 / 共512页
第6页 / 共512页
第7页 / 共512页
第8页 / 共512页
资料共512页，剩余部分请下载后查看
    2
    3
    Jonathan Katz and Yehuda Lindell Introduction to Modern Cryptography c2007 Jonathan Katz and Yehuda Lindell. All Rights Reserved CRC PRESS Boca Raton London New York Washington, D.C.
    Preface This book presents the basic paradigms and principles of modern cryptogra- phy. It is designed to serve as a textbook for undergraduate- or graduate-level courses in cryptography (in computer science or mathematics departments), as a general introduction suitable for self-study (especially for beginning grad- uate students), and as a reference for students, researchers, and practitioners. There are numerous other cryptography textbooks available today, and the reader may rightly ask whether another book on the subject is needed. We would not have written this book if the answer to that question were anything other than an unequivocal yes. The novelty of this book | and what, in our opinion, distinguishes it from all other books currently on the market | is that it provides a rigorous treatment of modern cryptography in an accessible manner appropriate for an introduction to the topic. To be sure, the material in this book is dicult (at least in comparison to some other books in this area). Rather than shy away from this diculty, however, we have chosen to face it head-on, to lead the reader through the demanding (yet enthralling!) subject matter rather than shield the reader’s eyes from it. We hope readers (and instructors) will respond by taking up the challenge. As mentioned, our focus is on modern (post-1980s) cryptography, which is distinguished from classical cryptography by its emphasis on denitions, precise assumptions, and rigorous proofs of security. We briey discuss each of these in turn (these principles are explored in greater detail in Chapter 1): The central role of denitions: A key intellectual contribution of modern cryptography has been the recognition that formal denitions of security are an essential rst step in the design of any cryptographic primitive or protocol. The reason, in retrospect, is simple: if you don’t know what it is you are trying to achieve, how can you hope to know when you have achieved it? As we will see in this book, cryptographic denitions of security are quite strong and | at rst glance | may appear impossible to achieve. One of the most amazing aspects of cryp- tography is that (under mild and widely-believed assumptions) ecient constructions satisfying such strong denitions can be proven to exist. The importance of formal and precise assumptions: As will be explained in Chapter 2, many cryptographic constructions cannot currently be proven secure in an unconditional sense. Security often relies, instead, on some widely-believed (albeit unproven) assumption. The modern cryptographic approach dictates that any such assumptions iii
    iv must be clearly and unambiguously dened. This not only allows for ob- jective evaluation of the assumption, but, more importantly, enables rigorous proofs of security as described next. The possibility of rigorous proofs of security: The previous two ideas lead naturally to the current one, which is the realization that cryp- tographic constructions can be proven secure with respect to a given def- inition of security and relative to a well-dened cryptographic assump- tion. This is the essence of modern cryptography, and was responsible for the transformation of cryptography from an art to a science. The importance of this idea cannot be over-emphasized. Historically, cryptographic schemes were designed in a largely ad-hoc fashion, and were deemed to be secure if the designers themselves could not nd any attacks. In contrast, modern cryptography promotes the design of schemes with formal, mathematical proofs of security in well-dened models. Such schemes are guaranteed to be secure unless the underly- ing assumption is false (or the security denition did not appropriately model the real-world security concerns). By relying on long-standing assumptions (e.g., the assumption that \factoring is hard"), it is thus possible to obtain schemes that are extremely unlikely to be broken. A unied approach. The above contributions of modern cryptography are felt not only within the \theory of cryptography" community. The importance of precise denitions is, by now, widely understood and appreciated by those in the security community (as well as those who use cryptographic tools to build secure systems), and rigorous proofs of security have become one of the requirements for cryptographic schemes to be standardized. As such, we do not separate \applied cryptography" from \provable security"; rather, we present practical and widely-used constructions along with precise statements (and, most of the time, a proof) of what denition of security is achieved. Guide to Using this Book This guide is intended primarily for instructors seeking to adopt this book for their course, though the student picking up this book on his or her own may also nd it useful. Required background. This book uses denitions, proofs, and mathemat- ical concepts, and therefore requires some mathematical maturity. In par- ticular, the reader is assumed to have had some exposure to proofs at the college level, say in an upper-level mathematics course or a course on discrete mathematics, algorithms, or computability theory. Having said this, we have made a signicant eort to simplify the presentation and make it generally accessible. It is our belief that this book is not more dicult than analogous textbooks that are less rigorous. On the contrary, we believe that (to take one
    v example) once security goals are clearly formulated, it often becomes easier to understand the design choices made in a particular construction. We have structured the book so that the only formal prerequisites are a course in algorithms and a course in discrete mathematics. Even here we rely on very little material: specically, we assume some familiarity with basic probability and big-O notation, modular arithmetic, and the idea of equating ecient algorithms with those running in polynomial time. These concepts are reviewed in Appendix A and/or when rst used in the book. Suggestions for course organization. The core material of this book, which we strongly recommend should be covered in any introductory course on cryptography, consists of the following (starred sections are excluded in what follows; see further discussion regarding starred material below): Chapters 1{4 (through Section 4.6), discussing classical cryptography, modern cryptography, and the basics of private-key cryptography (both private-key encryption and message authentication). Chapter 7, introducing concrete mathematical problems believed to be \hard", providing the number-theoretic background needed to under- stand RSA, Die-Hellman, and El Gamal, and giving a avor of how number-theoretic assumptions are used in cryptography. Chapters 9 and 10, motivating the public-key setting and discussing public-key encryption (including RSA-based schemes and El Gamal). Chapter 12, describing digital signature schemes. Sections 13.1 and 13.3, introducing the random oracle model and the RSA-FDH signature scheme. We believe that this core material | possibly omitting some of the more in-depth discussion and some proofs | can be covered in a 30{35-hour under- graduate course. Instructors with more time available could proceed at a more leisurely pace, e.g., giving details of all proofs and going more slowly when introducing the underlying group theory and number-theoretic background. Alternately, additional topics could be incorporated as discussed next. Those wishing to cover additional material, in either a longer course or a faster-paced graduate course, will nd that the book has been structured to allow exible incorporation of other topics as time permits (and depending on the instructor’s interests). Specically, some of the chapters and sections are starred (*). These sections are not less important in any way, but arguably do not constitute \core material" for an introductory course in cryptography. As made evident by the course outline just given (which does not include any starred material), starred chapters and sections may be skipped | or covered at any point subsequent to their appearance in the book | without aecting the ow of the course. In particular, we have taken care to ensure that none of
    vi the later un-starred material depends on any starred material. For the most part, the starred chapters also do not depend on each other (and in the rare cases when they do, this dependence is explicitly noted). We suggest the following from among the starred topics for those wishing to give their course a particular avor: Theory: A more theoretically-inclined course could include material from Sections 4.8 and 4.9 (dealing with stronger notions of security for private-key encryption); Chapter 6 (introducing one-way functions and hard-core bits, and constructing pseudorandom generators and pseu- dorandom functions/permutations starting from any one-way permuta- tion); Section 10.7 (constructing public-key encryption from trapdoor permutations); Chapter 11 (describing the Goldwasser-Micali, Rabin, and Paillier encryption schemes); and Section 12.6 (showing a signature scheme that does not rely on random oracles). Applications: An instructor wanting to emphasize practical aspects of cryptography is highly encouraged to cover Section 4.7 (describing HMAC); Chapter 5 (discussing modern block ciphers and techniques used in their design); and all of Chapter 13 (giving cryptographic con- structions in the random oracle model). Mathematics: A course directed at students with a strong mathematics background | or taught by someone who enjoys this aspect of cryp- tography | could incorporate material from Chapter 5 (see above) as well as Section 7.3.4 (elliptic-curve groups); Chapter 8 (algorithms for factoring and computing discrete logarithms); and Chapter 11 (describ- ing the Goldwasser-Micali, Rabin, and Paillier encryption schemes along with all the necessary number-theoretic background). Comments and Errata Our goal in writing this book was to make modern cryptography accessible to a wide audience outside the \theoretical computer science" community. We hope you will let us know whether we have succeeded. In particular, we are always more than happy to receive feedback on this book, especially construc- tive comments telling us how the book can be improved. We hope there are no errors or typos in the book; if you do nd any, however, we would greatly appreciate it if you let us know. (A list of known errata will be maintained at http://www.cs.umd.edu/~jkatz/imc.html.) You can email your com- ments and errata to jkatz@cs.umd.edu and lindell@cs.biu.ac.il; please put \Introduction to Modern Cryptography" in the subject line.
    vii Acknowledgements Jonathan Katz is deeply indebted to Zvi Galil, Moti Yung, and Rafail Os- trovsky for their help, guidance, and support throughout his career. This book would never have come to be without their contributions to his development, and he thanks them for that. He would also like to thank his colleagues with whom he has had numerous discussions on the \right" approach to writing a cryptography textbook, and in particular Victor Shoup. Yehuda Lindell wishes to rst and foremost thank Oded Goldreich and Moni Naor for introducing him to the world of cryptography. Their inuence is felt until today and will undoubtedly continue to be felt in the future. There are many, many other people who have also had considerable inuence over the years and instead of mentioning them all, he will just say thank you | you know who you are. Both authors would like to extend their gratitude to those who read and commented on earlier drafts of this book. We thank Salil Vadhan and Alon Rosen who experimented with this text in an introductory course on cryp- tography at Harvard and provided us with valuable feedback. We also thank all of the following for their many comments and corrections: Adam Bender, Yair Dombb, William Glenn, S. Dov Gordon, Carmit Hazay, Avivit Levy, Matthew Mah, Jason Rogers, Rui Xue, Dicky Yan, and Hila Zarosim. We are very grateful to all those who encouraged us to write this book and concurred with our feeling that a book of this nature is badly needed. Finally, we thank our (respective) wives and children for all their support and understanding during the many hours, days, and months that we have spent on this project.
    分享到：
    赞 收藏

    相关推荐

    资料库

    安全技术

    共收录1285份资料，累计4个分类，关注成员有19位，主要包括：网络攻防,系统安全,其它,网络安全

    热门标签

    网络攻防 系统安全 其它 网络安全

    最新资料