COMS E6998-2:  Advanced Cryptography

Spring 2004: Secure Multiparty Computation

Class Information || Syllabus || Class Requirements || Readings || Projects || Bulletin Board


4/20 - Office Hours: The TA's office hours for tomorrow, 4/21, are cancelled.

4/14 - There's a new due date for the project. If your project was originally due on April 20, it is now due on April 25 (23:59 EST). If your project was originally due on April 27, it is now due on May 2 (23:59 EST). Note that the paper must be in either ps or pdf format. The best system for typesetting your paper is LaTeX, and it is easy to convert to LaTeX files into ps or pdf files.

3/31 - If your progress report was submitted on time, your project will be due on 4/27. Otherwise, the progress report can be submitted by 4/7, and the project will be due on 4/20.

3/24 - Here are some web sites that may help with your research. Note that STOC and FOCS papers are only accesible through Columbia's network.

3/2 - Office Hours: today, Prof. Malkin's office hours are as usual (3-5pm). Next week, Tuesday March 9th, Prof. Malkin's office hours will be from 5-7pm. (The week after that there will be no office hours due to spring break).

3/1 - Details on the project are up!

2/25 - Reading Assignment: Oded Goldreich's Zero-Knowledge Twenty Years After Its Invention.

2/25 - Project suggestions will be up soon.

Project Due Dates:

2/16 - Office hours change for this week only: Prof. Malkin's office hours for Tuesday, February 17, will be from 1:45-3:45.

2/4 - Reading Assignment: Oded Goldreich's The Foundations of Cryptography Chapters 4.1-4.4. Click here for a preliminary postscript version.

2/4 - We now have a bulletin board for the class -- hope we get some interesting discussions despite the lack of frequent homework!

A few interesting talks on recent research in secure multiparty computation are coming up:

For more information about the last two talks, and to add yourself to the mailing list, check the Columbia Theory Seminar webpage.

General Information

This is a three-credit advanced graduate level course. The course serves as a theory elective for the PhD program in computer science. It also serves as an elective for MS students in the Foundations of Computer Science Track and the Computer Security Track.  The class will focus around a different topic, possibly with a different format, every time it is taught. The class can be repeated for credit.  Auditing the class requires instructor approval. CVN students should contact the instructor before registering.

Instructor: Tal Malkin, 514 CSB, Office hours: Tuesdays 3-5pm starting Tue 2/24/04

TA: Homin K Lee, Office hours: Wednesdays 3-4pm (in the CS Help Room), starting Wed 2/18/04

Time & Place: Wed 4:10-6:30pm, Mudd 1127 (note change of location!)

Prerequisites: COMS-4995 Introduction to Cryptography or equivalent with instructor approval.  It is assumed that all students already have good knowledge of basic notions from cryptography and complexity theory (e.g., pseudorandom generators, pseudorandom functions, private/public key encryption, digital signatures, message authentication codes, one-way functions, trapdoor functions, etc.)

Class Description and Syllabus

The class will focus on the study of secure multiparty computation. Informally, these are general protocols among two or more parties, where all parties want to maintain the privacy of their inputs and prevent other parties from disrupting the correct execution of the computation  (for example, think of voting protocols, auctions, computing the average salary of the participants, playing black jack, etc.).  Indeed, secure computation can be viewed as encompassing, in some sense, every other cryptographic task as a special case, and general plausibility results (protocols for secure computation of any functionality) are among the most important results in cryptography.  

Many issues are involved in studying secure computation, from definitional aspects to protocol design, and the solutions depend on questions such as: What attacks can the adversary mount? Is there only a single execution of the protocol, or do we allow concurrent "Internet-style" executions of many protocols?  Is there a broadcast channel available?  etc.  Useful tools needed to implement secure protocols include zero knowledge proof systems (an area that could easily span an entire semester - though we'll restrain ourselves to only a fraction), secret sharing, commitment schemes, oblivious transfer, and others.  We will cover some of the major results in the area, and continue to further advanced topics, depending on the interests and background of the audience.

The class format will be largely interactive lectures by the instructor, with expected participation and discussion by students. A smaller part of the course will be delivered by guest speakers and by students in the class presenting papers and projects. The emphasis in the class will be on a theoretically sound approach, rigorous definitions and provably secure protocols.   

Tentative List of Topics

The following is a tentative list of topics, including several advanced optional topics.  Only a subset of these will be covered, and possibly other topics not mentioned here, as time permits and depending on the interests and background of the participants. 


There is no required textbook for the class.  Pointers to (or hard copies of) required and recommended readings (research papers or book chapters) will be distributed to students during the semester and collected on a class web page that will be linked here.  

Class Requirements

Class participation:  Students are expected to come prepared and participate in lectures.  CVN students who cannot attend class will be required to send discussion topics (as well as encouraged to send questions) over email, and should contact the instructor for more specific details.

Homework:  There will be zero, one (most likely), or two homework assignments to be turned in throughout the semester.   

Project:  Students should complete a research project on a cryptographic topic of your choice, subject to instructor approval. You are encouraged to work on the research project in groups of two, but individual or three-student projects are allowed, if called for by the project topic.  Suggested topics include topics mentioned in the list above (e.g., privacy preserving data mining, private information retrieval, secure computation of approximations, voting schemes, completeness results in secure computation, credential systems, exposure resilient cryptography, algorithmic tamper proof security), or other cryptographic areas  (e.g., chosen ciphertext secure public key encryption, identity based encryption, steganography, quantum cryptography).  More detailed suggestions will be posted here.
The first stage of the project will consist of literature study of the selected area.  Based on that, you will then select a research problem or direction which you expect to make new progress in by the end of the semester.  I will be available to help you with both these stages, and expect to be updated about your progress throughout the semester.  You will be required to submit a short project proposal (before first stage) and a short midterm progress report (before the second stage), as well as a final report. Exact deadlines will be posted here.
Your final report will consist of a paper describing your new research result (including motivation and background), or, in case no new result was obtained, a literature survey, open problems, and description of why and where you got stuck, and what you learned from these obstacles, including a suggestion for the next research step.   

Class Presentation:  Every student is required to give a class presentation (roughly 20 minutes).  The presentation will be either of your final project, or of a research paper, determined in consultation with the instructor.  Most of the student presentations will happen in the later part of the course (in particular, projects will be presented in the last two classes).