Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan (auth.), Shai Halevi, Tal Rabin (eds.)3540327312, 9783540327318

This book constitutes the refereed proceedings of the Third Theory of Cryptography Conference, TCC 2006, held in New York, NY, USA in March 2006.

The 31 revised full papers presented were carefully reviewed and selected from 91 submissions. The papers are organized in topical sections on zero-knowledge, primitives, assumptions and models, the bounded-retrieval model, privacy, secret sharing and multi-party computation, universally-composible security, one-way functions and friends, and pseudo-random functions and encryption.

---

Table of contents :
Front Matter….Pages –
Concurrent Zero Knowledge Without Complexity Assumptions….Pages 1-20
Interactive Zero-Knowledge with Restricted Random Oracles….Pages 21-40
Non-interactive Zero-Knowledge from Homomorphic Encryption….Pages 41-59
Ring Signatures: Stronger Definitions, and Constructions Without Random Oracles….Pages 60-79
Efficient Blind and Partially Blind Signatures Without Random Oracles….Pages 80-99
Key Exchange Using Passwords and Long Keys….Pages 100-119
Mercurial Commitments: Minimal Assumptions and Efficient Constructions….Pages 120-144
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices….Pages 145-166
On Error Correction in the Exponent….Pages 167-183
On the Relation Between the Ideal Cipher and the Random Oracle Models….Pages 184-206
Intrusion-Resilience Via the Bounded-Storage Model….Pages 207-224
Perfectly Secure Password Protocols in the Bounded Retrieval Model….Pages 225-244
Polylogarithmic Private Approximations and Efficient Matching….Pages 245-264
Calibrating Noise to Sensitivity in Private Data Analysis….Pages 265-284
Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation….Pages 285-304
Efficient Multi-party Computation with Dispute Control….Pages 305-328
Round-Optimal and Efficient Verifiable Secret Sharing….Pages 329-342
Generalized Environmental Security from Number Theoretic Assumptions….Pages 343-359
Games and the Impossibility of Realizable Ideal Functionality….Pages 360-379
Universally Composable Symbolic Analysis of Mutual Authentication and Key-Exchange Protocols….Pages 380-403
Resource Fairness and Composability of Cryptographic Protocols….Pages 404-428
Finding Pessiland….Pages 429-442
Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness….Pages 443-461
On the Complexity of Parallel Hardness Amplification for One-Way Functions….Pages 462-481
On Matroids and Non-ideal Secret Sharing….Pages 482-501
Secure Computation with Partial Message Loss….Pages 502-521
Communication Efficient Secure Linear Algebra….Pages 522-541
Threshold and Proactive Pseudo-Random Permutations….Pages 542-560
PRF Domain Extension Using DAGs….Pages 561-580
Chosen-Ciphertext Security from Tag-Based Encryption….Pages 581-600
Separating Sources for Encryption and Secret Sharing….Pages 601-616
Back Matter….Pages –