Progress in Cryptology - AFRICACRYPT 2010: Third International Conference on Cryptology in Africa, Stellenbosch, South Africa, May 3-6, 2010, Proceedings ... Computer Science Security and Cryptology)

00 front-matter......Page 1
Introduction......Page 11
Strong Existential Unforgeability......Page 13
A New RSA-Based Signature Scheme......Page 14
Strong Existential Unforgeability of \mathcal{S}......Page 15
Signing Message Blocks......Page 21
Protocol for Signing Committed Messages......Page 22
Conclusion......Page 23
The Hohenberger-Waters Signature Scheme......Page 25
Prior Work......Page 26
Our Contribution......Page 27
Syntax......Page 28
Security Definitions......Page 29
A Note on the Hufschmitt-Traoré Security Notions......Page 30
A Signature Scheme to Sign Group Elements......Page 33
Commit and Encrypt......Page 34
A Scheme to Sign Three Diffie-Hellman Pairs......Page 35
A Fair Blind Signature Scheme......Page 37
A Blind Signature Scheme......Page 38
Security Proofs......Page 39
Conclusion......Page 42
Introduction......Page 44
Fair Partially Blind Signatures......Page 46
Definition......Page 47
Security of Fair Partially Blind Signatures......Page 48
A Warm-Up — Fischlin's Blind Signature Scheme......Page 51
An Instantiation from General Assumptions......Page 52
Construction......Page 53
Introduction......Page 62
Preliminaries......Page 64
Lattice Basis Reduction......Page 65
Programming Graphics Cards......Page 67
Original ENUM Algorithm......Page 68
Multi-thread Enumeration......Page 69
The Iterated Parallel ENUM Algorithm......Page 70
Experimental Results......Page 72
Further Work......Page 74
Introduction......Page 79
Notation......Page 80
A More Flexible Partial Enlargement......Page 81
The MGB Algorithm......Page 82
The Algorithm in Action......Page 85
Complexity Analysis......Page 86
Experimental Results......Page 87
Conclusions and Future Work......Page 90
Introduction......Page 92
The LSB Case: Combinatorial Analysis of [5]......Page 93
The Reconstruction Algorithm......Page 94
Growth of the Search Tree......Page 95
Known Prime Bits: Complementary Sets for p, q......Page 97
Known Prime Bits: Distributed at Random......Page 98
The LSB Case: Lattice Based Technique......Page 100
The Reconstruction Idea......Page 103
Analysis of the Reconstruction Algorithm......Page 104
Conclusion......Page 108
Introduction......Page 110
Informal Description of Our Technique......Page 112
Notation and Tools......Page 113
Proof of Knowledge of Permutation Matrix......Page 115
Proof of Proposition 1......Page 117
Proof of Knowledge of Restricted Permutation Matrix......Page 118
Encoding Graphs as Polynomials......Page 119
Proofs of Restricted Shuffles......Page 120
Variations and Generalizations......Page 121
Introduction......Page 124
Range Proof and the Most Recent Development in [5]......Page 126
Batch Proof and Verification......Page 127
Extended Batch Proof and Verification......Page 128
The New Range Proof Protocol......Page 131
Comparison of Efficiency and Security......Page 134
Conclusion......Page 136
Proof of Theorem 1 and Theorem 2......Page 137
Introduction......Page 141
Technical Preliminaries......Page 143
Definition......Page 145
Intuition Behind Our Construction......Page 146
Description of the Scheme......Page 147
Definition......Page 149
Intuition Behind Our Construction......Page 151
Description of the Scheme......Page 152
Conclusion......Page 155
Background......Page 158
Our Contribution......Page 160
The Model......Page 161
Security Notions and Their Formalization......Page 163
Lower Bounds......Page 166
Direct Construction......Page 167
Generic Construction......Page 168
Concluding Remarks......Page 170
Introduction......Page 176
Security Definition......Page 178
Polynomial 1-Phase Almost Secure Message Transmission......Page 180
Main Protocol Techniques......Page 181
Security and Efficiency......Page 182
Comparison of Protocol to Previous Work......Page 184
Main Protocol Techniques......Page 186
Formal Protocol Description......Page 188
Security and Efficiency......Page 189
2-Phase PSMT with O($n^2$) Transmission Rate......Page 190
Conclusion......Page 191
Generalized Broadcast......Page 192
Communication Efficient Perfectly Secure VSS and MPC in Asynchronous Networks with Optimal Resilience......Page 194
Introduction......Page 195
Definitions......Page 196
Our Contributions and Comparison with Existing Results......Page 197
Finding ($n,t$)-star Structure in a Graph......Page 199
Distribution Phase......Page 200
Verification and Agreement on CORE Phase......Page 201
Generation of $d$-Sharing Phase......Page 204
Protocol AVSS-Share-SS and AVSS-Rec-SS......Page 205
AVSS for Generating $d$-Sharing of Multiple Secrets......Page 206
Protocol for Generating ($t,2t$)-Sharing......Page 208
AMPC Protocol Overview......Page 209
Computation Phase......Page 210
Final AMPC Protocol......Page 211
Introduction......Page 213
Background......Page 216
$2^n$-ary Pairings: Miller $2^n$-tuple-and-add......Page 217
A Strategy for Obtaining Explicit Formulas......Page 220
Miller Quadruple-and-add......Page 222
Miller Octuple-and-add......Page 223
Comparisons......Page 226
Quadrupling Formulas for $y^2=x^3+b$......Page 230
Octupling Formulas for $y^2=x^3+b$......Page 231
Octupling Formulas for $y^2=x^3+ax$......Page 232
Explicit Formulas......Page 233
Introduction......Page 235
A Brief Description of the Cell Processor......Page 236
LS – Accessing Local Storage......Page 237
Preliminaries......Page 238
ECC2K-130 and Our Choice of the Iteration Function......Page 239
Computing the Iteration Function......Page 240
Bitsliced or Not Bitsliced?......Page 241
Polynomial or Normal Basis?......Page 242
The Non-bitsliced Implementation......Page 243
Multiplication......Page 244
Basis Conversion and m-Squaring......Page 245
The Bitsliced Implementation......Page 246
Multiplication......Page 247
$m$-Squaring......Page 248
Control Flow Overhead......Page 249
Conclusions......Page 250
Introduction......Page 253
Prerequisites......Page 254
How to Quantify the Information Amount?......Page 255
Profiled Side-Channel Attacks in Practice......Page 256
Success Rate......Page 261
Conditional Entropy......Page 262
Improvement of the Attacks Thanks to Leakage Profiles Noise Removal by Thresholding......Page 264
Success Rate......Page 265
Discussion......Page 266
Conclusions and Perspectives......Page 268
Introduction......Page 271
HC-128 Specifications and Definitions......Page 272
The Attack Overview......Page 273
The Faulty Value Position and Difference......Page 274
Recovering the Differences between Faulty and Non-faulty Words......Page 276
Recovering the Position of the Fault......Page 278
The Recovery of h Input Values for Steps 512,…1023......Page 279
The Recovery of the h Input Values for Steps 1024,…1535......Page 281
Equations of the Form $P^{b}_1[A_i]\oplus P^{b}_1[B_i]\oplus Q^{b}_1[j]=s^{b}_i\oplus c_{i,b}$......Page 282
Recovering Bits $P_1^b[0],\ldots P_1^b[255]$ and $Q_1^b[0],\ldots Q_1^b[255]$......Page 283
Utilizing Equations in Faulty Bits......Page 284
Conclusion......Page 287
Introduction......Page 289
Related Work......Page 291
Challenge-Response Protocol......Page 293
Desired Properties......Page 294
Unprotected Implementation......Page 295
Improving g's SPA/DPA Resistance with Blinding......Page 296
Improving g's SPA/DPA Resistance with Protected Logic-Styles......Page 297
Block Diagram and Design Space for the Function g......Page 298
Implementation Results and Performance Evaluation......Page 299
Resistance against Fault Attacks......Page 300
Resistance against Standard Side-Channel Attacks......Page 301
Resistance against Algebraic Side-Channel Attacks......Page 303
Conclusions......Page 304
Introduction......Page 307
Security Model......Page 309
Notations and Building Blocks......Page 312
Description of the Protocols......Page 314
Extensions of the Protocols......Page 319
Simulation-Sound NIZK Arguments for Relations of Ciphertexts and Commitments......Page 320
Introduction......Page 326
The Use of Pairings in Proxy Re-Encryption......Page 327
Our Contributions......Page 328
Framework of Unidirectional Proxy Re-Encryption......Page 329
Security Models for ``Token-Controlled'' Re-Encryption......Page 330
Review of Shao-Cao's Scheme......Page 333
Our Attack......Page 335
Flaws in the Proof and A Possible Fix......Page 336
Construction......Page 337
Security Analysis......Page 338
Efficiency Comparisons......Page 339
Conclusions......Page 340
Introduction......Page 343
Our Contributions......Page 344
Public Key Encryption with Non-interactive Opening......Page 347
Robust Non-interactive Threshold Public-Key Cryptosystems......Page 348
Stronger Proof Soundness Definitions......Page 350
Witness-Recovering Encryption Does Not Suffice......Page 351
Stronger Decryption-Consistency Definitions for TPKC......Page 352
Robust TPKC Implies PKENO......Page 353
New PKENO Constructions Implied by TPKC......Page 355
PKENO without Pairings in the Random-Oracle Model......Page 356
PKENO Based on the Decision Linear Assumption......Page 357
Introduction......Page 361
Related Work......Page 363
Notations and Assumptions......Page 364
Parallel Diffie-Hellman Key Exchange......Page 365
GKE+P Protocol from Modified BD and PDHKE......Page 366
GKE+S Protocol from Modified BD and PDHKE......Page 367
Participants, Sessions, and Correctness of GKE+P Protocols......Page 368
Adversarial Model and Security Goals......Page 369
Security of Our GKE+P and GKE+S Protocols......Page 372
Performance Comparison......Page 373
Conclusion......Page 374
Proof of Theorem 1......Page 377
Physical Unclonable Functions......Page 379
Getting Rid of the Trusted Remote Reader......Page 380
Authenticated Quantum Key Exchange......Page 381
Preliminaries......Page 382
Authentication Protocol 1......Page 384
Security of Authentication Protocol 1......Page 385
Authentication Protocol 2......Page 386
Limitations on the State Preparation......Page 387
Attack Model......Page 388
Protocol Description......Page 389
Remarks......Page 390
Security of the Authenticated QKE Protocol......Page 391
Summary and Future Work......Page 394
Background and Motivation......Page 397
Our Contribution......Page 398
Definitions and Preliminaries......Page 399
Practical Security Evaluation of GF-NLFSR against Differential and Linear Cryptanalysis......Page 401
Brief Description of Camellia......Page 404
Differential and Linear Cryptanalysis of p-Camellia......Page 405
Other Attacks on p-Camellia......Page 406
Implementation Advantages......Page 407
Parallelizing SMS4: p-SMS4......Page 409
Related-Key Differential Attack on p-SMS4......Page 410
Other Attacks on p-SMS4......Page 411
Implementation Advantages......Page 413
Conclusion......Page 414
Figure of p-Camellia......Page 416
Introduction......Page 417
Fixed-Input-Length Compression Function......Page 418
The Condition Function......Page 419
Algorithm Specification......Page 420
Searching for High Raw Probability......Page 421
Searching for Sparsity at the End......Page 422
Randomizing the Search......Page 423
Linear Differentials......Page 424
Conclusion......Page 427
Introduction......Page 429
The SHAvite-3-512 Hash Function......Page 430
Message Expansion......Page 431
The Cancellation Property......Page 433
From Partial Preimages to Preimages and Collisions......Page 435
Attacks on the Compression Function......Page 436
Outline of the Attack......Page 437
Using Different Salt Values......Page 439
Collision and Preimages for 14 Rounds......Page 441
Extending the 9 Round Attack......Page 442
Second Preimage Attack......Page 443
Conclusion......Page 444
Partial Preimage for 13 Rounds of the Compression of SHAvite-512......Page 445
26 back-matter......Page 447