Theory of Cryptography: First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004. Proceedings

Omer Reingold, Luca Trevisan, Salil Vadhan (auth.), Moni Naor (eds.)3540210008, 9783540210009, 9783540246381

This book constitutes the refereed proceedings of the first International Theory of Cryptography Conference, TCC 2004, held in Cambridge, MA, USA in February 2004.

The 28 revised full papers presented were carefully reviewed and selected from 70 submissions. The papers constitute a unique account of original research results on theoretical and foundational topics in cryptography; they deal with the paradigms, approaches, and techniques used to conceptualize, define, and provide solutions to natural cryptographic problems.

---

Table of contents :
Front Matter….Pages –
Notions of Reducibility between Cryptographic Primitives….Pages 1-20
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology….Pages 21-39
On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes….Pages 40-57
Universally Composable Commitments Using Random Oracles….Pages 58-76
Transformation of Digital Signature Schemes into Designated Confirmer Signature Schemes….Pages 77-100
List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument….Pages 101-120
On the Possibility of One-Message Weak Zero-Knowledge….Pages 121-132
Soundness of Formal Encryption in the Presence of Active Adversaries….Pages 133-151
Rerandomizable and Replayable Adaptive Chosen Ciphertext Attack Secure Cryptosystems….Pages 152-170
Alternatives to Non-malleability: Definitions, Constructions, and Applications….Pages 171-190
A Note on Constant-Round Zero-Knowledge Proofs for NP….Pages 191-202
Lower Bounds for Concurrent Self Composition….Pages 203-222
Secret-Key Zero-Knowlegde and Non-interactive Verifiable Exponentiation….Pages 223-237
A Quantitative Approach to Reductions in Secure Computation….Pages 238-257
Algorithmic Tamper-Proof (ATP) Security: Theoretical Foundations for Security against Hardware Tampering….Pages 258-277
Physically Observable Cryptography….Pages 278-296
Efficient and Universally Composable Committed Oblivious Transfer and Applications….Pages 297-316
A Universally Composable Mix-Net….Pages 317-335
A General Composition Theorem for Secure Reactive Systems….Pages 336-354
Unfair Noisy Channels and Oblivious Transfer….Pages 355-373
Computational Collapse of Quantum State with Application to Oblivious Transfer….Pages 374-393
Implementing Oblivious Transfer Using Collection of Dense Trapdoor Permutations….Pages 394-409
Composition of Random Systems: When Two Weak Make One Strong….Pages 410-427
Simpler Session-Key Generation from Short Random Passwords….Pages 428-445
Constant-Round Oblivious Transfer in the Bounded Storage Model….Pages 446-472
Hierarchical Threshold Secret Sharing….Pages 473-490
On Compressing Encrypted Data without the Encryption Key….Pages 491-504
On the Notion of Pseudo-Free Groups….Pages 505-521
Back Matter….Pages –