Modern Cryptography with Proof Techniques and Implementations

Proof techniques in cryptography are very difficult to understand, even for students or researchers who major in cryptography. In addition, in contrast to the excessive emphases on the security proofs of the cryptographic schemes, practical aspects of them have received comparatively less attention. This book addresses these two issues by providing detailed, structured proofs and demonstrating examples, applications and implementations of the schemes, so that students and practitioners may obtain a practical view of the schemes. Seong Oun Hwang is a professor in the Department of Computer Engineering and director of Artificial Intelligence Security Research Center, Gachon University, Korea. He received the Ph. D. degree in computer science from the Korea Advanced Institute of Science and Technology (KAIST), Korea. His research interests include cryptography, cybersecurity, networks, and machine learning. Intae Kim is an associate research fellow at the Institute of Cybersecurity and Cryptology, University of Wollongong, Australia. He received the Ph. D. degree in electronics and computer engineering from Hongik University, Korea. His research interests include cryptography, cybersecurity, and networks. Wai Kong Lee is an assistant professor in UTAR (University Tunku Abdul Rahman), Malaysia. He received the Ph. D. degree in engineering from UTAR, Malaysia. In between 2009 - 2012, he served as an R & D engineer in several multinational companies including Agilent Technologies (now known as Keysight) in Malaysia. His research interests include cryptography engineering, GPU computing, numerical algorithms, Internet of Things (IoT) and energy harvesting Cover Half Title Title Page Copyright Page Dedication Contents Preface List of Figures List of Tables I: Fundamentals of Cryptography 1. Introduction to Cryptography 1.1. History of Cryptography 1.1.1. Classical Cryptography 1.1.2. Modern Cryptography 1.2. Background Review 1.2.1. Big Oh Notation 1.2.2. Polynomial 1.2.3. Super Polynomial 1.2.4. Negligible Exercises 2. Structure of Security Proof 2.1. Overview of Security Proof 2.1.1. Why Proving Security? 2.1.2. Security Goals 2.1.3. Attack Models 2.1.4. How Can We Build a Cryptographic Scheme? Lego Approach! 2.1.5. Computational Assumptions 2.2. Proof by Reduction 2.2.1. What Is Reduction? 2.2.2. Outline of Security Proof by Reduction 2.3. Random Oracle Methodology 2.3.1. Security Proof in the Random Oracle Model 2.4. Sequence of Games 2.4.1. Hybrid Argument 2.5. The Generic Group Model Exercise 3. Private-Key Encryption (1) 3.1. Defining Computationally-Secure Encryption 3.2. Pseudorandomness 3.3. A Private-Key Encryption Scheme Based on Pseudorandom Generator Exercises 4. Private-Key Encryption (2) 4.1. Stream Ciphers 4.2. Stronger Security Notions 4.2.1. Security for Multiple Encryptions 4.2.2. Security for Chosen-Plaintext Attack 4.3. Constructing CPA-Secure Encryption Scheme 4.4. Advanced Encryption Standard Exercises 5. Private-Key Encryption (3) 5.1. Block Ciphers and Modes of Operation 5.1.1. Electronic Code Book (ECB) Mode 5.1.2. Cipher Block Chaining (CBC) Mode 5.1.3. Counter (CTR) Mode 5.2. CPA-Securities of Modes of Operation 5.2.1. IND-CPA Adversary 5.2.2. A Block Cipher Per Se Is Not IND-CPA Secure 5.2.3. ECB Is Not IND-CPA Secure 5.2.4. CBC Is IND-CPA Secure 5.2.5. CTR Is IND-CPA Secure 5.3. Security Against Chosen-Ciphertext Attack (CCA) 5.3.1. IND-CCA Adversary 5.3.2. A CPA-Secure Encryption Scheme from Any Pseudo-random Function Is Not CCA-Secure 5.3.3. A CPA-Secure Encryption Scheme Using CBC Mode (Random Version) Is Not CCA-Secure Exercises 6. Message Authentication Code 6.1. Overview 6.1.1. Encryption vs. Message Authentication 6.2. Message Authentication Code 6.3. Constructing Secure Message Authentication Code 6.3.1. Fixed-Length MAC 6.3.2. Variable-Length MAC 6.4. CBC-MAC 6.5. Obtaining Encryption and Message Authentication 6.5.1. Constructing CCA-Secure Encryption Schemes Using MAC 7. Hash Function 7.1. Definitions 7.1.1. Collision Resistance 7.1.2. Weaker Notions of Security 7.2. Design of Collision-Resistant Hash Functions 7.2.1. Compression Function Proved Secure Under the Discrete Log Assumption 7.2.2. Compression Functions Based on Secure Block Ciphers 7.2.3. Proprietary Compression Functions 7.3. The Merkle-Damgard Transform 7.4. Generic Attacks on Hash Functions 7.4.1. Birthday Attacks for Finding Collisions 7.4.2. Small-Space Birthday Attacks 7.5. Message Authentication Using Hash Functions 7.5.1. Hash-and-MAC 7.5.2. HMAC 7.6. Applications of Hash Function 7.6.1. Fingerprinting and Deduplication 7.6.2. Merkle Trees 7.6.3. Password Hashing 7.6.4. Key Derivation 7.6.5. Commitment Schemes Exercises 8. Introduction to Number Theory 8.1. Preliminaries 8.1.1. Division, Prime, and Modulo 8.1.2. Greatest Common Divisor 8.1.3. Euclidean Algorithm 8.1.4. Extended Euclidean Algorithm 8.1.5. Fermat's Little Theorem 8.1.6. Euler's Theorem 8.1.7. Exponentiation and Logarithm 8.1.8. Set of Residues Zn 8.1.9. Inverse Modulo 8.1.10. Euler's Criterion 8.2. Algebraic Structure 8.2.1. Group 8.2.2. Ring 8.2.3. Field 8.2.4. GF(2n) 8.2.5. Elliptic Curve 9. Public-Key Encryption 9.1. Discrete Logarithm and Its Related Assumptions 9.2. The Diffie-Hellman Key Exchange Protocol 9.3. Overview of Public-Key Encryption 9.3.1. Security Against CPA 9.3.2. Security Against CCA 9.3.3. Hybrid Encryption and the KEM/DEM Paradigm 9.4. Public-Key Encryption Schemes 9.4.1. The El Gamal Encryption 9.4.2. The Plain (aka Textbook) RSA Encryption 9.4.3. The Padded RSA Encryption 9.4.4. The CPA-Secure RSA Encryption Under the RSA Assumption in the Random Oracle Model 9.4.5. The CCA-Secure RSA Encryption Under the RSA Assumption in the Random Oracle Model 9.4.6. The RSA-OAEP Encryption 9.4.7. The Cramer-Shoup Encryption 9.4.8. The Paillier Encryption Exercises 10. Digital Signature 10.1. Overview 10.2. Definitions 10.3. The El Gamal Signatures 10.4. The RSA Signatures 10.4.1. Plain RSA 10.4.2. Full Domain Hash RSA 10.4.3. Probabilistic Signature Scheme (PSS) 10.5. Blockchain: Application of Hash Function and Public-Key Encryption 10.5.1. Blockchain 1.0: Early Development of Blockchain Technology 10.5.1.1. The Use of Cryptography in Blockchain 10.5.1.2. Other Consensus Algorithms 10.5.2. Blockchain 2.0: Smart Contract Beyond Cryptocurrency 10.5.3. Private, Consortium, and Public Blockchain Exercises II: Identity-Based Encryption and Its Variants 11. Identity-Based Encryption (1) 11.1. Overview 11.2. Preliminaries 11.2.1. Bilinear Map (Weil and Tate Pairing) 11.2.2. Hardness Assumption 11.3. Identity-Based Encryption 11.4. Boneh-Franklin IBE [24] 12. Identity-Based Encryption (2) 12.1. Overview 12.2. Preliminaries 12.2.1. Security Model 12.2.2. Hardness Assumptions 12.2.3. How to Achieve a Tight Reduction? 12.3. Gentry's IBE [48] 12.3.1. Construction 1: Chosen-Plaintext Security 12.3.2. Security 1: Chosen-Plaintext Security 12.3.3. Construction 2. Chosen-Ciphertext Security 12.3.4. Security 2: Chosen-Ciphertext Security Exercises 13. Identity-Based Encryption (3) 13.1. Overview 13.2. Preliminaries 13.2.1. Security Model 13.2.2. Hardness Assumptions 13.3. Dual System Encryption 13.4. Waters' IBE [99] 13.4.1. Proof of IBE Security Exercises 14. Hierarchical Identity-Based Encryption 14.1. Overview 14.2. Preliminaries 14.2.1. General Construction of HIBE 14.2.2. Security Model for HIBE 14.2.3. Composite Order Bilinear Groups 14.2.4. Hardness Assumptions 14.2.5. A "Master Theorem" for Hardness in Composite Order Bilinear Groups [60] 14.3. Waters' Realization 14.4. Waters' HIBE with Composite Order 14.4.1. Proof of HIBE Security 14.5. The Generic Group Model 14.5.1. The Decision Linear Diffie-Hellman Assumption 14.5.2. The Linear Problem in Generic Bilinear Groups Exercises 15. Identity-Based Encryption (4) 15.1. Overview 15.2. Preliminaries 15.2.1. Security Model 15.2.2. Hardness Assumption 15.3. Boneh-Boyen IBE [19] 15.3.1. Proof of IBE Security 16. Tight Reduction 16.1. Overview 16.2 .Why Is Tight Reduction Important? 16.3. Obstacles and Solutions in Tight Reduction 16.3.1. All-and-Any Strategy 16.3.2. Searching Method 16.3.3. Self-Decryption Paradox 16.4. All-and-Any Strategy Techniques in the Random Oracle Model 16.4.1. Katz-Wang Technique 16.4.2. Park-Lee Technique Exercises 17. Transformation Technique 17.1. Canetti-Halevi-Katz Transformation [32] 17.1.1. Definitions 17.1.1.1. Binary Tree Encryption 17.1.1.2. One-Time Signature 17.1.2. Chosen-Ciphertext Security from IBE 17.1.3. Chosen-Ciphertext Security for BTE Schemes 18. Broadcast Encryption 18.1. Introduction 18.2. Subset-Cover Revocation Framework [78] 18.2.1. Problem Definition 18.2.2. The Framework 18.2.3. Two Subset-Cover Algorithms 18.2.3.1. Complete Subtree (CS) Method 18.2.3.2. Subset Difference (SD) Method 18.3. Identity-Based Broadcast Encryption 18.3.1. Preliminaries 18.3.1.1. Definition 18.3.1.2. Security Model 18.3.1.3. Hardness Assumptions 18.3.2. Delerablee's Scheme [37] 18.3.3. Security Analysis of Delerablee's Scheme Exercises 19. Attribute-Based Encryption 19.1. Overview 19.2. Access Structure 19.2.1. Secret Sharing Scheme 19.2.2. Access Trees 19.2.3. Satisfying the Access Tree 19.3. Preliminaries 19.3.1. The Generic Bilinear Group Model 19.3.2. The Decisional Bilinear Diffie-Hellman (DBDH) Assumption 19.3.3. Selective-Set Model for KP-ABE 19.3.4. Security Model for CP-ABE 19.4. KP-ABE [55] 19.4.1. Security Analysis of KP-ABE 19.4.2. Probability Analysis 9.4.2.1. RSA Cryptosystem Based on Elliptic Curve 19.5. CP-ABE [14] 20. Secret Sharing 20.1. Overview 20.2. Efficient Secret Sharing 20.2.1. Shamir's Secret Sharing [90] 20.2.1.1. Mathematical Definition 20.2.1.2. The Construction 20.2.1.3. Example 20.2.2. Blakley's Secret Sharing [16] 20.2.2.1. The Construction 20.2.2.2. Example Exercise 21. Predicate Encryption and Functional Encryption 21.1. Overview 21.1.1 Predicate Encryption 21.1.2 Functional Encryption 21.2. Preliminaries 21.2.1 Hardness Assumptions 21.2.2 De nition of Predicate Encryption 21.2.3 De nition of Functional Encryption 21.3. Predicate-Only Encryption [62] 21.3.1 Proof of Predicate-Only Encryption Security 21.4. Predicate Encryption [62] 21.4.1 Proof of Predicate Encryption Security 21.5. Functional Encryption 21.5.1. Proof of Functional Encryption Security 21.5.2. Applications of Functional Encryption 21.5.2.1. Distance Measurement 21.5.2.2. Exact Threshold 21.5.2.3. Weighted Average III: Post-Quantum Cryptography 22. Introduction to Lattice 22.1. Preliminaries 22.2. Lattice Problems 22.3. NTRU Cryptosystem Exercises 23. Lattice-Based Cryptography 23.1. Overview 23.2. Preliminaries 23.2.1. Distributions 23.3. Lattice-Based Cryptography 23.3.1. Learning with Errors (LWE) 23.3.2. Learning with Rounding (LWR) 23.3.3. Ring Variants of LWE and LWR 23.4. (LWE+LWR)-Based Public-Key Encryption [34] 23.4.1. The Construction 23.4.2. Correctness 23.4.3. Security 23.5. Ring Variant of Lizard 23.5.1. The Construction 24. Introduction to Linear Codes 24.1. Fundamentals of Coding Theory 24.2. Basics of Linear Codes 24.2.1. Generator Matrix and Parity-Check Matrix 24.3. Types of Decoding 24.3.1. Maximum-Likelihood Decoding 24.3.2. Minimum-Distance Decoding 24.3.3. Syndrome Decoding 24.4. Hamming Geometry and Code Performance 24.5. Types of Codes 24.5.1. Hamming Code 24.5.2. Cyclic Codes 24.5.3. Generalized Reed-Solomon (GRS) Codes 24.5.4. Goppa Codes 24.5.4.1. Construction of Goppa Codes 24.5.4.2. Binary Goppa Codes 24.5.4.3. Parity-Check Matrix of Goppa Codes 24.6. Hard Problems Exercises 25. Code-Based Cryptography 25.1. McEliece Cryptosystem [75] 25.1.1. Key Generation 25.1.2. Encryption 25.1.3. Decryption 25.2. Niederreiter Cryptosystem 25.2.1. Key Generation 25.2.2. Encryption 25.2.3. Decryption 25.3. Security Analysis of McEliece and Niederreiter 25.4. QC-MDPC McEliece Cryptosystem 25.4.1. MDPC and QC-MDPC Codes 25.4.1.1. MDPC Code 25.4.1.2. MDPC Code Construction 25.4.1.3. QC-MDPC Code Construction 25.4.2. QC-MDPC McEliece Cryptosystem [101] 25.4.2.1. Key Generation 25.4.2.2. Encryption 25.4.2.3. Decryption Exercises IV: Implementations of Selected Algorithms 26. Selected Algorithms 26.1. Introduction 26.2. Boneh-Franklin IBE 26.3. Boneh-Boyen IBE 26.4. Broadcast Encryption 26.5. Ciphertext-Policy Attribute-Based Encryption (CP-ABE) 26.6. Predicate Encryption (PE) 26.7. Rivest-Shamir-Adleman (RSA) 26.8. Elliptic Curve Digital Signature Algorithm (ECDSA) 26.9. QC-MDPC McEliece 26.10. NTRUEncrypt 26.11. Number Theoretic Transform 26.12. The Paillier Encryption 26.13. AES Block Cipher 26.14. wolfSSL Bibliography Index This book is for cybersecurity leaders across all industries and organizations. It is intended to bridge the gap between the data center and the board room. It provides just enough practical skills and techniques for security leaders to get the job done.