COMS E6261: Advanced Cryptography

Spring 2024: Cryptography ∩ TFNP

New! Progress report due date has been extended -- it is now due on Friday April 12

Project Information

Project Requirements and Milestones Students should complete a research project on a cryptographic topic of their choice, subject to instructor approval (see more about topic selection below). Students may work on their research project individually or in a group. If you would like to collaborate with others outside the class, e.g., other professors or fellow students, you may do so, provided that all your collaborators are mentioned in your report and approve this, and that you are not getting double credit for the same work (and of course, we will hold you accountable for your project).

The first stage of the project will consist of literature study of the selected area, and tentative identification of the problem you would like to address (what you'd hope to achieve). Over the semester you will refine this goal, state a concrete research result you hope to obtain, and work towards it. Identifying a problem to pursue, making it well-defined, and coming up with a plan towards addressing it, is your responsibility. However, you are allowed and encouraged to discuss your ideas with (and receive feedback from) the instructors, TA, and fellow students, at all stages (you may also incorporate others' ideas in your project, as long as they are ok with it, you give them proper credit, and the project also reflects appropriate effort by each member of the group).

Note that the research problem you choose to work on does not have to be an open problem that is stated in some paper or identified by an expert in the field -- it can be a problem of your own invention. It can also be an extension of a known result to new, unknown settings. The final report does not need to be a publishable result, nor must it conclude in successful resolution. One of the main goals of this course is to invoke interesting research ideas, and give you a taste of the research process. We encourage interesting projects that might end up unsuccessful (as long as all attempts are well documented and make sense overall), over a successful resolution of a trivial problem.

While we expect that most projects will not end with a publishable result, given the nature of research and the time alotted, some might (examples of papers that originated from class projects in previous iterations include the following papers: PODS 12, ICALP 19, ITC 21, ITC 22). We suggest that you approach this optimistically: propose a concrete research problem, and attack it with the goal of solving it. In your final report, describe either your new result, or your attempt, where you reached, and what would be the next steps you would try if given more time.

Specific milestones and requirements are as follows:

More details on what is expected for each of these milestones are below. You are encouraged to consult us early, and submit the proposal/progress reports early, and we will do our best to provide early feedback.

Proposal: The proposal (which can be quite short), should include the following components:

  1. Participating group members (one or more)
  2. General area you'd like to investigate. Optionally, includ the reason that you selected this area.
  3. Identify an open problem you'd like to solve, or a research result you'd like to achieve. Imagine the best case scenario of you succeeding in your project: what will the abstract of the paper say? Include the statement of a (conjectured) result you hope to achieve, some motivation for why you think this is interesting, and how this compares to what is known. At this stage the open problem can be open ended (e.g., you could include more than one potential open problem, or a range of possible results parameters, or a "meta" open problem indicating your plan for coming up with an open problem of a certain type).
  4. An initial list of papers you plan to read, or other materials you plan to study.
  5. Indicate what you plan to complete by the time you submit your progress report. Keep in mind that as you explore and study an area (and also as you receive feedback from us), your plans may shift (you will have a chance to update your plan in the progress report).

Progress Report: The progress report will include the initial project proposal, and additionally include updates and refinement on points 3 and 5 above. Specifically, discuss what you've learned so far, and what changes you'd like to make to your proposed research problem. At this stage, the open problem you state as your goal should be more concrete (for example, a formal statement of a theorem you would like to prove or disprove). If based on your study so far you think your initial plan is not feasible or not interesting, explain why and set a new goal which you believe is interesting and achievable within the time frame. In any case you should outline your planned approach towards satisfying your goal based on the progress you've made so far. Additionally, describe what you are planning to cover in your project presentation.

Final report: Your final report will consist of a paper describing what you have achieved. If you obtained a new research result, state it clearly (typically this would take the form of a formal theorem, but the main result could also be a new formal model / definition, a description of experimental findings, etc), and include background information and motivation. If you have not solved a new open problem (which happens more often than not, given the short duration of the project), your final report will include a literature survey, open problems, a description of why and where you got stuck, and what you learned from these obstacles, including a suggestion for the next research steps, and what might be obtainable.

Overall, there are two main goals for a project in this class, and your final report should demonstrate you have progressed on both (although the ratio between the two can vary).

  1. Acquiring a substantial body of knowledge about the topic of your project. This will involve closely and carefully reading literature on your specific topic (likely to be several papers). You should demonstrate this aspect of your project in the "background" section(s) of your final report, which should be a clear synthesis and exposition in your own words of what you have learned.
  2. Gaining 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 a plausible approach to make progress; and (iii) working towards delivering on your approach. You should demonstrate this aspect of your project by explaining in detail your efforts towards (i), (ii) and (iii) in the rest of your final report.
The ratio of (1) to (2) may vary significantly between different projects. There are some projects that might involve relatively less background; in that case you will be expected to spend more time, and give more evidence of time well spent on the progress made and your successful/unsuccessful attempts. For other projects, you will need to acquire more extensive background.

There is no minimum (or maximum) number of papers you have to read or pages that you have to write, though we will try to guide students towards comparable (and reasonable) amount of work to complete your project. The expectation from a group will be calibrated to the group size, but the rule of thumb is: make an honest effort, start early, do not hesitate to request feedback.

Project Presentations: Each project will be presented to the rest of the class (during the last lecture, or during a designated time in the reading or finals week, in lieu of a final for the class). The amount of time will be between 15-35 minutes, depending on the number of students / projects we have in the class, and the size of the group (as we want each student to participate in their project presentation).

Project Topics

The project can be on any topic related to cryptography; it can, but does not have to, fall within the overall theme of the class this semester.

Here is an evolving document with Ideas for Project Topics.

Here are also some topics and suggestions published in the previous two iterations of the class.

Back to main class webpage