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:
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.)
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.
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 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).