TCC 2006

March 4-7 2006, Columbia University
New York, NY USA

Final Program

All talks were held in Davis hall, at the entrance level of the Schapiro Center.

Program at-a-glance	Saturday Mar 4	Sunday Mar 5	Monday Mar 6	Tuesday Mar 7
Morning I		Zero-knowledge	SS & MPC (I)	OWFs & friends
Morning II		Primitives	UC-security	SS & MPC (II)
Afternoon I		Assumptions & models	Tutorial: BB separations	PRFs & encryption
Afternoon II		Bounded retrieval model, Privacy	Tutorial: non-BB techniques
Evening	Reception	Rump session

Held at the Carleton Lounge, 1st floor of the Mudd Building, Columbia University.

Concurrent Zero Knowledge without Complexity Assumptions: Daniele Micciancio (UCSD) and Shien Jin Ong (Harvard) and Amit Sahai (UCLA) and Salil Vadhan (Harvard)
Interactive Zero-Knowledge with Restricted Random Oracles: Moti Yung (RSA Labs and Columbia Univ.) and Yunlei Zhao (Fudan Univ.)
Non-Interactive Zero-Knowledge from Homomorphic Encryption: Ivan Damgaard (Univ. of Aarhus) and Nelly Fazio and Antonio Nicolosi (NYU)

Ring Signatures: Stronger Definitions, and Constructions without Random Oracles: Adam Bender and Jonathan Katz and Ruggero Morselli (Univ. of Maryland, College Park)
Efficient Blind and Partially Blind Signatures Without Random Oracles: Tatsuaki Okamoto (NTT Labs)
Key Exchange Using Passwords and Long Keys: Vladimir Kolesnikov and Charles Rackoff (Univ. of Toronto)
Mercurial Commitments: Minimal Assumptions and Efficient Constructions: Dario Catalano (ENS) and Yevgeniy Dodis (NYU) and Ivan Visconti (Univ. of Salerno)

Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices: Chris Peikert (MIT) and Alon Rosen (Harvard)
On Error Correction in the Exponent: Chris Peikert (MIT)
On the Relation Between the Ideal Cipher and the Random Oracle Models: Yevgeniy Dodis and Prashant Puniya (NYU)

Intrusion-Resilience via the Bounded-Storage Model: Stefan Dziembowski (Warsaw University and CNR Pisa)
Perfectly Secure Password Protocols in the Bounded Retrieval Model: Giovanni Di Crescenzo (Telcordia) and Richard Lipton (Georgia Tech.) and Shabsi Walfish (NYU)

Polylogarithmic Private Approximations and Efficient Matching: Piotr Indyk (MIT) and David Woodruff (MIT and Tsinghua Univ.)
Calibrating Noise to Sensitivity in Private Data Analysis: Cynthia Dwork and Frank McSherry (Microsoft) and Kobbi Nissim (Ben-Gurion Univ.) and Adam Smith (Weizmann)

Unconditionally Secure Constant-Rounds Multi-Party Computation for Equality, Comparison, Bits and Exponentiation: Ivan Damgaard and Matthias Fitzi (Univ. of Aarhus) and Eike Kiltz (CWI Amsterdam) and Jesper Buus Nielsen and Tomas Toft (Univ. of Aarhus)
Efficient Multi-Party Computation with Dispute Control: Zuzana Beerliovà and Martin Hirt (ETH Zurich)
Round-Optimal and Efficient Verifiable Secret Sharing: Matthias Fitzi (Aarhus Univ.) and Juan Garay (Bell Labs) and Shyamnath Gollakota (IIT Madras) and C. Pandu Rangan (IIT Madras) and Kannan Srinathan (International Institute of Information Technology, Hyderabad, India)

Generalized Environmental Security from Number Theoretic Assumptions: Tal Malkin (Columbia Univ.) and Ryan Moriarty (UCLA) and Nikolai Yakovenko (Google)
Games and the Impossibility of Realizable Ideal Functionality: Anupam Datta and Ante Derek and John C. Mitchell and Ajith Ramanathan (Stanford Univ.) and Andre Scedrov (Univ. of Pennsylvania)
Universally Composable Symbolic Analysis of Mutual Authentication and Key Exchange Protocols: Ran Canetti (IBM) and Jonathan Herzog (MITRE)
Resource Fairness and Composability of Cryptographic Protocols: Juan Garay (Bell Labs) ,Phillip MacKenzie (Google) and Manoj Prabhakaran (Univ. of Illinois, Urbana-Champaign) and Ke Yang (Google)

Speaker: Omer Reingold

Speaker: Boaz Barak

Finding Pessiland: Hoeteck Wee (UC Berkeley)
Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness: Thomas Holenstein (ETH Zurich)
On the Complexity of Parallel Hardness Amplification for One-Way Functions: Chi-Jen Lu (Academia Sinica)

On Matroids and Non-ideal Secret Sharing: Amos Beimel and Noam Livne (Ben-Gurion Univ.)
Secure Computation with Partial Message Loss: Chiu-Yuen Koo (Univ. of Maryland, College Park)
Communication Efficient Secure Linear Algebra: Kobbi Nissim and Enav Weinreb (Ben-Gurion Univ.)
Threshold and Proactive Pseudo-Random Permutations: Yevgeniy Dodis (NYU) and Aleksandr Yampolskiy (Yale) and Moti Yung (RSA Labs and Columbia Univ.)

PRF Domain Extension Using DAGs: Charanjit S. Jutla (IBM)
Chosen-Ciphertext Security from Tag-Based Encryption: Eike Kiltz (CWI Amsterdam)
Separating Sources for Encryption and Secret Sharing: Yevgeniy Dodis (NYU) and Krzysztof Pietrzak and Bartosz Przydatek (ETH Zurich)