This graduate-level course covers the theory of cryptographic protocols and
some of its applications. Emphasis will be placed on the methodology of prov-
able security, whereby the security goals of a given communication and/or
computational task are abstracted into an adversarial model amenable to
Topics to be covered include: Commitment schemes, Coin-tossing, Zero-
knowledge, Oblivious transfer, Secret sharing, Secure function evaluation/multi-
party computation, Veriable computation and Cloud computing.
No prior knowledge of cryptography is required. However, general ease
with algorithms and elementary probability theory, and maturity with math-
ematical proofs will be assumed.
Evaluate a given security protocol against the state of the art.
Explain, illustrate, and contrast advanced cryptographic concepts, both
verbally and in writing, at a level suitable for either a technical or non-
Locate salient or innovative ideas in a technical paper, and summarize
ndings in reports.
Assess the work of others against given guidelines and requirements,
e.g., in the context of a peer review.
Research and document a topic as part of a class project.
Week 1-2 Introduction. Sample cryptographic protocols. Review of fundamental
Week 3 Some techniques and methodologies for arguments of provable security.
The case of ElGamal Encryption Scheme.
Week 4 Cramer-Shoup Encryption Scheme.
Week 5 Commitment schemes. Hiding and binding properties.correctness of programs.
- Week 6 Commitments schemes. Constructions from RSA.
Week 7 Bit Commitment using pseudo-randomness.
- Week 8 Intro to Zero-Knowledge. Interactive proofs/arguments, perfect/statistical/computational zero-knowledge.
Week 9 More on zero-knowledge. Rewinding and cut-and-choose techniques.
- Week 10 Zero-knowledge protocols for all NP languages. Zero-knowledge beyond NP: Graph Non-Isomorphism.
Week 11 Introduction to multi-party computation. Secret sharing. Security models for multi-party computation and secure function evaluation.
- Week 12 Secure evaluation of arithmetic circuits: The protocol and its security analysis.
Week 13 Proofs of knowledge and knowledge extraction: The Schnorr protocol.
- Week 14 Secure evaluation of boolean circuits: Oblivious transfer and Yao's garbled circuit protocol.