This book constitutes the refereed proceedings of the 10th International Conference on Cryptology in India, INDOCRYPT 2009, held in New Dehli, India, in December 2009.
The 28 revised full papers were carefully reviewed and selected from 104 submissions. The papers are organized in topical sections on post-quantum cryptology, key agreement protocols, side channel attacks, symmetric cryptology, hash functions, number theoretic cryptology, lightweight cryptology, signature protocols, and multiparty computation.
Author(s): Bimal Roy, Nicolas Sendrier
Edition: 1st Edition.
Publisher: Springer
Year: 2010
Language: English
Pages: 443
Introduction......Page 13
Two Average-Case Problems......Page 14
SWIFFT Compression Functions......Page 16
SWIFFT Lattice......Page 18
Parameter Generation......Page 19
Recommended Parameters......Page 20
Security Analysis......Page 21
Experiments......Page 22
SIS Reduces to SIS'......Page 26
IdealSIS Reduces to IdealSIS'......Page 27
Hybrid Lattice Reduction......Page 28
Introduction......Page 30
The Tree Algorithm......Page 32
Wagner in Memory-Restricted Environments......Page 33
Details of the FSB Hash Function......Page 35
Attacking the Compression Function of FSB_{48}......Page 36
How Large Is a List Entry?......Page 38
The Strategy......Page 39
Implementing the Attack......Page 42
Parallelization......Page 43
Efficient Implementation......Page 45
Results......Page 46
Time-Storage Tradeoffs......Page 47
Scalability Analysis......Page 48
Introduction......Page 51
Examples......Page 53
Certificate Format......Page 54
The One-Pass and Three-Pass Unified Model Protocols......Page 55
Generic 2-Pass KEM Protocols......Page 57
KEA+h and $\tau$......Page 58
Security Model......Page 60
The NAXOS-C and DHKEA Protocols......Page 63
Concluding Remarks......Page 65
The $\tau$ Protocol......Page 67
Introduction......Page 69
Background......Page 70
Security Attributes......Page 71
Security Model......Page 73
Attacks......Page 75
Al-Riyami and Paterson (AP) Protocol......Page 76
Mandt and Tan (MT) Protocol......Page 77
Wang et al. (WCW) Protocol......Page 79
Shao Protocol......Page 80
Shi Li (SL) Protocol......Page 81
Conclusion......Page 82
Introduction......Page 84
Description of Rabbit......Page 85
Previous Work on Rabbit......Page 87
Fault Attacks on Stream Ciphers......Page 88
Motivations......Page 89
Fault Model......Page 90
Fault Analysis......Page 91
Attack Algorithm......Page 94
Extension to a Full Key Recovery......Page 95
Conclusion......Page 96
Second Set of Equations......Page 98
Case of Unexploitable Faults......Page 99
Introduction......Page 100
Physically Obfuscated Key......Page 101
Obfuscation of Basic Operations......Page 102
Towards Obfuscating the Taps and the State Simultaneously......Page 104
Fill in the Gap......Page 105
Krawczyk's MACs and LFSR-Based Hashing......Page 106
Self-shrinking Generator......Page 107
Trivium......Page 109
Conclusion......Page 111
Krawczyk's MACs......Page 114
Introduction......Page 116
Related Work......Page 117
The Clefia Structure......Page 118
Small Tables......Page 120
Extraction of Round Keys $RK2$ and $RK3$......Page 121
Cache Attacks on Small Table Cipher Implementations......Page 122
Modifications of Bernstein's Attack......Page 124
Determining $RK2 \oplus WK0$ and $RK3 \oplus WK1$......Page 125
Computing $RK2$ and $RK3$......Page 126
Results......Page 127
Conclusion......Page 128
Software Oriented Stream Ciphers Based upon FCSRs in Diversified Mode......Page 131
FCSR Automata in Ring Representation......Page 132
Diversified FCSR Automata......Page 133
Design of a Diversified FCSR for Software Applications......Page 134
Design of X-FCSR-128 v.2......Page 138
Extraction Function......Page 139
Key and IV Injection......Page 140
Security......Page 141
Performances......Page 142
Conclusion......Page 143
Random Algorithms to Pick Good $q$s......Page 145
The $T$ Matrix......Page 146
The S-Box $S$......Page 147
Introduction......Page 148
Preliminary......Page 149
Symmetric Negabent Function......Page 151
Conclusions......Page 154
Introduction......Page 156
The AES Encryption Algorithm......Page 157
A 4-Round Distinguisher of AES......Page 158
A New Attack on AES......Page 160
A 4-Round Differential Distinguisher......Page 161
The Attack......Page 162
A 4-Round Collision-Differential Distinguisher of AES......Page 164
Comparison of Attacks on AES......Page 165
Conclusion......Page 166
Introduction......Page 169
HAS-160......Page 170
The Related-Key Rectangle Attack......Page 173
A 71-Round Related-Key Rectangle Distinguisher......Page 175
The Attack on the Full HAS-160 Encryption Mode......Page 177
Analysis of the Attack......Page 178
Conclusion......Page 179
Introduction......Page 181
The SHAMATA Hash Function......Page 182
Observation: Another Description of the Shift Register......Page 183
Notations and Setting of Second Preimage Attack......Page 184
Procedure of Second Preimage Attack......Page 185
Building Message Candidates of the First Segment of Message......Page 186
Building Message Candidates for the Second Segment of Message......Page 188
Complexity of the Attack......Page 191
Conclusion......Page 192
Introduction......Page 194
Preliminaries......Page 196
Problems with the MACs Recommended for WSN......Page 197
A Comparison of Some Practical MACs for BSN......Page 199
TuLP and TuLP-128......Page 200
Security Analysis......Page 204
Performance......Page 207
Conclusion......Page 208
Introduction......Page 211
Notations and Preliminaries......Page 213
Indifferentiability of GDE......Page 216
Security Games......Page 217
Merkle-Damgård with Prefix Free Padding......Page 221
Merkle-Damgård with HAIFA......Page 222
Tree Mode of Operation with Counter......Page 224
Distinguishing Attacks on Merkle-Damgård Constructions......Page 225
Distinguishing Attacks on Tree Mode......Page 226
Conclusion and Future Work......Page 227
Proof of Lemma 1......Page 228
Introduction......Page 231
SIMD Step Function......Page 232
The Basic Attack Strategy......Page 234
Differential Behavior of IF and MAJ......Page 235
Finding Good Characteristics......Page 236
Estimating the Probability for a Characteristic......Page 237
Differential $q$-Multicollision......Page 239
The Differential Characteristic......Page 240
The Complexity of the Attack......Page 241
Conclusions......Page 242
Differential Characteristic for the 4 Steps in the Feed-Forward......Page 244
Introduction......Page 245
Preliminaries......Page 247
Free Abelian Groups......Page 248
Signed Quadratic Residues......Page 249
Our Choice for N and G......Page 250
Strong Signed QR-RSA (SQR-RSA) Assumption......Page 251
$\mathbb{Z}*_{N}$ Is Pseudo-free......Page 253
Introduction......Page 260
Hancke and Kuhn's Protocol......Page 262
Munilla and Peinado's Protocol......Page 263
MUSE-3 HK......Page 265
Generation of the Registers......Page 267
Memory Consumption......Page 268
Hancke and Kuhn......Page 269
Kim and Avoine......Page 271
Brands and Chaum......Page 274
On the Implementability of MUSE......Page 275
Conclusion......Page 276
Introduction......Page 278
The MSP430 Microcontroller......Page 279
Multiplication......Page 280
Reduction......Page 283
Identity Based Cryptography Using Pairings......Page 285
MNT Curve over a 160-Bit Field......Page 286
Elliptic Curve Cryptography......Page 287
Conclusion......Page 290
Introduction......Page 293
Paillier's Scheme......Page 295
The Most Significant Bit of $Class$ Is Hard......Page 296
Conclusion......Page 301
Introduction......Page 302
Identification Codes......Page 303
General Definition......Page 304
Application to Our Setting......Page 305
Vaudenay's Model for Privacy......Page 306
Our Protocol for Interrogation......Page 309
Specifications Using Reed-Solomon Based Identification Codes......Page 310
Assumptions......Page 311
Effect of Passive Eavesdropping......Page 312
Privacy......Page 314
Practical Parameters......Page 315
Conclusion......Page 316
Security against Impersonation......Page 318
Privacy......Page 319
Introduction......Page 320
Learning Parity with Noise......Page 321
The $F_{f}$ Family of Protocols......Page 323
Structure of the $f$ Function......Page 325
Lowering the Complexity of the LPN Problem......Page 327
A Resynchronization Attack......Page 328
Decreasing the Noise and Solving for $K'$......Page 329
Conclusion......Page 330
Introduction......Page 333
Signcryption......Page 336
Security......Page 337
Simple Composition Using Symmetric Key Primitives......Page 340
Simple Composition Using Tag-Based Encryption......Page 342
Signcryption Composability......Page 344
Signcryption from SC-Composable Schemes......Page 345
(T)NIKE Schemes in the Random Oracle Model......Page 346
TBE and TBKEM Schemes......Page 347
Concrete SC-Composable Schemes......Page 348
Comparison......Page 349
Introduction......Page 355
Related Work......Page 356
Convertible Designated Confirmer Signatures (CDCS)......Page 358
Security Model......Page 359
The Plain ``Encryption of a Signature'' Paradigm......Page 360
The Construction......Page 366
Efficient Instantiations Using Certain Signatures and Cryptosystems......Page 367
Comparisons and Possible Extentions......Page 371
Introduction......Page 375
Verifiably Encrypted Signature Schemes......Page 378
Our Construction......Page 380
Conclusions......Page 385
Digital Signatures......Page 387
Merkle Authentication Trees......Page 388
Completeness of Our Construction......Page 389
Introduction......Page 390
Computational Assumptions......Page 394
Model for Identity Based Aggregate Signcryption(IBAS)......Page 395
Unforgeability......Page 396
IBAS-1 Scheme......Page 397
Security Proof of IBAS-1......Page 398
IBAS-2 Scheme......Page 403
IBAS-3 Scheme......Page 405
Efficiency......Page 407
Conclusion and Open Problems......Page 408
Round Efficient Unconditionally Secure MPC and Multiparty Set Intersection with Optimal Resilience......Page 410
Introduction......Page 411
Overview of Our UMPC Protocol......Page 413
Robust Generation of Multiplication Triples......Page 414
Information Checking Protocol and IC Signatures......Page 415
Unconditional Verifiable Secret Sharing......Page 417
Public Reconstruction of $t-2D^(+,\ell)$-sharing of $\ell$ Values......Page 419
Public Reconstruction of $t-1D^(+,\ell)$-sharing of Values......Page 420
Proving $c=ab$......Page 421
Robust Multiplication Protocol: Our Main Contribution......Page 422
Preparation Phase......Page 424
Input and Computation Phase......Page 425
Unconditionally Secure Multiparty Set Intersection......Page 426
Introduction......Page 430
This Work......Page 431
Oblivious Naor-Pinkas Cryptosystems......Page 433
Non-committing Encryptions: Functionality and Security Definition......Page 435
Description of Non-committing Protocol......Page 437
The Proof of Security......Page 438
Conclusion......Page 440
Introduction......Page 442
Homomorphic Encryption Schemes......Page 444
Domains $Z_{p}*$......Page 445
Domains $Z_{pq}*$......Page 446
Oblivious Multivariate Polynomial Evaluation ($OMPE$)......Page 447
The Protocol $Mult2Add$......Page 448
The Complete $OMPE$ Protocol......Page 449
Complexity Analysis......Page 450
Conclusion and Future Work......Page 451
Proof (schetch) of Theorem 1......Page 453
