Cryptographic Protocols

CSc 85030–Fall 2015

 CUNY Graduate Center
Computer Science Department

Instructor: Prof. Nelly Fazio
Lectures: Tuesdays, 2:00–4:00pm (Room 3308)
Office hours: By appointment (Room 4439)
Email: nfazio AT gc DOT cuny DOT edu [Put CSc85030 in Subject line]

[ Course Description | List of Topics | Textbook | Grading | Weekly Schedule ]

Course Description

This graduate-level course covers the theory of cryptographic protocols and some of its applications. Emphasis will be placed on the methodology of provable security, whereby the security goals of a given communication and/or computational task are abstracted into an adversarial model amenable to mathematical treatment. No prior knowledge of cryptography is required. However, general ease with algorithms and elementary probability theory, and maturity with mathematical proofs will be assumed.

Textbook

There is no required textbook. Assigned readings will be taken from the research literature, and will be posted under the weekly schedule list at least one week in advance of their due date. Students are required to read the relevant research papers before each class, and to participate in classroom discussion. One-page summaries of each assigned reading will be due the day after they are discussed in class. (PDF or plain text only!)

The final exam will consists of student presentations on a topic agreed with the instructor. Students will work on their term project individually. Each student will prepare a 30-minute presentation, along with 10-page report on the chosen topic. The report will be due one week before the exam. Students are strongly encouraged to prepare their term reports in LaTeX.

A useful reference:

List of Topics

Topics to be covered include: Commitment schemes, Coin-tossing, Zero-knowledge, Oblivious transfer, Secret sharing, Secure function evaluation/multi-party computation, Password-based key exchange, Identification protocols.

Grading

Weekly Schedule (tentative)

Lecture Date Topic Readings
1 Sep 1 Introduction. Sample cryptographic protocols. Review of fundamental cryptographic primitives. KL Chap. 3, 9
2 Sep 8 Review of fundamental cryptographic primitives (con't). KL Chap. 4, 10, 12, 13
Sep 15 No Class!  
Sep 22 No Class!  
3 Sep 25 Some techniques and methodologies for arguments of provable security. The case of ElGamal Encryption Scheme. Sho06.pdf
4 Sep 29 Cramer-Shoup Encryption Scheme. CrSh98.pdf
5 Oct 6 More on Cramer-Shoup Encryption Scheme.
CrSh98.pdf
6 Oct 13 Commitment schemes. Hiding and binding properties. Constructions from RSA. DaNi08
7 Oct 20 Bit Commitment using pseudo-randomness. Nao89
8 Oct 27 Intro to Zero-Knowledge. Interactive proofs/arguments, perfect/statistical/computational zero-knowledge. DaNi08
9 Nov 3 More on zero-knowledge. Rewinding and cut-and-choose techniques. DaNi08
10 Nov 10 Zero-knowledge protocols for all NP languages. Zero-knowledge beyond NP: Graph Non-Isomorphism. Dam08
11 Nov 17 Introduction to multi-party computation. Secret sharing.
Security models for multi-party computation and secure function evaluation.		 Sha79, Dam06
12 Nov 24 Secure evaluation of arithmetic circuits: The protocol and its security analysis. CDN09
13 Dec 1 Proofs of knowledge and knowledge extraction: The Schnorr protocol. Dam10
14 Dec 8 Secure evaluation of boolean circuits: Oblivious transfer and Yao's garbled circuit protocol. LiPi08
Dec 15 Final Report & Presentations

Copyright © Nelly Fazio