Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings

Front Matter....Pages -
Input Locality and Hardness Amplification....Pages 1-18
General Hardness Amplification of Predicates and Puzzles....Pages 19-36
Security Amplification for the Cascade of Arbitrarily Weak PRPs: Tight Bounds via the Interactive Hardcore Lemma....Pages 37-54
Dense Model Theorems and Their Applications....Pages 55-57
Parallel Repetition for Leakage Resilience Amplification Revisited....Pages 58-69
Achieving Leakage Resilience through Dual System Encryption....Pages 70-88
Signatures Resilient to Continual Leakage on Memory and Computation....Pages 89-106
After-the-Fact Leakage in Public-Key Encryption....Pages 107-124
One-Time Computable Self-erasing Functions....Pages 125-143
Perfectly Secure Oblivious RAM without Random Oracles....Pages 144-163
Unconditional and Composable Security Using a Single Stateful Tamper-Proof Hardware Token....Pages 164-181
Correlated-Input Secure Hash Functions....Pages 182-200
Black-Box Circular-Secure Encryption beyond Affine Functions....Pages 201-218
Homomorphic Encryption: From Private-Key to Public-Key....Pages 219-234
Identity-Based Encryption Secure against Selective Opening Attack....Pages 235-252
Functional Encryption: Definitions and Challenges....Pages 253-273
Concurrent Non-Malleable Zero Knowledge with Adaptive Inputs....Pages 274-292
Round-Optimal Password-Based Authenticated Key Exchange....Pages 293-310
Bringing People of Different Beliefs Together to Do UC....Pages 311-328
Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer....Pages 329-346
Practical Adaptive Oblivious Transfer from Simple Assumptions....Pages 347-363
Completeness Theorems with Constructive Proofs for Finite Deterministic 2-Party Functions....Pages 364-381
A Zero-One Law for Secure Multi-party Computation with Ternary Outputs....Pages 382-399
PCPs and the Hardness of Generating Private Synthetic Data....Pages 400-416
Limits of Computational Differential Privacy in the Client/Server Setting....Pages 417-431
Towards Privacy for Social Networks: A Zero-Knowledge Based Definition of Privacy....Pages 432-449
On the Black-Box Complexity of Optimally-Fair Coin Tossing....Pages 450-467
Tight Bounds for Classical and Quantum Coin Flipping....Pages 468-485
Exploring the Limits of Common Coins Using Frontier Analysis of Protocols....Pages 486-503
Limits on the Stretch of Non-adaptive Constructions of Pseudo-Random Generators....Pages 504-521
On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators....Pages 522-539
Concurrent Security and Non-malleability....Pages 540-540
(Nearly) Round-Optimal Black-Box Constructions of Commitments Secure against Selective Opening Attacks....Pages 541-558
Limits on the Power of Zero-Knowledge Proofs in Cryptographic Constructions....Pages 559-578
Towards Non-Black-Box Lower Bounds in Cryptography....Pages 579-596
On Black-Box Separations among Injective One-Way Functions....Pages 597-614
Impossibility of Blind Signatures from One-Way Permutations....Pages 615-629
Back Matter....Pages -