Instructor: Tal Malkin, 514 CSB, Office hours: Tuesdays 1:30-3:30pm
TA: Andrew Wan, Office hours: TBA
Time & Place: Thur 4:10-6:30pm, 476 CSB
(note change of location!)
Prerequisites: COMS-4261 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 this semester will focus on black-box complexity of cryptographic primitives . The class will have two parts (not necessarily of equal weight): 1) Black-box reductions, 2) black-box separations. While we will read some classical papers from the previos millennium, our emphasis will be on newer works from the last several years. We will also not necessarily aim at giving an exhaustive treatment of the subject, but rather go in depth into several papers, biased by the interests of the instructor and the students taking the class.
The class will consist of lectures given by students presenting papers they have read , by the instructor, and guest speakers. Students are expected to present papers, read papers, and participate in discussion (see below).
Black-Box Constructions:
Black-Box Separations and lower bounds:
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 Presentation: Every student is required to present one of the papers in class (roughly a one hour presentation) one time throughout the semester. Project presentations (roughly 20 minutes each) will also be required at the end of the semester.
Reading Papers and Class Participation: Before each class a list of papers will be distributed, typically one of which will be presented in the following class. Each student has to choose one of the papers and read it for class, being prepared to discuss it, and be able to describe the results and techniques of the paper. If the student would like to read a different paper that seems appropriate for the lecture's topic, the student may email the instructor, who will approve another paper if deemed appropriate. Alternatively, the student may carefully read the introductions of all papers, and be prepared to discuss the model and results, how they compare / differ from each other, though will not need to know the techniques and the proofs. Each student gets 3 lectures during the semester for which the student need not prepare as above. Students should send their prefernece (which paper they will read, or whether they are taking one of their three free passes) to the TA, and await TA's confirmation (in some cases the TA may ask the student to change their selection, so that every paper is covered by someone).
Homework: There will
be at most two (but likely significantly less) 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 will be posted here, although anything that is related to the foundation of cryptography is likely to be appropriate.
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. Due dates:
More details on the project and possible topics below:
Proposal: The proposal should include the area that you want to investigate, the papers that you plan to read to that end, and your goals for the project. At this stage your goals may be vague and broad, though if you have very specific goals in mind, please include them in the proposal.
The scope (e.g how many papers have been published in the area to date, how many papers you need to read and understand for your project, and in what depth) may vary considerably, though we will try to guide students towards comparable amounts of work to complete the project.
Progress Report: In the second stage you will have to specify your goals much more clearly, typically in the form of a specific research problem you wish to resolve. Outline your planned approach towards satisfying these goals based on the progress you have made by studying the area. Your final project will have to be in-depth research into a well-defined problem (suggesting the problem and making it well defined is part of your job, though you're allowed and encouraged to discuss your ideas with the instructor).
Please notify us of your general area of choice as soon as you can. Several of the suggestions below can support more than one group (working on different subareas), but if several groups consider projects that overlap too much, the first group to request it will get priority.
For all the areas below, contact us for pointers to the important/latest papers in the area.
Final Report: 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.
See here for a list of possible topics.
General Guidelines: In general there are two main goals for a project in this class:
(1) You should acquire a substantial body of knowledge about the topic of your project. This will involve closely and carefully reading literature on your specific project topic (likely to be several papers). You'll demonstrate this aspect of your project in the "background" section(s) of your project report, which should be a clear synthesis and exposition in your own words of what you learned.
(2) You should gain research experience in this area; i.e. make a serious effort to contribute to the state of knowledge on your project topic by (i) identifying an interesting open question or direction for future research related to your project topic; (ii) coming up with an approach to make progress; and (iii) working to carry out your approach. You'll demonstrate this aspect of your project by explaining in detail what you did for (i), (ii) and (iii) in the rest of your project report.
The ratio of (1) to (2) may vary between different projects. There are some projects that might involve relatively less background (but in that case you will be expected to spend more time -- and give more evidence of time well spent) -- on trying to make research progress; and there are other projects where you'll need to acquire more extensive background.