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

Paul Valiant (auth.), Ran Canetti (eds.)354078523X, 9783540785231

This book constitutes the refereed proceedings of the Fifth Theory of Cryptography Conference, TCC 2008, held in New York, USA, March 19-21, 2008.

The 33 revised full papers presented were carefully reviewed and selected from 81 submissions. The papers are organized in 16 sessions dealing with the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems.

---

Table of contents :
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 –