Time & Place: Thursdays 2:10pm-4:00pm, Mudd 524
Administrative Notes:
This course can be used as an elective for the PhD program in computer science and for undergraduate CS majors, and as a secondary elective for MS students in the "Foundations of Computer Science" or the "Computer Security" pathways.
COMS-W4261 Introduction to Cryptography, or two 4000-level theory courses, or instructor approval. The most important prerequisite is mathematical maturity, and comfort with (preferably also strong affection for) rigorous definitions and proofs.
This class will explore the emerging interface between cryptography and AI. Our main focus will be on cryptographic approaches to AI, asking how we can build on the last four decades of development of modern cryptography towards understanding, formulating, and achieving privacy, trust, and safety goals for AI algorithms, as their interaction with everyday public discourse continues to grow. This includes exploring cryptographic techniques that can be used either to develop privacy-preserving and safe AI, or to demonstrate attacks against it. More importantly, it also includes applying a cryptographic mindset: explicitly thinking about adversarial models, rigorously formalizing definitions and assumptions, and provably showing when they can and cannot be achieved, all while using the complex, ambiguous, and messy real world to inform our choices and argue their meaningfulness. We will also consider the other direction: how recent AI developments can help towards achieving cryptographic goals.
We will explore these topics through critical reading of recent research papers, and discussion of open problems and directions. Specific papers will be selected by the instructors based on their interests and the interests of the students taking the class. Sample topics may include privacy-preserving learning, secure inference, watermarks for generative AI, backdoors in AI models, interactive proofs and verification of model properties, cryptographic hardness of learning tasks, weight extraction, steganography, AI-based cryptography and cryptanalysis, and AI safety.
This course is an advanced graduate level seminar, where most lectures will be given by students taking the class (with prior feedback and support from the instructors and fellow students). A typical lecture will center around a topic (e.g., watermarks for generative AI, backdoors in ML models) and involve presenting, critiquing, and discussing several papers within this topic. This plan may change as the course progresses, based on student and instructor interest.
In each lecture, we have listed papers that will be presented (self explanatory), along with papers that are optional (not the focus but will be featured in lecture), and papers that are relevant (may not be discussed in lecture, but we recommend checking them out if you're interested).
Introduction and class overview (what is a cryptographic mindset?); Private Learning I
First lecture given by Miranda and Tal, slides available here (to those with a Columbia account). The lecture covered the following works:
Question to think about: What can we do when practical defenses have no provable guarantees (and are in fact easily broken), but provable defenses are impractical?
Assignment: Make sure you have access to the gradescope page for our class. You can reach it from courseworks (left side of menu), or by adding the course on gradescope with entry code ZJP8J8. First quiz will be posted shortly!
Adversarial examples and backdoors
Presentation 1: the exciting world of adversarial examples
Presentation 2: backdoors
Private learning II
Papers TBA.
Watermarks
Presentation 1: hash-based LLM watermarks
Presentation 2: pseudorandom-code-based watermarks
Papers and topics to be covered later in the semester (schedule TBD). Email us if you want to sign up!
Below are additional resources you may find helpful.
The class requirements and their relative weight in the grade are as follows:
Overall, we plan to grade (very) generously, but what you get from the class in terms of the class goals—learning of and exposure to the topics covered, research, and teaching—is proportional to how much you put into it (and for the learning part, also proportional to how much your fellow students and teaching staff put into the teaching part). We hope for an intimate, fun class, where everyone puts forth their best effort.
The team of presenter(s) and supporter(s) will work together to thoroughly understand the assigned paper(s), and plan how to teach it effectively. Motivation and context, as well as definitions, proofs, techniques, and open problems, are all important—the team, with guidance and feedback from the teaching staff, should plan the right balance in teaching their particular topic to the class.
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 (and have before). 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 required include a proposal, progress report, and final report, as well as project presentations at the end. Details for the expectations and time line will be posted here soon.
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).
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.
More information, deadlines, and suggested topics and resources for projects will be provided soon.
We expect that the primary goal of everyone in the class is to learn (we can imagine no other reason that you would be in this class). Hopefully this means that there will be no focus on grades (which we can tolerate but discourage in this class), and no issues of dishonesty (which we absolutely will not tolerate). In particular, students should take the quizzes on their own, and be sure to provide appropriate citations for all sources used in their project reports, as well as acknowledgements to other people who contributed (just as you should do in any academic publishing).
As in every CS class, students are expected to adhere to the academic honesty policy of the CS department. This policy has been passed by the faculty of the Department and approved by the school deans.
We require that all original text (e.g., on your slides and in your final project) is written by you. Cosmetic use of AI, for proofreading/grammar is acceptable. We say "original text" because your slides and project may include definitions or theorems from relevant papers, with proper attribution. Otherwise, we allow any use of AI: to help with coding, understanding papers, etc. However, we believe that struggling with difficult material is very important in building research skills. We encourage you to use your best judgment (about what will best help your learning) when using AI.