Theory of Cryptography: Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008. Proceedings

Front Matter....Pages -
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency....Pages 1-18
On Seed-Incompressible Functions....Pages 19-36
Asymptotically Efficient Lattice-Based Digital Signatures....Pages 37-54
Basing Weak Public-Key Cryptography on Strong One-Way Functions....Pages 55-72
Which Languages Have 4-Round Zero-Knowledge Proofs?....Pages 73-88
How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge....Pages 89-106
General Properties of Quantum Zero-Knowledge Proofs....Pages 107-124
The Layered Games Framework for Specifications and Analysis of Security Protocols....Pages 125-141
Universally Composable Multi-party Computation with an Unreliable Common Reference String....Pages 142-154
Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries....Pages 155-175
Fast Private Norm Estimation and Heavy Hitters....Pages 176-193
Matroids Can Be Far from Ideal Secret Sharing....Pages 194-212
Perfectly-Secure MPC with Linear Communication Complexity....Pages 213-230
MPC vs. SFE: Perfect Security in a Unified Corruption Model....Pages 231-250
Bridging Game Theory and Cryptography: Recent Results and Future Directions....Pages 251-272
Verifiably Secure Devices....Pages 273-301
Lower Bounds on Implementing Robust and Resilient Mediators....Pages 302-319
Cryptography and Game Theory: Designing Protocols for Exchanging Information....Pages 320-339
Equivocal Blind Signatures and Adaptive UC-Security....Pages 340-355
P-signatures and Noninteractive Anonymous Credentials....Pages 356-374
Multi-property Preserving Combiners for Hash Functions....Pages 375-392
OT-Combiners via Secure Computation....Pages 393-411
Semi-honest to Malicious Oblivious Transfer—The Black-Box Way....Pages 412-426
Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One....Pages 427-444
A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval....Pages 445-464
Randomness Extraction Via δ -Biased Masking in the Presence of a Quantum Attacker....Pages 465-481
An Equivalence Between Zero Knowledge and Commitments....Pages 482-500
Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model....Pages 501-534
The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization....Pages 535-552
On Constant-Round Concurrent Zero-Knowledge....Pages 553-570
Concurrent Non-malleable Commitments from Any One-Way Function....Pages 571-588
Faster and Shorter Password-Authenticated Key Exchange....Pages 589-606
Saving Private Randomness in One-Way Functions and Pseudorandom Generators....Pages 607-625
Degradation and Amplification of Computational Hardness....Pages 626-643
Back Matter....Pages -