Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010169230 | QA76.9.A25 M377 2008 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Identity-based encryption (IBE) is a new technology that allows the identity of users to be used as cryptographic keys instead of the long, random strings of bits that earlier technologies required. This allows for the creation of cryptographic systems that are as secure as traditional systems, but are much simpler and easier to use. Until now, details on IBE have only been found in cumbersome, hard-to-follow journal articles and conference proceedings. This is the first book to offer complete, accessible guidance on the subject. It provides professionals and students with an in-depth understanding of IBE, and offers practitioners a wealth of practical techniques, algorithms and numerous worked examples to help them effectively implement this technology in the field.
Author Notes
Luther Martin is a security architect at Voltage Security, Palo Alto, California.
Table of Contents
Preface | p. xiii |
1 Introduction | p. 1 |
1.1 What Is IBE? | p. 1 |
1.2 Why Should I Care About IBE? | p. 8 |
References | p. 13 |
2 Basic Mathematical Concepts and Properties | p. 15 |
2.1 Concepts from Number Theory | p. 15 |
2.1.1 Computing the GCD | p. 16 |
2.1.2 Computing Jacobi Symbols | p. 24 |
2.2 Concepts from Abstract Algebra | p. 25 |
References | p. 39 |
3 Properties of Elliptic Curves | p. 41 |
3.1 Elliptic Curves | p. 41 |
3.2 Adding Points on Elliptic Curves | p. 47 |
3.2.1 Algorithm for Elliptic Curve Point Addition | p. 52 |
3.2.2 Projective Coordinates | p. 53 |
3.2.3 Adding Points in Jacobian Projective Coordinates | p. 54 |
3.2.4 Doubling a Point in Jacobian Projective Coordinates | p. 55 |
3.3 Algebraic Structure of Elliptic Curves | p. 55 |
3.3.1 Higher Degree Twists | p. 61 |
3.3.2 Complex Multiplication | p. 65 |
References | p. 66 |
4 Divisors and the Tate Pairing | p. 67 |
4.1 Divisors | p. 67 |
4.1.1 An Intuitive Introduction to Divisors | p. 68 |
4.2 The Tate Pairing | p. 76 |
4.2.1 Properties of the Tate Pairing | p. 81 |
4.3 Miller's Algorithm | p. 84 |
References | p. 87 |
5 Cryptography and Computational Complexity | p. 89 |
5.1 Cryptography | p. 91 |
5.1.1 Definitions | p. 91 |
5.1.2 Protection Provided by Encryption | p. 93 |
5.1.3 The Fujisaki-Okamoto Transform | p. 95 |
5.2 Running Times of Useful Algorithms | p. 95 |
5.2.1 Finding Collisions for a Hash Function | p. 96 |
5.2.2 Pollard's Rho Algorithm | p. 98 |
5.2.3 The General Number Field Sieve | p. 99 |
5.2.4 The Index Calculus Algorithm | p. 102 |
5.2.5 Relative Strength of Algorithms | p. 102 |
5.3 Useful Computational Problems | p. 104 |
5.3.1 The Computational Diffie-Hellman Problem | p. 105 |
5.3.2 The Decision Diffie-Hellman Problem | p. 106 |
5.3.3 The Bilinear Diffie-Hellman Problem | p. 107 |
5.3.4 The Decision Bilinear Diffie-Hellman Problem | p. 107 |
5.3.5 q-Bilinear Diffie-Hellman Inversion | p. 108 |
5.3.6 q-Decision Bilinear Diffie-Hellman Inversion | p. 109 |
5.3.7 Cobilinear Diffie-Hellman Problems | p. 109 |
5.3.8 Integer Factorization | p. 109 |
5.3.9 Quadratic Residuosity | p. 109 |
5.4 Selecting Parameter Sizes | p. 110 |
5.4.1 Security Based on Integer Factorization and Quadratic Residuosity | p. 110 |
5.4.2 Security Based on Discrete Logarithms | p. 110 |
5.5 Important Special Cases | p. 111 |
5.5.1 Anomalous Curves | p. 112 |
5.5.2 Supersingular Elliptic Curves | p. 112 |
5.5.3 Singular Elliptic Curves | p. 113 |
5.5.4 Weak Primes | p. 113 |
5.6 Proving Security of Public-Key Algorithms | p. 114 |
5.7 Quantum Computing | p. 116 |
5.7.1 Grover's Algorithm | p. 116 |
5.7.2 Shor's Algorithm | p. 117 |
References | p. 118 |
6 Related Cryptographic Algorithms | p. 121 |
6.1 Goldwasser-Michali Encryption | p. 121 |
6.2 The Diffie-Hellman Key Exchange | p. 124 |
6.3 Elliptic Curve Diffie-Hellman | p. 125 |
6.4 Joux's Three-Way Key Exchange | p. 126 |
6.5 ElGamal Encryption | p. 128 |
References | p. 129 |
7 The Cocks IBE Scheme | p. 131 |
7.1 Setup of Parameters | p. 131 |
7.2 Extraction of the Private Key | p. 133 |
7.3 Encrypting with Cocks IBE | p. 133 |
7.4 Decrypting with Cocks IBE | p. 135 |
7.5 Examples | p. 136 |
7.6 Security of the Cocks IBE Scheme | p. 139 |
7.6.1 Relationship to the Quadratic Residuosity Problem | p. 139 |
7.6.2 Chosen Ciphertext Security | p. 142 |
7.6.3 Proof of Security | p. 142 |
7.6.4 Selecting Parameter Sizes | p. 143 |
7.7 Summary | p. 143 |
References | p. 145 |
8 Boneh-Franklin IBE | p. 147 |
8.1 Boneh-Franklin IBE (Basic Scheme) | p. 149 |
8.1.1 Setup of Parameters (Basic Scheme) | p. 149 |
8.1.2 Extraction of the Private Key (Basic Scheme) | p. 150 |
8.1.3 Encrypting with Boneh-Franklin IBE (Basic Scheme) | p. 150 |
8.1.4 Decrypting with Boneh-Franklin IBE (Basic Scheme) | p. 151 |
8.1.5 Examples (Basic Scheme) | p. 151 |
8.2 Boneh-Franklin IBE (Full Scheme) | p. 156 |
8.2.1 Setup of Parameters (Full Scheme) | p. 156 |
8.2.2 Extraction of the Private Key (Full Scheme) | p. 157 |
8.2.3 Encrypting with Boneh-Franklin IBE (Full Scheme) | p. 157 |
8.2.4 Decrypting with Boneh-Franklin IBE (Full Scheme) | p. 158 |
8.3 Security of the Boneh-Franklin IBE Scheme | p. 158 |
8.4 Summary | p. 159 |
Reference | p. 160 |
9 Boneh-Boyen IBE | p. 161 |
9.1 Boneh-Boyen IBE (Basic Scheme-Additive Notation) | p. 162 |
9.1.1 Setup of Parameters (Basic Scheme-Additive Notation) | p. 162 |
9.1.2 Extraction of the Private Key (Basic Scheme-Additive Notation) | p. 164 |
9.1.3 Encrypting with Boneh-Boyen IBE (Basic Scheme-Additive Notation) | p. 164 |
9.1.4 Decrypting with Boneh-Boyen IBE (Basic Scheme-Additive Notation) | p. 164 |
9.2 Boneh-Boyen IBE (Basic Scheme-Multiplicative Notation) | p. 168 |
9.2.1 Setup of Parameters (Basic Scheme-Multiplicative Notation) | p. 168 |
9.2.2 Extraction of the Private Key (Basic Scheme-Multiplicative Notation) | p. 170 |
9.2.3 Encrypting with Boneh-Boyen IBE (Basic Scheme-Multiplicative Notation) | p. 170 |
9.2.4 Decrypting with Boneh-Boyen IBE (Basic Scheme-Multiplicative Notation) | p. 170 |
9.3 Boneh-Boyen IBE (Full Scheme) | p. 171 |
9.3.1 Setup of Parameters (Full Scheme) | p. 172 |
9.3.2 Extraction of the Private Key (Full Scheme) | p. 173 |
9.3.3 Encrypting with Boneh-Boyen IBE (Full Scheme) | p. 173 |
9.3.4 Decrypting with Boneh-Boyen IBE (Full Scheme) | p. 173 |
9.4 Security of the Boneh-Boyen IBE Scheme | p. 174 |
9.5 Summary | p. 175 |
Reference | p. 176 |
10 Sakai-Kasahara IBE | p. 177 |
10.1 Sakai-Kasahara IBE (Basic Scheme-Additive Notation) | p. 177 |
10.1.1 Setup of Parameters (Basic Scheme-Additive Notation) | p. 178 |
10.1.2 Extraction of the Private Key (Basic Scheme-Additive Notation) | p. 178 |
10.1.3 Encrypting with Sakai-Kasahara IBE (Basic Scheme-Additive Notation) | p. 180 |
10.1.4 Decrypting with Sakai-Kasahara IBE (Basic Scheme-Additive Notation) | p. 180 |
10.2 Sakai-Kasahara IBE (Basic Scheme-Multiplicative Notation) | p. 182 |
10.2.1 Setup of Parameters (Basic Scheme-Multiplicative Notation) | p. 182 |
10.2.2 Extraction of the Private Key (Basic Scheme-Multiplicative Notation) | p. 183 |
10.2.3 Encrypting with Sakai-Kasahara IBE (Basic Scheme-Multiplicative Notation) | p. 184 |
10.2.4 Decrypting with Sakai-Kasahara IBE (Basic Scheme-Multiplicative Notation) | p. 184 |
10.3 Sakai-Kasahara IBE (Full Scheme) | p. 185 |
10.3.1 Setup of Parameters (Full Scheme) | p. 185 |
10.3.2 Extraction of the Private Key (Full Scheme) | p. 185 |
10.3.3 Encrypting with Sakai-Kasahara IBE (Full Scheme) | p. 185 |
10.3.4 Decrypting with Sakai-Kasahara IBE (Full Scheme) | p. 187 |
10.4 Security of the Sakai-Kasahara IBE Scheme | p. 187 |
10.5 Summary | p. 188 |
Reference | p. 189 |
11 Hierarchial IBE and Master Secret Sharing | p. 191 |
11.1 HIBE Based on Boneh-Franklin IBE | p. 193 |
11.1.1 GS HIBE (Basic) Root Setup | p. 194 |
11.1.2 GS HIBE (Basic) Lower-Level Setup | p. 194 |
11.1.3 GS HIBE (Basic) Extract | p. 194 |
11.1.4 GS HIBE (Basic) Encrypt | p. 194 |
11.1.5 GS HIBE (Basic) Decrypt | p. 195 |
11.2 Example of a GS HIBE System | p. 195 |
11.2.1 GS HIBE (Basic) Root Setup | p. 196 |
11.2.2 GS HIBE (Basic) Lower-Level Setup | p. 196 |
11.2.3 GS HIBE (Basic) Extraction of Private Key | p. 196 |
11.2.4 GS HIBE (Basic) Encryption | p. 197 |
11.2.5 GS HIBE (Basic) Decryption | p. 197 |
11.3 HIBE Based on Boneh-Boyen IBE | p. 197 |
11.3.1 BBG HIBE (Basic) Setup | p. 198 |
11.3.2 BBG HIBE (Basic) Extract | p. 199 |
11.3.3 BBG HIBE (Basic) Encryption | p. 199 |
11.3.4 BBG HIBE (Basic) Decryption | p. 199 |
11.4 Example of a BBG HIBE System | p. 200 |
11.4.1 BBG HIBE (Basic) Setup | p. 200 |
11.4.2 BBG HIBE (Basic) Extraction of Private Key | p. 200 |
11.4.3 BBG HIBE (Basic) Encryption | p. 201 |
11.4.4 BBG HIBE (Basic) Decryption | p. 201 |
11.5 Master Secret Sharing | p. 201 |
11.6 Master Secret Sharing Example | p. 202 |
References | p. 204 |
12 Calculating Pairings | p. 207 |
12.1 Pairing-Friendly Curves | p. 207 |
12.1.1 Relative Efficiency of Parameters of Pairing-Friendly Curves | p. 209 |
12.2 Eliminating Irrelevant Factors | p. 210 |
12.2.1 Eliminating Random Components | p. 211 |
12.2.2 Eliminating Extension Field Divisions | p. 214 |
12.2.3 Denominator Elimination | p. 215 |
12.3 Calculating the Product of Pairings | p. 216 |
12.4 The Shipsey-Stange Algorithm | p. 217 |
12.5 Precomputation | p. 221 |
References | p. 222 |
Appendix Useful Test Data | p. 225 |
About the Author | p. 229 |
Index | p. 231 |