0368-4165-01

Spring 2009

Seminar in Cryptographic Protocols

Mondays 13-15

Instructor:  Ran Canetti

Note:  On Monday, March 15 there will be no meeting. A makeup meeting will take place Friday, March 20, 10-12.

General

Cryptographic protocols are algorithms that allow parties to communicate and collaborate in untrusted environments. They include algorithms that protect against external attackers, as well as algorithms for collaboration with untrusted peers. Besides being fascinating in of themselves, cryptographic protocols provide essential building blocks in the design of secure systems. This seminar will cover some aspects of cryptographic protocols, with the purpose of bringing students up to speed with the state of the art and enabling them to perform independent research.

Required background

An introductory graduate course in cryptography (such as the one given last semester at TAU) is highly recommended. If you haven't taken such a course please contact Ran.

Format

Most lectures will be given by the students. Preparing for the lecture will involve:

• Reading the relevant material.
• Preparing a presentation. (Slides are recommended but not mandatory.)
• Meeting with Ran during the week prior to the presentation to go over the presentation, and fixing it accordingly.
• Presenting in class.
• Preparing a written summary of the presentation to be posted online. (In case of a slides presentation, the slides themselves can double up as the summary.)

Lecture Topics

Below is a list of lecture topics for students to pick from. The lectures to be given and their order will be decided in the first two meetings, based on the makeup of the class and the preferences of the students.

Some lectures are bunched under a single topic. These lectures are best given in sequence, in the specified order. Some ordering between the topic is also best kept. Otherwise lectures can be presented at any order. In any case, each bullet corresponds to a lecture.

In much of the list below only the original papers are mentioned. Often the covered material has better or alternative descriptions in later papers. There may also be presentation materials available online. You are encouraged to use all of these to improve your understanding and your presentation.

Composition and round complexity of Zero-Knowledge protocols

• On the Composition of Zero-Knowledge Proof Systems
  Oded Goldreich, Hugo Krawczyk
  SIAM Journal on Computing
• How to Construct Constant-Round Zero-Knowledge Proof Systems for NP
  O. Goldreich and A. Kahan,

A note on constant-round zero-knowledge proofs for NP
Alon Rosen
TCC 2004

• On the Concurrent Composition of Zero-Knowledge Proofs
  Ransom Richardson, Joe Kilian
  EUROCRYPT 1999: 415-431

On Constant-Round Concurrent Zero Knowledge.
R. Pass and M. Venkitasubramaniam
TCC 2008

• How to Go Beyond the Black-Box Simulation Barrier
  Boaz Barak
  FOCS 2001 106-115

Non-Interactive Zero Knowledge and CCA-secure encryption

• Multiple Non-Interactive Zero Knowledge Proofs Under General Assumptions.
  Uriel Feige, Dror Lapidot, Adi Shamir
  SIAM J. Comput. 29(1): 1-28 (1999)IZK: FLS
• Robust Non-interactive Zero Knowledge.
  Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai
  CRYPTO 2001: 566-598

Y. Lindell. A Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions. In the Journal of Cryptology, 19(3):359-377, 2006.

Identity-based and CCA-secure encryption

• Identity based encryption from the Weil pairing
  D. Boneh and M. Franklin
  SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003.

Chosen-Ciphertext Security from Identity-Based Encryption.
D. Boneh, R. Canetti, S. Halevi, and J. Katz.
SIAM J. Comput., 36(5): 1301-1328 (2007)

Non-malleable commitments

• Concurrent Non-malleable Commitments from One-way Functions
  H. Lin, R. Pass and M. Venkitasubramaniam
  TCC 2008

Multi-party computation and Universally Composable security

• Universally Composable Security: A New Paradigm for Cryptographic Protocols
  Ran Canetti
  Cryptology ePrint Archive: Report 2000/067
• Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation
  Michael Ben-Or Shafi Goldwasser Avi Wigderson
  STOC 1988

Simplified VSS and Fact-Track Multi-party Computations with Applications to Threshold Cryptography.
Rosario Gennaro, Michael O. Rabin, Tal Rabin:
PODC 1998: 101-111

• Universally Composable Commitments.
  R. Canetti and M. Fischlin. Crypto, 2001. Long version at eprint.iacr.org/2001/055.
• Universally composable two-party and multi-party secure computation.
  R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai.
  34th STOC, 2002. Longer version at eprint.iacr.org/2002/140.
• Universally Composable Security with Pre-Existing Setup.
  R. Canetti, Y. Dodis, R. Pass and S. Walfish.
  TCC 2007. Long version at eprint.iacr.org/2006/432.
• Universally Composable Symbolic Analysis of Mutual Authentication and Key-Exchange Protocols.
  R. Canetti and J. Herzog.
  TCC 2006: 380-403. Long version at eprint.iacr.org/2004/334.

Pseudorandom generators from one-way functions

• Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness
  Thomas Holenstein
  TCC 2006

Program Obfuscation

• On the (Im)possibility of Obfuscating Programs
  Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan and Ke Yang
  Crypto 2001
  http://www.math.ias.edu/~boaz/Papers/obfuscate.ps
• Towards realizing random oracles: Hash functions that hide all partial information.
  R. Canetti.
  Crypto, 1997. Longer version available at eprint.iacr.org/1997/007 .

Schedule of talks and presentation materials