0368416501
Spring
2009
Seminar in Cryptographic Protocols
Mondays 1315
Instructor: Ran Canetti
Note: On Monday, March 15
there will be no meeting. A makeup meeting will take place Friday, March 20,
1012.
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 ZeroKnowledge protocols
A
note on constantround zeroknowledge proofs for NP
Alon Rosen
TCC 2004
 On
the Concurrent Composition of ZeroKnowledge Proofs
Ransom Richardson, Joe Kilian
EUROCRYPT 1999: 415431
On ConstantRound Concurrent Zero Knowledge.
R. Pass and M. Venkitasubramaniam
TCC 2008
 How
to Go Beyond the BlackBox Simulation Barrier
Boaz Barak
FOCS 2001 106115
NonInteractive Zero Knowledge and CCAsecure encryption
 Multiple
NonInteractive Zero Knowledge Proofs Under General Assumptions.
Uriel Feige, Dror Lapidot, Adi Shamir
SIAM J. Comput. 29(1): 128 (1999)IZK: FLS
 Robust
Noninteractive Zero Knowledge.
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe
Persiano, Amit Sahai
CRYPTO 2001: 566598
Y. Lindell. A Simpler Construction of
CCA2Secure PublicKey Encryption Under General Assumptions. In the Journal
of Cryptology, 19(3):359377, 2006.
Identitybased and CCAsecure encryption
 Identity
based encryption from the Weil pairing
D. Boneh and M. Franklin
SIAM J. of Computing, Vol. 32, No. 3, pp. 586615, 2003.
ChosenCiphertext
Security from IdentityBased Encryption.
D. Boneh, R. Canetti, S. Halevi, and J. Katz.
SIAM J. Comput., 36(5): 13011328 (2007)
Nonmalleable commitments
Multiparty computation and Universally Composable security
Simplified VSS and FactTrack Multiparty
Computations with Applications to Threshold Cryptography.
Rosario Gennaro, Michael O. Rabin, Tal Rabin:
PODC 1998: 101111
 Universally
Composable Commitments.
R. Canetti and M. Fischlin. Crypto, 2001. Long version at eprint.iacr.org/2001/055.
 Universally
composable twoparty and multiparty 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 PreExisting 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 KeyExchange
Protocols.
R. Canetti and J. Herzog.
TCC 2006: 380403. Long version at eprint.iacr.org/2004/334.
Pseudorandom generators from oneway functions
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
No.

Date

Topic

Speaker

Materials

1

2.3.

Review of ZeroKnowledge (ZK), Triviality of
3round BlackBox ZK: The GoldreichKrawczyk bound

Ran Canetti


2

9.3.

ZK protocols for NP with constant number of rounds : The
GoldreichKahan and Rosen protocols

Dima
Sotnikov

notes
slides

3

23.3.

Concurrent
ZK: Lower bounds and protocols

Omer
Paneth

slides

4

30.3.

NonBlackBox
ZK: The Barak protocol

Asaf
Porat

slides


.

Pesach Vacation



5

20.4.

NonInteractive
ZK (NIZK): The FeigeLapidotShamir protocol

Ben
Riva

slides

6

27.4.

Robust
NIZK and CCAsecure encryption

Roy
Kasher

slides

7

4.5.

IdentityBased
Encryption and CCAsecure encryption

Ilia
Lotosh

slides

8

11.5.

NonMalleable
Commitments: The DolevDworkNaor and
LinPassVenkitasubramaniam
protocols

Rita
Vald

slides

9

15.5.

Universally
Composable (UC) Security: The basic framework and composition theorem

Ran
Canetti

slides

10

25.5.

UC
secure computation with honest majority: The BenOrGoldwasserWigderson
protocol

MichaelHakimi

slides

11

1.6.

UC
commitments and general secure computation

Daniel
Shahaf

slides

12

8.6.

Program
obfuscation: Practical background, definitions, general impossibility

Omer
Singer

slides

13

15.6.

Perfect
One Way hashing and obfuscation of point functions

Nir
Bitansky

slides








