Preface
Acknowledgements
Contents
Chapter 1 Guide to This Book
Chapter 2 Notions, Definitions, and Models
2.1 Digital Signatures
2.2 Public-Key Encryption
2.3 Identity-Based Encryption
2.4 Further Reading
Chapter 3 Foundations of Group-Based Cryptography
3.1 Finite Fields
3.1.1 Definition
3.1.2 Field Operations
3.1.3 Field Choices
3.1.4 Computations over a Prime Field
3.2 Cyclic Groups
3.2.1 Definitions
3.2.2 Cyclic Groups of Prime Order
3.2.3 Group Exponentiations
3.2.4 Discrete Logarithms
3.2.5 Cyclic Groups from Finite Fields
3.2.6 Group Choice 1: Multiplicative Groups
3.2.7 Group Choice 2: Elliptic Curve Groups
3.2.8 Computations over a Group
3.3 Bilinear Pairings
3.3.1 Symmetric Pairing
3.3.2 Asymmetric Pairing
3.3.3 Computations over a Pairing Group
3.4 Hash Functions
3.5 Further Reading
Chapter 4 Foundations of Security Reduction
4.1 Introduction to Basic Concepts
4.1.1 Mathematical Primitives and Superstructures
4.1.2 Mathematical Problems and Problem Instances
4.1.3 Cryptography, Cryptosystems, and Schemes
4.1.4 Algorithm Classification 1
4.1.5 Polynomial Time and Exponential Time
4.1.6 Negligible and Non-negligible
4.1.7 Insecure and Secure
4.1.8 Easy and Hard
4.1.9 Algorithm Classification 2
4.1.10 Algorithms in Cryptography
4.1.11 Hard Problems in Cryptography
4.1.12 Security Levels
4.1.13 Hard Problems and Hardness Assumptions
4.1.14 Security Reductions and Security Proofs
4.2 An Overview of Easy/Hard Problems
4.2.1 Computational Easy Problems
4.2.2 Computational Hard Problems
4.2.3 Decisional Easy Problems
4.2.4 Decisional Hard Problems
4.2.5 How to Prove New Hard Problems
4.2.6 Weak Assumptions and Strong Assumptions
4.3 An Overview of Security Reduction
4.3.1 Security Models
4.3.2 Weak Security Models and Strong Security Models
4.3.3 Proof by Testing
4.3.4 Proof by Contradiction
4.3.5 What Is Security Reduction?
4.3.6 Real Scheme and Simulated Scheme
4.3.7 Challenger and Simulator
4.3.8 Real Attack and Simulation
4.3.9 Attacks and Hard Problems
4.3.10 Reduction Cost and Reduction Loss
4.3.11 Loose Reduction and Tight Reduction
4.3.12 Security Level Revisited
4.3.13 Ideal Security Reduction
4.4 An Overview of Correct Security Reduction
4.4.1 What Should Bob Do?
4.4.2 Understanding Security Reduction
4.4.3 Successful Simulation and Indistinguishable Simulation
4.4.4 Failed Attack and Successful Attack
4.4.5 Useless Attack and Useful Attack
4.4.6 Attack in Simulation
4.4.7 Successful/Correct Security Reduction
4.4.8 Components of a Security Proof
4.5 An Overview of the Adversary
4.5.1 Black-Box Adversary
4.5.2 What Is an Adaptive Attack?
4.5.3 Malicious Adversary
4.5.4 The Adversary in a Toy Game
4.5.5 Adversary's Successful Attack and Its Probability
4.5.6 Adversary's Computational Ability
4.5.7 The Adversary's Computational Ability in a Reduction
4.5.8 The Adversary in a Reduction
4.5.9 What the Adversary Knows
4.5.10 What the Adversary Never Knows
4.5.11 How to Distinguish the Given Scheme
4.5.12 How to Generate a Useless Attack
4.5.13 Summary of Adversary
4.6 An Overview of Probability and Advantage
4.6.1 Definitions of Probability
4.6.2 Definitions of Advantage
4.6.3 Malicious Adversary Revisited
4.6.4 Adaptive Choice Revisited
4.6.5 Useless, Useful, Loose, and Tight Revisited
4.6.6 Important Probability Formulas
4.7 An Overview of Random and Independent
4.7.1 What Are Random and Independent?
4.7.2 Randomness Simulation with a General Function
4.7.3 Randomness Simulation with a Linear System
4.7.4 Randomness Simulation with a Polynomial
4.7.5 Indistinguishable Simulation and Useful Attack Together
4.7.6 Advantage and Probability in Absolutely Hard Problems
4.8 An Overview of Random Oracles
4.8.1 Security Proof with Random Oracles
4.8.2 Hash Functions vs Random Oracles
4.8.3 Hash List
4.8.4 How to Program Security Reductions with Random Oracles
4.8.5 Oracle Response and Its Probability Analysis
4.8.6 Summary of Using Random Oracles
4.9 Security Proofs for Digital Signatures
4.9.1 Proof Structure
4.9.2 Advantage Calculation
4.9.3 Simulatable and Reducible
4.9.4 Simulation of Secret Key
4.9.5 Partition
4.9.6 Tight Reduction and Loose Reduction Revisited
4.9.7 Summary of Correct Security Reduction
4.10 Security Proofs for Encryption Under Decisional Assumptions
4.10.1 Proof Structure
4.10.2 Classification of Ciphertexts
4.10.3 Classification of the Challenge Ciphertext
4.10.4 Simulation of the Challenge Ciphertext
4.10.5 Advantage Calculation 1
4.10.6 Probability PT of Breaking the True Challenge Ciphertext
4.10.7 Probability PF of Breaking the False Challenge Ciphertext
4.10.8 Advantage Calculation 2
4.10.9 Definition of One-Time Pad
4.10.10 Examples of One-Time Pad
4.10.11 Analysis of One-Time Pad
4.10.12 Simulation of Decryption
4.10.13 Simulation of Challenge Decryption Key
4.10.14 Probability Analysis for PF
4.10.15 Examples of Advantage Results for AFK and AFI
4.10.16 Advantage Calculation 3
4.10.17 Summary of Correct Security Reduction
4.11 Security Proofs for Encryption Under Computational Assumptions
4.11.1 Random and Independent Revisited
4.11.2 One-Time Pad Revisited
4.11.3 Solution to Hard Problem Revisited
4.11.4 Simulation of Challenge Ciphertext
4.11.5 Proof Structure
4.11.6 Challenge Ciphertext and Challenge Hash Query
4.11.7 Advantage Calculation
4.11.8 Analysis of No Advantage
4.11.9 Requirements of Decryption Simulation
4.11.10 An Example of Decryption Simulation
4.11.11 Summary of Correct Security Reduction
4.12 Simulatable and Reducible with Random Oracles
4.12.1 H-Type: Hashing to Group
4.12.2 C-Type: Commutative
4.12.3 I-Type: Inverse of Group Exponent
4.13 Examples of Incorrect Security Reductions
4.13.1 Example 1: Distinguishable
4.13.2 Example 2: Useless Attack by Public Key
4.13.3 Example 3: Useless Attack by Signature
4.14 Examples of Correct Security Reductions
4.14.1 One-Time Signature with Random Oracles
4.14.2 One-Time Signature Without Random Oracles
4.14.3 One-Time Signature with Indistinguishable Partition
4.15 Summary of Concepts
4.15.1 Concepts Related to Proof
4.15.2 Preliminaries and Proof by Contradiction
4.15.3 Security Reduction and Its Difficulty
4.15.4 Simulation and Its Requirements
4.15.5 Towards a Correct Security Reduction
4.15.6 Other Confusing Concepts
Chapter 5 Digital Signatures with Random Oracles
5.1 BLS Scheme
5.2 BLS+ Scheme
5.3 BLS# Scheme
5.4 BBRO Scheme
5.5 ZSS Scheme
5.6 ZSS+ Scheme
5.7 ZSS# Scheme
5.8 BLSG Scheme
Chapter 6 Digital Signatures Without Random Oracles
6.1 Boneh-Boyen Scheme
6.2 Gentry Scheme
6.3 GMS Scheme
6.4 Waters Scheme
6.5 Hohenberger-Waters Scheme
Chapter 7 Public-Key Encryption with Random Oracles
7.1 Hashed ElGamal Scheme
7.2 Twin Hashed ElGamal Scheme
7.3 Iterated Hashed ElGamal Scheme
7.4 Fujisaki-Okamoto Hashed ElGamal Scheme
Chapter 8 Public-Key Encryption Without Random Oracles
8.1 ElGamal Scheme
8.2 Cramer-Shoup Scheme
Chapter 9 Identity-Based Encryption with Random Oracles
9.1 Boneh-Franklin Scheme
9.2 Boneh-BoyenRO Scheme
9.3 Park-Lee Scheme
9.4 Sakai-Kasahara Scheme
Chapter 10 Identity-Based Encryption Without Random Oracles
10.1 Boneh-Boyen Scheme
10.2 Boneh-Boyen+ Scheme
10.3 Waters Scheme
10.4 Gentry Scheme
References