|
Contents I Fundamentals of Cryptography 1 1 Introduction to Cryptography 3 1.1 History of Cryptography . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Classical Cryptography . . . . . . . . . . . . . . . . . 4 1.1.2 Modern Cryptography . . . . . . . . . . . . . . . . . . 7 1.2 Background Review . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Big Oh Notation . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Polynomial . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Super Polynomial . . . . . . . . . . . . . . . . . . . . . 10 1.2.4 Negligible . . . . . . . . . . . . . . . . . . . . . . . . . 10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Structure of Security Proof 13 2.1 Overview of Security Proof . . . . . . . . . . . . . . . . . . . 14 2.1.1 Why Proving Security? . . . . . . . . . . . . . . . . . 14 2.1.2 Security Goals . . . . . . . . . . . . . . . . . . . . . . 14 2.1.3 Attack Models . . . . . . . . . . . . . . . . . . . . . . 16 2.1.4 How Can We Build a Cryptographic Scheme? Lego Approach! . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.5 Computational Assumptions . . . . . . . . . . . . . . 17 2.2 Proof by Reduction . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 What Is Reduction? . . . . . . . . . . . . . . . . . . . 19 2.2.2 Outline of Security Proof by Reduction . . . . . . . . 19 2.3 Random Oracle Methodology . . . . . . . . . . . . . . . . . . 20 2.3.1 Security Proof in the Random Oracle Model . . . . . . 21 2.4 Sequence of Games . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.1 Hybrid Argument . . . . . . . . . . . . . . . . . . . . 24 2.5 The Generic Group Model . . . . . . . . . . . . . . . . . . . 25 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 Private-Key Encryption (1) 27 3.1 Defining Computationally-Secure Encryption . . . . . . . . . 27 3.2 Pseudorandomness . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 A Private-Key Encryption Scheme Based on Pseudorandom Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 Private-Key Encryption (2) 35 4.1 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Stronger Security Notions . . . . . . . . . . . . . . . . . . . . 36 4.2.1 Security for Multiple Encryptions . . . . . . . . . . . . 36 4.2.2 Security for Chosen-Plaintext Attack . . . . . . . . . . 38 4.3 Constructing CPA-Secure Encryption Scheme . . . . . . . . 42 4.4 Advanced Encryption Standard . . . . . . . . . . . . . . . . 47 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5 Private-Key Encryption (3) 51 5.1 Block Ciphers and Modes of Operation . . . . . . . . . . . . 51 5.1.1 Electronic Code Book (ECB) Mode . . . . . . . . . . 52 5.1.2 Cipher Block Chaining (CBC) Mode . . . . . . . . . . 52 5.1.3 Counter (CTR) Mode . . . . . . . . . . . . . . . . . . 54 5.2 CPA-Securities of Modes of Operation . . . . . . . . . . . . . 55 5.2.1 IND-CPA Adversary . . . . . . . . . . . . . . . . . . . 55 5.2.2 A Block Cipher Per Se Is Not IND-CPA Secure . . . . 56 5.2.3 ECB Is Not IND-CPA Secure . . . . . . . . . . . . . . 56 5.2.4 CBC Is IND-CPA Secure . . . . . . . . . . . . . . . . 57 5.2.5 CTR Is IND-CPA Secure . . . . . . . . . . . . . . . . 57 5.3 Security Against Chosen-Ciphertext Attack (CCA) . . . . . 59 5.3.1 IND-CCA Adversary . . . . . . . . . . . . . . . . . . . 61 5.3.2 A CPA-Secure Encryption Scheme from Any Pseudorandom Function Is Not CCA-Secure . . . . . . . . . . 62 5.3.3 A CPA-Secure Encryption Scheme Using CBC Mode (Random Version) Is Not CCA-Secure . . . . . . . . . 62 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6 Message Authentication Code 65 6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.1.1 Encryption vs. Message Authentication . . . . . . . . 66 6.2 Message Authentication Code . . . . . . . . . . . . . . . . . 67 6.3 Constructing Secure Message Authentication Code . . . . . . 70 6.3.1 Fixed-Length MAC . . . . . . . . . . . . . . . . . . . . 70 6.3.2 Variable-Length MAC . . . . . . . . . . . . . . . . . . 72 6.4 CBC-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.5 Obtaining Encryption and Message Authentication . . . . . 77 6.5.1 Constructing CCA-Secure Encryption Schemes Using MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7 Hash Function 87 7.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.1.1 Collision Resistance . . . . . . . . . . . . . . . . . . . 88 7.1.2 Weaker Notions of Security . . . . . . . . . . . . . . . 89 7.2 Design of Collision-Resistant Hash Functions . . . . . . . . . 90 7.2.1 Compression Function Proved Secure Under the Discrete Log Assumption . . . . . . . . . . . . . . . . . . 90 7.2.2 Compression Functions Based on Secure Block Ciphers 93 7.2.3 Proprietary Compression Functions . . . . . . . . . . . 93 7.3 The Merkle-Damgard Transform . . . . . . . . . . . . . . . . 93 7.4 Generic Attacks on Hash Functions . . . . . . . . . . . . . . 95 7.4.1 Birthday Attacks for Finding Collisions . . . . . . . . 95 7.4.2 Small-Space Birthday Attacks . . . . . . . . . . . . . . 96 7.5 Message Authentication Using Hash Functions . . . . . . . . 97 7.5.1 Hash-and-MAC . . . . . . . . . . . . . . . . . . . . . . 97 7.5.2 HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.6 Applications of Hash Function . . . . . . . . . . . . . . . . . 99 7.6.1 Fingerprinting and Deduplication . . . . . . . . . . . . 99 7.6.2 Merkle Trees . . . . . . . . . . . . . . . . . . . . . . . 99 7.6.3 Password Hashing . . . . . . . . . . . . . . . . . . . . 101 7.6.4 Key Derivation . . . . . . . . . . . . . . . . . . . . . . 102 7.6.5 Commitment Schemes . . . . . . . . . . . . . . . . . . 102 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 8 Introduction to Number Theory 105 8.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.1.1 Division, Prime, and Modulo . . . . . . . . . . . . . . 106 8.1.2 Greatest Common Divisor . . . . . . . . . . . . . . . . 107 8.1.3 Euclidean Algorithm . . . . . . . . . . . . . . . . . . . 107 8.1.4 Extended Euclidean Algorithm . . . . . . . . . . . . . 107 8.1.5 Fermat’s Little Theorem . . . . . . . . . . . . . . . . . 107 8.1.6 Euler’s Theorem . . . . . . . . . . . . . . . . . . . . . 108 8.1.7 Exponentiation and Logarithm . . . . . . . . . . . . . 108 8.1.8 Set of Residues Zn . . . . . . . . . . . . . . . . . . . . 109 8.1.9 Inverse Modulo . . . . . . . . . . . . . . . . . . . . . . 110 8.1.10 Euler’s Criterion . . . . . . . . . . . . . . . . . . . . . 112 8.2 Algebraic Structure . . . . . . . . . . . . . . . . . . . . . . . 112 8.2.1 Group . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 8.2.2 Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8.2.3 Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8.2.4 GF(2n) . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.2.5 Elliptic Curve . . . . . . . . . . . . . . . . . . . . . . . 116 9 Public-Key Encryption 119 9.1 Discrete Logarithm and Its Related Assumptions . . . . . . . 120 9.2 The Diffie-Hellman Key Exchange Protocol . . . . . . . . . . 122 9.3 Overview of Public-Key Encryption . . . . . . . . . . . . . . 125 9.3.1 Security Against CPA . . . . . . . . . . . . . . . . . . 126 9.3.2 Security Against CCA . . . . . . . . . . . . . . . . . . 129 9.3.3 Hybrid Encryption and the KEM/DEM Paradigm . . 130 9.4 Public-Key Encryption Schemes . . . . . . . . . . . . . . . . 131 9.4.1 The El Gamal Encryption . . . . . . . . . . . . . . . . 131 9.4.2 The Plain (aka Textbook) RSA Encryption . . . . . . 135 9.4.2.1 RSA Cryptosystem Based on Elliptic Curve . 137 9.4.3 The Padded RSA Encryption . . . . . . . . . . . . . . 138 9.4.4 The CPA-Secure RSA Encryption Under the RSA Assumption in the Random Oracle Model . . . . . . . . 140 9.4.5 The CCA-Secure RSA Encryption Under the RSA Assumption in the Random Oracle Model . . . . . . . . 143 9.4.6 The RSA-OAEP Encryption . . . . . . . . . . . . . . 147 9.4.7 The Cramer-Shoup Encryption . . . . . . . . . . . . . 147 9.4.8 The Paillier Encryption . . . . . . . . . . . . . . . . . 159 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 10 Digital Signature 161 10.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 10.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 10.3 The El Gamal Signatures . . . . . . . . . . . . . . . . . . . . 164 10.4 The RSA Signatures . . . . . . . . . . . . . . . . . . . . . . . 170 10.4.1 Plain RSA . . . . . . . . . . . . . . . . . . . . . . . . . 171 10.4.2 Full Domain Hash RSA . . . . . . . . . . . . . . . . . 172 10.4.3 Probabilistic Signature Scheme (PSS) . . . . . . . . . 173 10.5 Blockchain: Application of Hash Function and Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 10.5.1 Blockchain 1.0: Early Development of Blockchain Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 10.5.1.1 The Use of Cryptography in Blockchain . . . 176 10.5.1.2 Other Consensus Algorithms . . . . . . . . . 177 10.5.2 Blockchain 2.0: Smart Contract Beyond Cryptocurrency 178 10.5.3 Private, Consortium, and Public Blockchain . . . . . . 178 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 II Identity-Based Encryption and Its Variants 181 11 Identity-Based Encryption (1) 183 11.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 11.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 11.2.1 Bilinear Map (Weil and Tate Pairing) . . . . . . . . . 184 11.2.2 Hardness Assumption . . . . . . . . . . . . . . . . . . 186 11.3 Identity-Based Encryption . . . . . . . . . . . . . . . . . . . 186 11.4 Boneh-Franklin IBE [24] . . . . . . . . . . . . . . . . . . . . 187 12 Identity-Based Encryption (2) 201 12.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 12.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.1 Security Model . . . . . . . . . . . . . . . . . . . . . . 203 12.2.2 Hardness Assumptions . . . . . . . . . . . . . . . . . . 204 12.2.3 How to Achieve a Tight Reduction? . . . . . . . . . . 206 12.3 Gentry’s IBE [48] . . . . . . . . . . . . . . . . . . . . . . . . 208 12.3.1 Construction 1: Chosen-Plaintext Security . . . . . . . 208 12.3.2 Security 1: Chosen-Plaintext Security . . . . . . . . . 210 12.3.3 Construction 2. Chosen-Ciphertext Security . . . . . . 216 12.3.4 Security 2: Chosen-Ciphertext Security . . . . . . . . . 218 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 13 Identity-Based Encryption (3) 231 13.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 13.2.1 Security Model . . . . . . . . . . . . . . . . . . . . . . 234 13.2.2 Hardness Assumptions . . . . . . . . . . . . . . . . . . 234 13.3 Dual System Encryption . . . . . . . . . . . . . . . . . . . . 235 13.4 Waters’ IBE [99] . . . . . . . . . . . . . . . . . . . . . . . . . 239 13.4.1 Proof of IBE Security . . . . . . . . . . . . . . . . . . 244 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 14 Hierarchical Identity-Based Encryption 263 14.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 14.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 14.2.1 General Construction of HIBE . . . . . . . . . . . . . 265 14.2.2 Security Model for HIBE . . . . . . . . . . . . . . . . 266 14.2.3 Composite Order Bilinear Groups . . . . . . . . . . . 267 14.2.4 Hardness Assumptions . . . . . . . . . . . . . . . . . . 268 14.2.5 A “Master Theorem” for Hardness in Composite Order Bilinear Groups [60] . . . . . . . . . . . . . . . . . . . 269 14.3 Waters’ Realization . . . . . . . . . . . . . . . . . . . . . . . 274 14.4 Waters’ HIBE with Composite Order . . . . . . . . . . . . . 275 14.4.1 Proof of HIBE Security . . . . . . . . . . . . . . . . . 281 14.5 The Generic Group Model . . . . . . . . . . . . . . . . . . . 292 14.5.1 The Decision Linear Diffie-Hellman Assumption . . . . 292 14.5.2 The Linear Problem in Generic Bilinear Groups . . . . 293 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 15 Identity-Based Encryption (4) 297 15.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 15.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 15.2.1 Security Model . . . . . . . . . . . . . . . . . . . . . . 299 15.2.2 Hardness Assumption . . . . . . . . . . . . . . . . . . 301 15.3 Boneh-Boyen IBE [19] . . . . . . . . . . . . . . . . . . . . . . 301 15.3.1 Proof of IBE Security . . . . . . . . . . . . . . . . . . 303 16 Tight Reduction 307 16.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 16.2 Why Is Tight Reduction Important? . . . . . . . . . . . . . . 308 16.3 Obstacles and Solutions in Tight Reduction . . . . . . . . . . 309 16.3.1 All-and-Any Strategy . . . . . . . . . . . . . . . . . . 309 16.3.1.1 Relationship Between Security Models and Strategies . . . . . . . . . . . . . . . . . . . . 310 16.3.2 Searching Method . . . . . . . . . . . . . . . . . . . . 311 16.3.3 Self-Decryption Paradox . . . . . . . . . . . . . . . . . 312 16.4 All-and-Any Strategy Techniques in the Random Oracle Model 312 16.4.1 Katz-Wang Technique . . . . . . . . . . . . . . . . . . 313 16.4.2 Park-Lee Technique . . . . . . . . . . . . . . . . . . . 314 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 17 Transformation Technique 317 17.1 Canetti-Halevi-Katz Transformation [32] . . . . . . . . . . . 317 17.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 318 17.1.1.1 Binary Tree Encryption . . . . . . . . . . . . 318 17.1.1.2 One-Time Signature . . . . . . . . . . . . . . 320 17.1.2 Chosen-Ciphertext Security from IBE . . . . . . . . . 321 17.1.3 Chosen-Ciphertext Security for BTE Schemes . . . . . 325 18 Broadcast Encryption 331 18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 18.2 Subset-Cover Revocation Framework [78] . . . . . . . . . . . 333 18.2.1 Problem Definition . . . . . . . . . . . . . . . . . . . . 333 18.2.2 The Framework . . . . . . . . . . . . . . . . . . . . . . 333 18.2.3 Two Subset-Cover Algorithms . . . . . . . . . . . . . . 335 18.2.3.1 Complete Subtree (CS) Method . . . . . . . 337 18.2.3.2 Subset Difference (SD) Method . . . . . . . . 340 18.3 Identity-Based Broadcast Encryption . . . . . . . . . . . . . 347 18.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 347 18.3.1.1 Definition . . . . . . . . . . . . . . . . . . . . 347 18.3.1.2 Security Model . . . . . . . . . . . . . . . . . 348 18.3.1.3 Hardness Assumptions . . . . . . . . . . . . 349 18.3.2 Delerablée’s Scheme [37] . . . . . . . . . . . . . . . . . 351 18.3.3 Security Analysis of Delerablée’s Scheme . . . . . . . . 352 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 19 Attribute-Based Encryption 359 19.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 19.2 Access Structure . . . . . . . . . . . . . . . . . . . . . . . . . 361 19.2.1 Secret Sharing Scheme . . . . . . . . . . . . . . . . . . 361 19.2.2 Access Trees . . . . . . . . . . . . . . . . . . . . . . . 361 19.2.3 Satisfying the Access Tree . . . . . . . . . . . . . . . . 362 19.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 19.3.1 The Generic Bilinear Group Model . . . . . . . . . . . 364 19.3.2 The Decisional Bilinear Diffie-Hellman (DBDH) Assumption . . . . . . . . . . . . . . . . . . . . . . . . . 365 19.3.3 Selective-Set Model for KP-ABE . . . . . . . . . . . . 365 19.3.4 Security Model for CP-ABE . . . . . . . . . . . . . . . 365 19.4 KP-ABE [55] . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 19.4.1 Security Analysis of KP-ABE . . . . . . . . . . . . . . 369 19.4.2 Probability Analysis . . . . . . . . . . . . . . . . . . . 372 19.5 CP-ABE [14] . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 20 Secret Sharing 383 20.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 20.2 Efficient Secret Sharing . . . . . . . . . . . . . . . . . . . . . 384 20.2.1 Shamir’s Secret Sharing [90] . . . . . . . . . . . . . . . 384 20.2.1.1 Mathematical Definition . . . . . . . . . . . . 385 20.2.1.2 The Construction . . . . . . . . . . . . . . . 385 20.2.1.3 Example . . . . . . . . . . . . . . . . . . . . 385 20.2.2 Blakley’s Secret Sharing [16] . . . . . . . . . . . . . . 387 20.2.2.1 The Construction . . . . . . . . . . . . . . . 387 20.2.2.2 Example . . . . . . . . . . . . . . . . . . . . 388 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 21 Predicate Encryption and Functional Encryption 391 21.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 21.1.1 Predicate Encryption . . . . . . . . . . . . . . . . . . 392 21.1.2 Functional Encryption . . . . . . . . . . . . . . . . . . 393 21.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 21.2.1 Hardness Assumptions . . . . . . . . . . . . . . . . . . 395 21.2.2 Definition of Predicate Encryption . . . . . . . . . . . 397 21.2.3 Definition of Functional Encryption . . . . . . . . . . 399 21.3 Predicate-Only Encryption [62] . . . . . . . . . . . . . . . . . 400 21.3.1 Proof of Predicate-Only Encryption Security . . . . . 402 21.4 Predicate Encryption [62] . . . . . . . . . . . . . . . . . . . . 410 21.4.1 Proof of Predicate Encryption Security . . . . . . . . . 412 21.5 Functional Encryption . . . . . . . . . . . . . . . . . . . . . . 417 21.5.1 Proof of Functional Encryption Security . . . . . . . . 419 21.5.2 Applications of Functional Encryption . . . . . . . . . 423 21.5.2.1 Distance Measurement . . . . . . . . . . . . 423 21.5.2.2 Exact Threshold . . . . . . . . . . . . . . . . 424 21.5.2.3 Weighted Average . . . . . . . . . . . . . . . 424 III Post-Quantum Cryptography 425 22 Introduction to Lattice 427 22.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 22.2 Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . 428 22.3 NTRU Cryptosystem . . . . . . . . . . . . . . . . . . . . . . 429 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 23 Lattice-Based Cryptography 433 23.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 23.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 23.2.1 Distributions . . . . . . . . . . . . . . . . . . . . . . . 435 23.3 Lattice-Based Cryptography . . . . . . . . . . . . . . . . . . 435 23.3.1 Learning with Errors (LWE) . . . . . . . . . . . . . . 436 23.3.2 Learning with Rounding (LWR) . . . . . . . . . . . . 438 23.3.3 Ring Variants of LWE and LWR . . . . . . . . . . . . 439 23.4 (LWE+LWR)-Based Public-Key Encryption [34] . . . . . . 439 23.4.1 The Construction . . . . . . . . . . . . . . . . . . . . . 440 23.4.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . 441 23.4.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . 441 23.5 Ring Variant of Lizard . . . . . . . . . . . . . . . . . . . . . 442 23.5.1 The Construction . . . . . . . . . . . . . . . . . . . . . 444 24 Introduction to Linear Codes 447 24.1 Fundamentals of Coding Theory . . . . . . . . . . . . . . . . 448 24.2 Basics of Linear Codes . . . . . . . . . . . . . . . . . . . . . 448 24.2.1 Generator Matrix and Parity-Check Matrix . . . . . . 449 24.3 Types of Decoding . . . . . . . . . . . . . . . . . . . . . . . . 453 24.3.1 Maximum-Likelihood Decoding . . . . . . . . . . . . . 453 24.3.2 Minimum-Distance Decoding . . . . . . . . . . . . . . 453 24.3.3 Syndrome Decoding . . . . . . . . . . . . . . . . . . . 454 24.4 Hamming Geometry and Code Performance . . . . . . . . . 454 24.5 Types of Codes . . . . . . . . . . . . . . . . . . . . . . . . . 455 24.5.1 Hamming Code . . . . . . . . . . . . . . . . . . . . . . 455 24.5.2 Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . 456 24.5.3 Generalized Reed-Solomon (GRS) Codes . . . . . . . . 457 24.5.4 Goppa Codes . . . . . . . . . . . . . . . . . . . . . . . 457 24.5.4.1 Construction of Goppa Codes . . . . . . . . 457 24.5.4.2 Binary Goppa Codes . . . . . . . . . . . . . 457 24.5.4.3 Parity-Check Matrix of Goppa Codes . . . . 458 24.6 Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 459 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 25 Code-Based Cryptography 463 25.1 McEliece Cryptosystem [75] . . . . . . . . . . . . . . . . . . 464 25.1.1 Key Generation . . . . . . . . . . . . . . . . . . . . . . 464 25.1.2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . 465 25.1.3 Decryption . . . . . . . . . . . . . . . . . . . . . . . . 465 25.2 Niederreiter Cryptosystem . . . . . . . . . . . . . . . . . . . 466 25.2.1 Key Generation . . . . . . . . . . . . . . . . . . . . . . 466 25.2.2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . 467 25.2.3 Decryption . . . . . . . . . . . . . . . . . . . . . . . . 468 25.3 Security Analysis of McEliece and Niederreiter . . . . . . . . 468 25.4 QC-MDPC McEliece Cryptosystem . . . . . . . . . . . . . . 469 25.4.1 MDPC and QC-MDPC Codes . . . . . . . . . . . . . 470 25.4.1.1 MDPC Code . . . . . . . . . . . . . . . . . . 470 25.4.1.2 MDPC Code Construction . . . . . . . . . . 470 25.4.1.3 QC-MDPC Code Construction . . . . . . . . 470 25.4.2 QC-MDPC McEliece Cryptosystem [101] . . . . . . . 471 25.4.2.1 Key Generation . . . . . . . . . . . . . . . . 471 25.4.2.2 Encryption . . . . . . . . . . . . . . . . . . . 471 25.4.2.3 Decryption . . . . . . . . . . . . . . . . . . . 472 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 IV Implementations of Selected Algorithms 475 26 Selected Algorithms 477 26.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 26.2 Boneh-Franklin IBE . . . . . . . . . . . . . . . . . . . . . . . 478 26.3 Boneh-Boyen IBE . . . . . . . . . . . . . . . . . . . . . . . . 478 26.4 Broadcast Encryption . . . . . . . . . . . . . . . . . . . . . . 478 26.5 Ciphertext-Policy Attribute-Based Encryption (CP-ABE) . . 479 26.6 Predicate Encryption (PE) . . . . . . . . . . . . . . . . . . . 479 26.7 Rivest-Shamir-Adleman (RSA) . . . . . . . . . . . . . . . . . 480 26.8 Elliptic Curve Digital Signature Algorithm (ECDSA) . . . . 480 26.9 QC-MDPC McEliece . . . . . . . . . . . . . . . . . . . . . . 480 26.10 NTRUEncrypt . . . . . . . . . . . . . . . . . . . . . . . . . 481 26.11 Number Theoretic Transform . . . . . . . . . . . . . . . . . 481 26.12 The Paillier Encryption . . . . . . . . . . . . . . . . . . . . 482 26.13 AES Block Cipher . . . . . . . . . . . . . . . . . . . . . . . 482 26.14 wolfSSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 Bibliography 485 |