This book constitutes the thoroughly refereed proceedings of the 8th Theory of Cryptography Conference, TCC 2011, held in Providence, Rhode Island, USA, in March 2011.
The 35 revised full papers are presented together with 2 invited talks and were carefully reviewed and selected from 108 submissions. The papers are organized in topical sections on hardness amplification, leakage resilience, tamper resilience, encryption, composable security, secure computation, privacy, coin tossing and pseudorandomness, black-box constructions and separations, and black box separations.
Author(s): Andrej Bogdanov, Alon Rosen (auth.), Yuval Ishai (eds.)
Series: Lecture Notes in Computer Science 6597
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 631
Tags: Data Encryption; Computer Communication Networks; Systems and Data Security; Coding and Information Theory; Math Applications in Computer Science; Algorithm Analysis and Problem Complexity
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 -
