Theory of Cryptography: 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings

Tal Moran, Moni Naor, Gil Segev (auth.), Omer Reingold (eds.)3642004563, 9783642004568

This book constitutes the refereed proceedings of the Sixth Theory of Cryptography Conference, TCC 2009, held in San Francisco, CA, USA, March 15-17, 2009.

The 33 revised full papers presented together with two invited talks were carefully reviewed and selected from 109 submissions. The papers are organized in 10 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 –
An Optimally Fair Coin Toss….Pages 1-18
Complete Fairness in Multi-party Computation without an Honest Majority….Pages 19-35
Fairness with an Honest Minority and a Rational Majority….Pages 36-53
Purely Rational Secret Sharing (Extended Abstract)….Pages 54-71
Some Recent Progress in Lattice-Based Cryptography….Pages 72-72
Non-malleable Obfuscation….Pages 73-90
Simulation-Based Concurrent Non-malleable Commitments and Decommitments….Pages 91-108
Proofs of Retrievability via Hardness Amplification….Pages 109-127
Security Amplification for Interactive Cryptographic Primitives….Pages 128-145
Composability and On-Line Deniability of Authentication….Pages 146-162
Authenticated Adversarial Routing….Pages 163-182
Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer….Pages 183-201
On the (Im)Possibility of Key Dependent Encryption….Pages 202-219
On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols….Pages 220-237
Secure Computability of Functions in the IT Setting with Dishonest Majority and Applications to Long-Term Security….Pages 238-255
Complexity of Multi-party Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation….Pages 256-273
Realistic Failures in Secure Multi-party Computation….Pages 274-293
Secure Arithmetic Computation with No Honest Majority….Pages 294-314
Universally Composable Multiparty Computation with Partially Isolated Parties….Pages 315-331
Oblivious Transfer from Weak Noisy Channels….Pages 332-349
Composing Quantum Protocols in a Classical Environment….Pages 350-367
LEGO for Two-Party Secure Computation….Pages 368-386
Simple, Black-Box Constructions of Adaptively Secure Protocols….Pages 387-402
Black-Box Constructions of Two-Party Protocols from One-Way Functions….Pages 403-418
Chosen-Ciphertext Security via Correlated Products….Pages 419-436
Hierarchical Identity Based Encryption with Polynomially Many Levels….Pages 437-456
Predicate Privacy in Encryption Systems….Pages 457-473
Simultaneous Hardcore Bits and Cryptography against Memory Attacks….Pages 474-495
The Differential Privacy Frontier (Extended Abstract)….Pages 496-502
How Efficient Can Memory Checking Be?….Pages 503-520
Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms….Pages 521-538
Secret Sharing and Non-Shannon Information Inequalities….Pages 539-557
Weak Verifiable Random Functions….Pages 558-576
Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection….Pages 577-594
Towards a Theory of Extractable Functions….Pages 595-613
Back Matter….Pages –