The Theory of Hash Functions and Random Oracles

Hash functions are the cryptographer's Swiss Army knife. Even though they play an integral part in today's cryptography, existing textbooks discuss hash functions only in passing and instead often put an emphasis on other primitives like encryption schemes. In this book the authors take a different approach and place hash functions at the center. The result is not only an introduction to the theory of hash functions and the random oracle model but a comprehensive introduction to modern cryptography.

After motivating their unique approach, in the first chapter the authors introduce the concepts from computability theory, probability theory, information theory, complexity theory, and information-theoretic security that are required to understand the book content. In Part I they introduce the foundations of hash functions and modern cryptography. They cover a number of schemes, concepts, and proof techniques, including computational security, one-way functions, pseudorandomness and pseudorandom functions, game-based proofs, message authentication codes, encryption schemes, signature schemes, and collision-resistant (hash) functions. In Part II the authors explain the random oracle model, proof techniques used with random oracles, random oracle constructions, and examples of real-world random oracle schemes. They also address the limitations of random oracles and the random oracle controversy, the fact that uninstantiable schemes exist which are provably secure in the random oracle model but which become insecure with any real-world hash function. Finally in Part III the authors focus on constructions of hash functions. This includes a treatment of iterative hash functions and generic attacks against hash functions, constructions of hash functions based on block ciphers and number-theoretic assumptions, a discussion of privately keyed hash functions including a full security proof for HMAC, and a presentation of real-world hash functions.

The text is supported with exercises, notes, references, and pointers to further reading, and it is a suitable textbook for undergraduate and graduate students, and researchers of cryptology and information security.

Self-contained textbook explains the foundations of modern cryptography Supported with exercises, notes, references, and pointers to further reading Authors introduce the theoretical foundations of the Random Oracle methodology Suitable for undergraduate and graduate students of cryptology, information security, and computational complexity

Auteur

Dr. Arno Mittelbach is the Director of Development at AGT International. He received his PhD from Technische Universität Darmstadt in 2015. Prof. Dr. Marc Fischlin has been Professor for Cryptography and Complexity Theory at the Technische Universität Darmstadt since 2011. He previously held postdoctoral positions at research institutes such as the Fraunhofer Institute for Secure IT, University of California, San Diego, and ETH Zürich. His team's main research area is complexity-based cryptography.

Texte du rabat

Hash functions are the cryptographer s Swiss Army knife. Even though they play an integral part in today s cryptography, existing textbooks discuss hash functions only in passing and instead often put an emphasis on other primitives like encryption schemes. In this book the authors take a different approach and place hash functions at the center. The result is not only an introduction to the theory of hash functions and the random oracle model but a comprehensive introduction to modern cryptography. After motivating their unique approach, in the first chapter the authors introduce the concepts from computability theory, probability theory, information theory, complexity theory, and information-theoretic security that are required to understand the book content. In Part I they introduce the foundations of hash functions and modern cryptography. They cover a number of schemes, concepts, and proof techniques, including computational security, one-way functions, pseudorandomness and pseudorandom functions, game-based proofs, message authentication codes, encryption schemes, signature schemes, and collision-resistant (hash) functions. In Part II the authors explain the random oracle model, proof techniques used with random oracles, random oracle constructions, and examples of real-world random oracle schemes. They also address the limitations of random oracles and the random oracle controversy, the fact that uninstantiable schemes exist which are provably secure in the random oracle model but which become insecure with any real-world hash function. Finally in Part III the authors focus on constructions of hash functions. This includes a treatment of iterative hash functions and generic attacks against hash functions, constructions of hash functions based on block ciphers and number-theoretic assumptions, a discussion of privately keyed hash functions including a full security proof for HMAC, and a presentation of real-world hash functions. The text is supported with exercises, notes, references, and pointers to further reading, and it is a suitable textbook for undergraduate and graduate students, and researchers of cryptology and information security.

Résumé

"The authors put a lot of work to create this 788-page book - the text has been edited even after the layout to insert links with page numbers, there are exercises and a website for errata and discussions." (Jaak Henno, zbMATH 1490.94001, 2022)

"Arno Mittelbach and Marc Fischlin did a good job at producing this book with a collection of ideas on the Theory of Hash Functions and Random Oracles, focusing in-depth on these two areas enabling the student, the practitioner, and the researcher, to deepen their knowledge. The book is a great add-on for a modern cryptography course or for 'light summer reading' for those interested in learning more about these two topics." (Sven Dietrich, IEEE Cipher, July 20, 2021)

Contenu

Introduction.- Preliminaries: Cryptographic Foundations.- Part I: Foundations.- Computational Security.- Pseudorandomness and Computational Indistinguishability.- Collision Resistance.- Encryption Schemes.- Signature Schemes.- Non-cryptographic Hashing.- Part II: The Random Oracle Methodology.- The Random Oracle Model.- The Full Power of Random Oracles.- Random Oracle Schemes in Practice.- Limitations of Random Oracles.- The Random Oracle Controversy.- Part III: Hash Function Constructions.- Iterated Hash Functions.- Constructing Compression Functions.- Iterated Hash Functions in Practice.- Constructions of Keyed Hash Functions.- Constructing Random Oracles: Indifferentiability.- Constructing Random Oracles: UCEs.- Index. <p