Public Key Cryptography - PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010, ... Computer Science Security and Cryptology)

Introduction......Page 1
Our Contributions......Page 3
Notation......Page 4
Key Encapsulation Mechanisms......Page 5
Diffie-Hellman Assumptions......Page 6
Chosen-Ciphertext Secure Key Encapsulation......Page 7
Constrained Chosen-Ciphertext Secure Key Encapsulation......Page 10
Reducing the Size of the Public Key......Page 11
Public-Key Encryption with Public Keys of Size $\\mathcal{O}$(1)......Page 12
Public-Key Encryption with Public-Key of Size $\\mathcal{O}$($ qrt{n}$)......Page 15
Introduction......Page 19
Attribute-Based Encryption......Page 22
The Augmented Multi-sequence of Exponents Diffie-Hellman Problem......Page 24
Description of the Scheme......Page 26
Security Analysis......Page 28
More General Decryption Policies......Page 31
Conclusion......Page 32
Introduction......Page 35
Keys......Page 38
Encryption/Decryption......Page 39
Description of the Attack......Page 40
Level 1 Attack: Decomposition of Ideals......Page 41
Level 2 Attack: Computing in the Field of Fractions $\\mathbb{F}_p$(t)......Page 42
Level 3 Attack: Computing in Finite Fields $\\mathbb{F}_{p^m}$......Page 43
A Concrete Example......Page 44
Complexity Analysis......Page 46
Experimental Results......Page 47
Conclusion......Page 50
Gr\\\"{o}bner Bases and Normal Form......Page 51
Magma Code for the Level 1 Attack......Page 52
Introduction......Page 53
Basics......Page 55
Unravelled Linearization and the Boneh-Durfee Attack......Page 56
CRT Exponents......Page 60
Experiments......Page 65
Counting #u, #v, #w, #x......Page 67
Improving the Bound Using Extrashifts......Page 68
Introduction......Page 70
Implicit Factoring of Two RSA Moduli with Shared MSBs......Page 74
Implicit Factoring of k RSA Moduli with Shared MSBs......Page 76
Implicit Factoring with Shared Bits in the Middle......Page 78
Shared MSBs......Page 81
Shared Bits in the Middle......Page 83
Conclusion......Page 84
Common Results on Lattice......Page 86
Exact Computation of the Volume of Lattice L of Section 3......Page 87
Introduction......Page 88
Definition of Consistent Computations......Page 90
List Commitment Schemes......Page 94
Consistent Adaptive Oblivious Transfer......Page 97
Consistent Conditional Disclosure of Secrets......Page 101
Discussion and Open Problems......Page 103
Introduction......Page 107
Background......Page 108
Challenges and Techniques......Page 109
Preliminaries......Page 110
Lower Bound on ($m,n,l$)-CPIR Communication......Page 111
Restricted Multi-query CPIR......Page 113
Multi-query ($m,n,l$)-CPIR for Small m......Page 116
Multi-query ($m,n,l$)-CPIR for Large Values of m and $l \\leq log_2(n/m)$......Page 118
Summary: Communication-Optimal Multi-query CPIR......Page 122
Introduction......Page 124
Previous Work......Page 125
Our Contributions......Page 127
Syntax of Optimistic Fair Exchange......Page 128
Security against Signer(s)......Page 129
Security against Verifier(s)......Page 130
Security against the Arbitrator......Page 131
Strong Resolution-Ambiguity......Page 133
Definition of Strong Resolution-Ambiguity......Page 134
Optimistic Fair Exchange Protocols with/without Strong Resolution-Ambiguity......Page 135
Security of Optimistic Fair Exchange Protocols with Strong Resolution-Ambiguity......Page 136
The Proposed Protocol......Page 137
Comparison to Previous Protocols......Page 138
Conclusion......Page 139
Introduction......Page 142
Network Coding......Page 145
Network Coding Signatures......Page 146
Network Coding over the Integers......Page 148
Improvements to Existing Schemes......Page 150
An RSA-Based Network Coding Signature Scheme......Page 152
Proof of Security......Page 155
Homomorphic Hashing Modulo a Composite......Page 157
Introduction......Page 161
Network Coding......Page 163
Multiple Sources, Multiple Files......Page 164
Signatures and File Identifiers......Page 166
Generic Attack (For Arbitrary File Identifiers)......Page 167
Network Coding Signatures......Page 169
Security......Page 170
Vector Hashes......Page 172
The Construction......Page 173
Introduction......Page 177
Bilinear Groups......Page 180
Groth–Sahai Proofs......Page 182
Equations for $i$ and $p$......Page 184
SXDH-Based Proofs......Page 185
SDLIN-Based Proofs......Page 187
Performance Comparison......Page 189
Summary......Page 191
Introduction......Page 193
Our Contribution......Page 196
Concurrent Non-Malleable Commitments and Decommitments......Page 197
Constant-Round Statistically Binding Concurrent NMc and Concurrent NMd......Page 198
Concluding Remarks......Page 206
Introduction......Page 209
Pairing, Towering and Squaring-Friendly Fields......Page 210
New Fast Squaring in the Cyclotomic Subgroup......Page 211
Fast Squaring in $\\text{Res}_{\\F_{q^2}/\\F_{q}} G_{\\Phi_2(q)}$......Page 212
Fast Squaring in $\\text{Res}_{\\F_{q^6}/\\F_{q^2}} G_{\\Phi_6(q)}$......Page 213
Comparison with Prior Work......Page 215
Operation Counts......Page 216
Application to Pairing-Based Cryptography......Page 217
BN Curves......Page 218
Application to Torus-Based Cryptography......Page 220
Conclusion......Page 221
Introduction......Page 224
Background on Pairings......Page 226
Computing the Ate Pairing Entirely on the Twisted Curve......Page 228
Pairings on $y^2$=$x^3$+ax with Even Embedding Degrees......Page 231
Pairings on $y^2$=$x^3$+b with Even Embedding Degrees......Page 234
Fast Formulas for Pairing Computations with Cubic Twists......Page 235
Comparisons......Page 237
Introduction......Page 243
Definition......Page 245
Universality of the Model......Page 247
Unified Addition Formulas......Page 248
Complete Addition Formulas......Page 249
Addition......Page 251
Doubling......Page 252
Tripling......Page 253
Differential Addition......Page 254
Conclusion......Page 256
The Number of Distinct $j$-Invariants......Page 258
The Number of $\\mathbb{F}_q$-Isomorphism Classes......Page 260
Background......Page 261
Our Contribution......Page 262
Related Work......Page 264
All-But-One Trapdoor Functions......Page 266
Re-applicable Lossy Trapdoor Functions......Page 267
Bidirectional and Multi-Hop PRE-CCA Scheme......Page 268
Bidirectional and Multi-Hop PRE-CCA Security......Page 269
Description of Our Scheme......Page 270
Security of Our Scheme......Page 272
Realization of Re-applicable LTDFs Based on DDH Assumption......Page 274
Introduction......Page 279
Our Contributions......Page 281
Related Work......Page 282
Lossy Trapdoor Functions......Page 283
Correlation-Secure Trapdoor Functions......Page 285
A Construction Based on the Quadratic Residuosity Assumption......Page 286
A Construction Based on the d-Linear Assumption......Page 288
Correlated Input Security from Syndrome Decoding......Page 291
Introduction......Page 296
Preliminaries......Page 299
Products and Lossiness Amplification......Page 302
Subset Reconstructible Distributions......Page 303
The Rosen-Segev Construction......Page 304
Our Result......Page 305
An Explicit Construction of a Slightly Lossy TDF......Page 307
Introduction......Page 312
Our Contributions......Page 314
Preliminaries......Page 317
The El Gamal Encryption Scheme......Page 318
Balanced Allocation......Page 319
Secure Set Intersection......Page 320
Checking the Polynomials......Page 322
Secure Set-Intersection in the Presence of Malicious Adversaries......Page 323
A Very Efficient Heuristic Construction......Page 327
Introduction......Page 332
Tools and Definitions......Page 335
Secure Text Search Protocols......Page 336
``Honest-But-Curious\'\' Secure Text Search......Page 337
Secure Text Search in the Presence of Malicious Adversaries......Page 339
Secure Oblivious Automata Evaluation......Page 340
A Zero-Knowledge Proof of Knowledge for a KMP Automaton......Page 346
Text Search Protocol with Simulation Based Security......Page 348
Conclusion......Page 349
Introduction......Page 351
Outline of Function Field Sieve......Page 353
Comparison of Polynomial Selection on JL02-FFS and JL06-FFS......Page 354
Polynomial Selection of JL06-FFS and Its Sieving Area......Page 355
Comparison of Sieving Area......Page 356
Collection of Relations......Page 358
Linear Algebra......Page 360
Computation Results......Page 362
Concluding Remarks......Page 365
Introduction......Page 368
The Gaudry-Schost Algorithm......Page 370
Theoretical Analysis......Page 371
Pseudorandom Walks and Practical Considerations......Page 372
Equivalence Classes......Page 373
The Gaudry-Schost Algorithm on Equivalence Classes......Page 374
The New Algorithm......Page 375
Experimental Results......Page 378
Conclusion......Page 379
Background on the Pollard Kangaroo Method......Page 381
Solving Using Equivalence Classes......Page 382
Larger Equivalence Classes in the GLV Method......Page 383
Introduction......Page 384
Syntax and Security Definition for Functional Encryption......Page 388
Inner Product Encryption and Its Consequences......Page 390
Warm-Up: Selectively Secure Zero IPE from Spatial Encryption......Page 392
Adaptively Secure Zero IPE under Simple Assumptions......Page 393
Negated Spatial Encryption......Page 397
Non-zero IPE under Simple Assumptions......Page 398
A Generalization of the Scheme and Its Application......Page 399
For the Zero IPE Scheme of Section 4.2......Page 401
For the Non-zero IPE Scheme of Section 5.2......Page 402
Introduction......Page 403
Definitions of the Weakened Random Oracle Models......Page 408
Difference from the Random Oracle Model......Page 409
Simulation Methods......Page 410
The Encryption Schemes and Their Security in the Weakened Random Oracle Models......Page 411
The First Variant dFO......Page 412
The Second Variant wFO......Page 413
The Original Fujisaki-Okamoto Conversion......Page 415
OAEP......Page 416
Future Work......Page 417
Introduction......Page 420
Notation......Page 421
Ideals in Number Fields......Page 422
Our Somewhat Homomorphic Scheme......Page 423
Analysis......Page 424
Security Analysis......Page 428
A Fully Homomorphic Scheme......Page 432
Extension to Large Message Space......Page 433
Implementation Results......Page 434
Analysis of the Recrypt Procedure......Page 436
Stage 7......Page 442
Introduction......Page 444
Sanitizable Signatures......Page 447
Security of Sanitizable Signatures......Page 449
Definition......Page 452
Relationships of the Security Notions......Page 454
Group Signatures......Page 455
Construction......Page 456
Security Proof......Page 458
Introduction......Page 462
Definition of Confidential Signature Schemes......Page 464
Confidential Hash Functions......Page 466
Full-Domain Hash Signatures......Page 468
Strongly Confidential Signatures in the ROM......Page 469
Fiat-Shamir Signature Schemes......Page 470
Strongly Confidential Signatures from Randomness Extraction......Page 471
Notions of Confidentiality for Signcryption Schemes......Page 472
The Encrypt-and-Sign Signcryption Scheme......Page 474
Derandomization......Page 476
Public-Key Encryption......Page 478
Pseudo-Random Functions......Page 479
Introduction......Page 480
Technical Overview......Page 483
Identity-Based Multi-/Aggregate Signature Schemes......Page 485
$\\Sigma$-Equivocable Commitments and Structured-Instance Zero-Knowledge......Page 487
RSA-Based Multiplicatively Homomorphic $\\Sigma$-Equivocable Commitment......Page 491
Identity-Based Multisignature Scheme Based on RSA......Page 493
Identity-Based Aggregate Signature Scheme......Page 497
Introduction......Page 499
Related Work......Page 500
Highlights......Page 501
Bases and Trapdoors......Page 502
Discrete Gaussians......Page 503
Statistical Mixing......Page 504
Preimage Sampling......Page 505
More Useful Facts......Page 506
Two-Sided Trapdoors......Page 507
Main Signature Scheme......Page 509
Security Reduction......Page 510
Lattice Parameters......Page 514
Refined Simulation Framework......Page 515