Topics in Cryptography

Computer Science 787
Cornell University
Spring 2007

 

Instructor: Rafael Pass
Time: Tuesdays 10:10-12:00 am.
Place: 315 Upson Hall.
http://www.cs.cornell.edu/courses/cs787/2007sp/

Overview

CS 787 is a seminar-style course in which students will read and present papers on current research in Cryptography. Potential topics include zero knowledge, concurrency and protocol security, database privacy, connections between symbolic and computational security analysis, and cryptographic game theory.

The course will build on material covered in CS 687, but 687 is not a formal prerequisite for 787.

Potential Topics

Zero Knowledge

Precise Zero Knowledge

Non Black-box Simulation

Concurrency and Protocol Security

Non-malleable Cryptography

Concurrent Zero Knowledge

Universally Composable Security

Relaxed notions of security

Database Privacy and Security

Definitions of Database Privacy

Zero-Knowledge Sets

Private Information Retrieval

Evaluating functions on Encrypted Data

Connections between Symbolic and Computational Security Analysis

Soundness Theorems for Symbolic Security Analysis

Concurrency and Symbolic Analysis

Cryptographic Game Theory

Achieving Better Equilibria using Cryptographic Protocols

Game Theoretic Analysis of Cryptographic Protocols

Potential papers for presentations

Zero Knowledge

·        Silvio Micali and Rafael Pass. Local Zero Knowledge. STOC 2006.

·        Rafael Pass. A Precise Computational Approach to Knowledge.

·        Boaz Barak, How to go Beyond the Black-box Simulation Barrier, FOCS 2002.

Concurrency and Protocol Security

·        Dolev, Dwork and Naor. Non-malleable Cryptography, SIAM Journal of Computing, 2000.

·        Concurrent Zero Knowledge: Richarson, Kilian, Petrank, Prabhakaran, Rosen, Sahai [RK00], [KP01] [PRS03]  

·        Pass. Bounded-Concurrent Secure Multi-party Computation, STOC 2004.

·        Pass and Rosen. New and Improved Constructions of Non-Mallable Cryptographic Protocols, STOC 2005.

·        Pass and Rosen. Concurrent Non Mallable Commitments, FOCS 2005.

·        Barak, Prabhakaran and Sahai. Concurrent Non-malleable Zero Knowledge, FOCS 2006.

·        Pass, Simulation in Quasi-polynomial Time and its application to protocol composition, EUROCRYPT 2003.

·        Micali, Pass, and Rosen. Input-Indistinguishable Computation, FOCS 2006.

Universally Composable Security

·        Ran Canetti, Universally Composable Security, FOCS 2001.

·        Dodis, Canetti, Pass and Walfish. Universally Composable Security with Global Set-up, TCC 2007.

Database Privacy and Security

·        Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith, Calibrating Noise to Sensitivity in Private Data Analysis,
TCC 2006.

·        Cynthia Dwork, Differential Privacy, ICALP 2006.

·        Kilian, Micali, and Rabin, Zero-Knowledge Sets, FOCS 2003.

·        Kushilevitz and Ostrovsky, Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval, FOCS 1997.

·        Cachin, Micali and Stadler, Computationally private information retrieval with polylogarithmic communication. EUROCRYPT 1999.

·        Micali, Rabin and Kilian, Zero-Knowledge Sets, FOCS 2003.

Connections between Symbolic and Computational Security Analysis

·        Dolev, Yao, On the security of public key protocols, IEEE TIT 1983.

·        Abadi, Rogaway: Reconciling Two Views of Cryptography. J. Cryptology 2002.

·        Micciancio, Warinschi: Soundness of formal encryption in the presence of active adversaries. TCC 2004.

·        Canetti and Herzog, Universally Composable Symbolic Analysis of Cryptographic Protocols (The case of encryption-based mutual authentication and key exchange)

·        See also Daniele Micciancio's course

Cryptographic Game Theory

·        Halpern and Teague, Rational secret sharing and multiparty computation, STOC 2004.

·        Izmalkov, Lepinski and Micali. Rational Secure Function Evaluation and Ideal Mechanism Design.  FOCS 2005.

·        Abraham, Dolev, Gonen and Halpern, Distributed Computing Meets Game Theory:
Robust Mechanisms for Rational Secret Sharing and Multiparty Computation
, PODC 2005.

 

Schedule

January 23 (Rafael)

·        Review of Interactive Proofs and Zero Knowledge

·        Precise Zero Knowledge.

January 30 (Rafael)

·        Precise Proofs of Knowledge

·        Witness Indistinguishability.

February 6 (Muthu)

·        Boaz Barak, How to go Beyond the Black-box Simulation Barrier, FOCS 2002.

February 13 (Muthu)

·        Pass. Bounded-Concurrent Secure Multi-party Computation, STOC 2004.

·        Pass and Rosen. New and Improved Constructions of Non-Mallable Cryptographic Protocols, STOC 2005.

February 20 (Rachel)

·        Dolev, Dwork and Naor. Non-malleable Cryptography, SIAM Journal of Computing, 2000.

February 27 (Dustin)

·        Concurrent Zero Knowledge: Richarson, Kilian, Petrank, Prabhakaran, Rosen, Sahai [RK00], [KP01] [PRS03]  

March 6 (Ariel)

·        Kushilevitz and Ostrovsky, Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval, FOCS 1997.

·        Cachin, Micali and Stadler, Computationally private information retrieval with polylogarithmic communication. EUROCRYPT 1999.

March 13 (Michael G)

·        Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith, Calibrating Noise to Sensitivity in Private Data Analysis,
TCC 2006.

·        Cynthia Dwork, Differential Privacy, ICALP 2006.

March 20 (Spring Break)

March 27 (Tudor)

·        Dolev, Yao, On the security of public key protocols, IEEE TIT 1983.

·        Abadi, Rogaway: Reconciling Two Views of Cryptography. J. Cryptology 2002.

April 3 (Michael C)

·        Micciancio, Warinschi: Soundness of formal encryption in the presence of active adversaries. TCC 2004.

·        Canetti and Herzog, Universally Composable Symbolic Analysis of Cryptographic Protocols (The case of encryption-based mutual authentication and key exchange)

April 10 (Tom)

April 17 (Thanh)

April 24 (Vikram)

May 3