Advances in Cryptology - EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, ... Computer Science / Security and Cryptology)

00 front-matter......Page 1
Introduction......Page 12
Informal Description of Results......Page 14
Discussion and Applications......Page 15
Ideal Lattices......Page 17
Techniques......Page 19
Preliminaries......Page 20
Lattice Background......Page 21
Algebraic Number Theory Background......Page 22
Main Reduction......Page 25
Main Theorem and Proof Overview......Page 26
Core Step: The BDD to LWE Reduction......Page 27
Pseudorandomness of Ring-LWE......Page 29
Worst-Case Search to Worst-Case Decision......Page 30
Introduction......Page 35
Preliminaries......Page 36
Homomorphic Encryption......Page 37
A Somewhat Homomorphic Encryption Scheme......Page 38
The Construction......Page 39
Correctness......Page 40
Optimizations......Page 41
Security of the Somewhat Homomorphic Scheme......Page 42
Reduction to Approximate-GCD......Page 43
The Approximate GCD of Two Numbers......Page 46
The Approximate GCD of Many Numbers......Page 47
Squashing the Decryption Circuit......Page 48
Bootstrapping Achieved!......Page 50
Conclusion and Open Problems......Page 53
Introduction......Page 55
Subgroup Decision Problems......Page 58
Product Groups, DDH, and d-Linear Assumptions......Page 60
Pairings on Product Groups......Page 62
Performance Analysis......Page 66
Application: The BGN Cryptosystem......Page 68
More Applications......Page 69
Introduction......Page 73
Attribute-Based Encryption......Page 74
Predicate Encryption for Inner Products......Page 77
Related Work......Page 79
Background......Page 80
Transformation from One-Use CP-ABE......Page 83
Our Fully Secure CP-ABE System......Page 84
Discussion......Page 89
Our Approach and Key Technique......Page 90
Dual Pairing Vector Spaces by Direct Product of Symmetric Pairing Groups......Page 92
Assumption......Page 93
Definition of Predicate Encryption......Page 94
The Proposed PE Scheme......Page 95
The Proposed HPE Scheme......Page 99
Introduction......Page 103
Basic Idea......Page 105
Our Contributions......Page 107
Preliminaries......Page 108
Public-Key Encryption and Digital Signatures......Page 109
Security of Digital Signatures in the Context of ES......Page 111
Virtual Black-Box Properties......Page 112
Algebraic Setting and Complexity Assumptions......Page 115
Linear Encryption Scheme......Page 116
The Obfuscator for the ES Functionality......Page 117
Concluding Remarks......Page 120
EncryptedSignature-then-Encryption......Page 122
Obfuscation for EStE......Page 123
Introduction......Page 124
Our Results......Page 126
Related Work......Page 130
Preliminaries......Page 131
Definition......Page 132
A Construction of IB-HPS Based on Bilinear Groups......Page 134
Parameters of Three IB-HPS Constructions......Page 136
Leakage-Resilient IBE from IB-HPS......Page 137
Leakage Amplification of IB-HPS......Page 138
Public-Key Encryption and IBE in the BRM......Page 140
Extensions......Page 141
Comparison of PKE (and IBE) in BRM Constructions......Page 143
Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases......Page 146
Introduction......Page 147
Our Results......Page 148
Overview of the Techniques......Page 150
Preliminaries and Definitions......Page 151
Leakage-Resilient Circuit Transformation......Page 152
Circuit Transformation from Linear Secret-Sharing......Page 154
The Transformation for Stateless Circuits......Page 156
Proof of Security......Page 158
Reconstructors for Single Gadgets......Page 159
Security of Full Circuit Transformation......Page 161
AC0 Leakage......Page 162
Security against Noisy Leakage......Page 163
A New Circuit Transformation against Noisy Leakage......Page 164
References......Page 166
Introduction......Page 168
Prior Work......Page 170
Overview of Our Approach......Page 171
Definitions......Page 172
A Useful Lemma......Page 174
1p-Security for Functionalities with Polynomial-Size Domain......Page 175
1p-Security for Functionalities with Polynomial-Size Range......Page 179
Impossibility of 1p-Security and Security-with-Abort Simultaneously......Page 181
Impossibility of 1p-Security for General Functions......Page 183
Conclusions and Open Questions......Page 185
Introduction......Page 188
Model and Preliminaries......Page 192
A Generic Protocol with Optimal Private Communication......Page 195
Instantiating the Generic Protocol......Page 198
A Protocol with Logarithmic Public Communication......Page 199
Private Communication Lower Bound......Page 201
Amortized Use of the Public Channel......Page 203
References......Page 206
Introduction......Page 208
The Idea Behind Our Result......Page 209
The Essence of Our Meta-reduction and Impossibility of Random Oracle Instantiations......Page 211
Related Work......Page 212
Blind Signatures......Page 213
Hard Problems and Black-Box Reductions......Page 215
Preliminaries......Page 216
Impossibility Result......Page 219
Impossibility Result for Statistically Blind Signature Schemes......Page 221
Preliminaries......Page 222
Impossibility Result......Page 223
Conclusion......Page 224
Minimizing Assumptions for Secure Key Agreement......Page 227
The Basic Idea: Systems, Correlations, and Non-locality......Page 228
Non-locality Exists in Nature......Page 229
The General Non-signaling Adversary......Page 230
Non-locality + Non-signaling = Limited Bias = Secrecy......Page 231
Our Protocol and Results......Page 232
Modeling the Attacks......Page 234
Security Definition......Page 236
Privacy Amplification......Page 238
Information Reconciliation and Privacy Amplification: From One to Several Bits......Page 241
The Quantum Regime......Page 242
Concluding Remarks and Open Questions......Page 243
Introduction......Page 246
Random Knapsacks......Page 248
Asymptotic Values of Binomials......Page 249
Distribution of Random Knapsack Sums......Page 250
The Algorithm of Schroeppel and Shamir......Page 251
A Variation on the Schroeppel and Shamir Algorithm......Page 253
Application to Unbalanced Knapsacks......Page 255
Basic Principle......Page 256
Simple Algorithm......Page 258
A Better Heuristic Algorithm......Page 261
A Practical Experiment......Page 262
Possible Extensions and Applications......Page 263
Conclusion, Open Problems......Page 265
Graph of Compared Complexities......Page 267
Introduction......Page 268
Preliminaries......Page 271
Enumeration......Page 272
Description......Page 273
Complexity......Page 274
Running Time Analysis......Page 275
Success Probability Analysis......Page 277
Running Time Analysis......Page 278
Asymptotic Analysis......Page 279
Experiments......Page 282
Verifying the Heuristics......Page 284
The Analysis of Schnorr and Hörner......Page 287
Pseudo-code of the Pruned Enumeration Code......Page 288
Introduction......Page 290
McEliece Public-Key Cryptosystem......Page 293
Algebraic Approach......Page 294
Algebraic Cryptanalysis of the Quasi-Cyclic Variant......Page 298
Algebraic Cryptanalysis of the Dyadic Variant......Page 300
Conclusion......Page 303
Gröbner Basics......Page 306
Description of the Variant Based on Dyadic Goppa Codes......Page 307
Proof of Proposition 4......Page 308
Introduction......Page 310
Our Notations......Page 313
Related-Key Attacks......Page 314
A Related-Key (XOR Difference) Attack......Page 315
Attacks on 10 Round Variants of AES-256......Page 322
Chosen-Ciphertext Attack......Page 323
A Related-Key Distinguisher for 8 Rounds......Page 324
Related-Subkey Attacks on 11 Rounds......Page 325
The Choice of the Data and the Key Differences......Page 326
Conclusions......Page 327
Comments on Figures 2 and 3......Page 329
Cryptography between Wonderland and Underland......Page 331
Introduction......Page 333
A Tool for Search of Related-Key Differential Characteristics......Page 336
AES......Page 342
Related-Key Boomerang Attack on 7-Round AES-128......Page 343
Camellia......Page 345
Khazad......Page 346
Related-Key Boomerang Attacks on 7 Rounds of Khazad......Page 347
FOX and Anubis......Page 348
Conclusions and Future Research......Page 349
Introduction......Page 356
Our Contribution......Page 357
SSH Binary Packet Protocol......Page 358
Modeling the SSH BPP and Its Security......Page 359
Notation......Page 360
Building Blocks......Page 361
Encode-then-Encrypt&MAC......Page 363
Chosen Plaintext Security......Page 365
Chosen Ciphertext Security......Page 367
Security Analysis......Page 369
Conclusion......Page 371
Introduction......Page 373
Preliminaries......Page 378
Computationally Sound Greatest Fixed Point Semantics......Page 381
Example......Page 385
Discussion and Open Problems......Page 386
Encryption Schemes Secure against Chosen-Ciphertext Selective Opening Attacks......Page 392
Introduction......Page 393
Preliminaries......Page 397
Warmup: An NC-CPA Secure Scheme......Page 401
Hash Proof Systems with Explainable Domains......Page 403
Cross-Authentication Codes......Page 405
Our NC-CCA Secure Scheme......Page 407
Security Analysis......Page 408
Introduction......Page 414
Preliminaries......Page 420
Agility Definitions......Page 421
Negative Results......Page 424
Positive Results......Page 430
Bounded Key-Dependent Message Security......Page 434
Introduction......Page 435
Our Results......Page 436
Our Techniques......Page 438
Preliminaries......Page 440
Garbled Circuits......Page 441
Key-Dependent Message Security......Page 442
KDM Security from Homomorphic Encryption......Page 443
Targeted Encryption......Page 445
Single-Key Security of the Construction......Page 447
Multiple Key Security......Page 449
Application to Formal Cryptography......Page 450
Extending Haitner and Holenstein's Impossibility Result......Page 452
Introduction......Page 456
The Complexity of MPC......Page 457
Our Results......Page 458
The Computational Overhead of Cryptography......Page 460
The Model......Page 461
Overview of the Protocol......Page 462
Subprotocols......Page 464
Permuting Elements within a Block......Page 465
The Main Protocol......Page 471
Application to Two-Party Cryptography......Page 472
References......Page 474
Introduction......Page 477
Property-Based vs. Simulation-Based Definition......Page 478
Broadcast in the Literature......Page 479
Contributions......Page 480
Comparison with Previous Work......Page 481
Synchronous Communication (No Multi-send)......Page 482
Security Definition......Page 483
Perfect Security (No Setup)......Page 484
Statistical and Computational Security (with a Trusted Setup)......Page 488
Conclusions......Page 494
Introduction......Page 497
How to Interpret Our Result......Page 500
Related Work......Page 502
Preliminaries......Page 503
Quantum Universal Composability......Page 504
Relating Classical and Quantum-UC......Page 509
Corrupted Alice......Page 511
Multi-party Computation......Page 514
Introduction......Page 517
Our Contributions......Page 518
Learning with Errors (LWE)......Page 520
Trapdoor Sampling......Page 521
The Encryption Scheme......Page 522
Homomorphic Operations......Page 523
Setting the Parameters......Page 524
Security......Page 525
Formula Privacy......Page 526
Encrypting Polynomials and Large Integers......Page 527
Identity-Based and Leakage-Resilient BGN-Type Encryption......Page 528
The Aguilar Melchor-Gaborit-Herranz Transformation......Page 530
Introduction......Page 534
Our Results......Page 535
Overview of Bonsai Trees and Applications......Page 536
Complexity and Open Problems......Page 540
Notation......Page 541
Cryptographic Definitions......Page 542
Lattices......Page 544
Undirected Growth......Page 546
Extending Control......Page 547
Signatures......Page 549
Security......Page 550
Key Encapsulation Mechanism......Page 551
BTE and HIBE Scheme......Page 552
Full Security in the Random Oracle Model......Page 555
Full Security in the Standard Model......Page 558
Introduction......Page 564
Preliminaries......Page 565
IBE and Hierarchical IBE......Page 566
Statistical Distance......Page 567
The Gram-Schmidt Norm of a Basis......Page 568
Discrete Gaussians......Page 569
The LWE Hardness Assumption......Page 570
Random Subset Sums......Page 571
Algorithm SampleLeft......Page 572
Algorithm SampleRight......Page 573
Encoding Identities as Matrices......Page 574
Intuition......Page 576
The Basic IBE Construction......Page 577
Security Reduction......Page 578
Extensions: HIBE and Adaptively-Secure IBE......Page 581
Conclusion and Open Problems......Page 582
Introduction......Page 584
Security Definitions......Page 589
Weak Collision Resistance and Unforgeability......Page 594
Collision Resistance and Indistinguishability......Page 598
Preimage Awareness and Indifferentiability......Page 599
The Quadratic Blockcipher-Based Compression Function......Page 601
The Quadratic Cascade Compression Function......Page 602
The Proof of Lemma 5......Page 604
Improved Analysis of Lucks' Double-Piped Mode of Operation......Page 605
Introduction......Page 608
Basic Results......Page 611
Intuition for Stam's Bound: The Case r > 1......Page 613
Intuition for r = 1 and Reduction to r = 1......Page 615
Main Result......Page 616
An Alternate Approach for Random Primitives......Page 620
Universal One-Way Hash Functions via Inaccessible Entropy......Page 627
Introduction......Page 628
Our Constructions......Page 629
Perspective......Page 631
Inaccessible Entropy for Inversion Problems......Page 632
A Direct Construction......Page 635
A More Efficient Construction......Page 639
The More Efficient UOWHF......Page 644
UOWHF via a Direct Construction......Page 646
Introduction......Page 649
Our Results......Page 650
Our Techniques......Page 652
Concurrent Non-malleable Commitments......Page 653
Overview of Our Construction......Page 654
Handling Identities of Length logloglogn + O(1)......Page 655
Proof of Simulation-Soundness......Page 659
Non-malleability Amplification......Page 661
Construction from Sub-exponential One-Way Functions......Page 663
nmCom Is One-Many Non-malleable......Page 666
Introduction......Page 667
Related Work......Page 670
Definition......Page 671
VRF Construction from the DDHE Assumption......Page 672
Proof of DDHE VRF......Page 674
Conclusion and Open Directions......Page 679
Proof of Claim 5......Page 682
Introduction......Page 684
Our Contributions......Page 685
Related Work......Page 687
Open Problems......Page 688
Adaptive Trapdoor Functions......Page 689
CCA-Secure PKE from ATDFs......Page 691
Constructing ATDFs from Stronger TDFs......Page 693
Constructions from Correlated-Product TDFs......Page 694
Constructions from Lossy and All-But-One TDFs......Page 695
A Black-Box Separation......Page 696
Tag-Based ATDF from an Assumption on RSA Inversion......Page 698
35 back-matter......Page 704