COMS W4261:   Introduction to Cryptography

    Fall 2019

Teaching Staff | Syllabus | Lecture Summaries | Required and Suggested Reading | Prerequisites | Grading and Policies | Homework | Quizzes | Courseworks | Gradescope

Announcements

  • 1/5/19 Final letter grades submitted. Thank you for a great semester.
  • 12/30/19
    • HW6 grades have been released on gradescope. Mean: 63.4, Median: 66.5, Std Dev: 21.43.
    • Note: the worst homework of each student will count as half the weight compared to other homework.
  • 12/22/19 Scores for the final were uploaded on courseworks. Mean: 80.84, Median: 83, Std Dev: 13.62

General Information

This is a three-credit graduate level course. It can be credited to all degree programs, subject to advisor approval.  It is also a theory elective for the PhD program in computer science, a suitable elective for the MS foundations or security tracks, and a foundations track elective for undergrad CS majors.  
We meet Tuesday and Thursday, 11:40-12:55 at 633 Mudd.

Teaching Staff and Office Hours

You can email the teaching staff at cryptofa19 at googlegroups dot com with any question about the material (lecture, homework, etc) or administrative issues. For issues of a personal nature, feel free to email the professor directly (if you have a medical or other emergency, have your advisor/dean contact the professor).

Instructor

Tal Malkin (tal at cs)
Office hours: Thursday 2:00-4:00pm, 514 CS Building

Teaching Assistants

Lali Devadas (lalita.devadas at columbia)
Office hours: Tuesday 5-7:30pm

Eli Goldin (eg2917 at columbia)
Office hours: Monday 4:15-6:45pm

Alex Lamy (a.lamy at columbia)
Office hours: Wednesday 2-4pm

All TA office hours are in the Computer Science TA room in Mudd unless otherwise noted.

CVN office hours will alternate between Mondays 8-9pm and Wednesdays 8-9pm on alternate weeks. See announcement section for upcoming CVN office hours.

Class Description and Syllabus 

Lectures and Readings

This course is an introduction to modern cryptography.  In general, cryptography aims to construct efficient schemes achieving some desired functionality, even in an adversarial environment.  For example, the most basic question in cryptography is that of secure communication across an insecure channel: Can Alice send a message to Bob so that Bob understands the message, but no eavesdropper does?   How can Bob be sure that the message received was sent by Alice?  Another question is that of secure computation in an insecure environment:  Can a group of parties perform some distributed computation (e.g., coordinate an attack, or tally a vote), so that an adversary controlling the communication channels and some of the parties cannot disrupt the computation or learn extra information?  

While cryptography is an ancient field, the emergence of modern cryptography in the last few decades is characterized by several important features distinguishing it from classical cryptography.  For one thing, the availability of computers and the wide spread of networked information systems and the Web, has dramatically increased both the need for good cryptography, and the possibilities that it can offer.  In addition to the classical military and national security applications, a wide scope of financial, legal, and social cryptographic applications has emerged, from using a credit card on-line or sending an encrypted email, to more ambitious goals of electronic commerce, electronic voting, contract-signing, database privacy, and so on.  The most important characteristic of modern cryptography is its rigorous, scientific approach, based on firm complexity-theoretical foundations.  In contrast to the classical approach based on ad-hoc solutions (design a scheme that seems very hard to break, and hope for the best), modern cryptography aims for specific, rigorously quantifiable security guarantees,  based on precise mathematical definitions and provably secure protocols.

What You Will Learn in This Class (Hopefully!)

The principles and techniques underlying the above will be illustrated through specific examples drawing from the basic cryptographic primitives.  Through these examples, which are very important on their own, you will also learn to critically evaluate and interpret cryptographic definitions and security proofs (i.e., what is and what is not guaranteed?).  
While the class will focus on the theoretical foundations, we will discuss the relation to how things are actually done in practice.
The material covered in the class should prepare you to make sense of some current research papers in cryptography, and to study further on your own (or take an advanced class).  Opportunities for research under my supervision may be available for interested students who do well in the class.

Tentative List of Topics 

The following is an ambitious list of topics to be covered.  Depending on time, some of the topics may be omitted.

What You Will Not Learn in This Class

The following topics are outside of the scope of this class.

Other classes related to cryptography, which cover some aspects of the above topics, include COMS 4181 (Security I), COMS E6184 (Anonymity and Privacy), COMS W3995 Computers and Society, COMS 4995 Blockchains and Applications, Math 3020 (Number theory and Cryptography), and Math 3025 (Making and Breaking Codes). All these classes have very little intersection with our class.

Required Text

We will use the book “Introduction to Modern Cryptography” by Jonathan Katz and Yehuda Lindell, Chapman and Hall/CRC Press, 2nd edition. This book will be on reserve in the science and engineering library, and available from the Columbia bookstore.   Additional papers and handouts may occasionally be distributed in class.  Recommendations for some other textbooks (not required) appear here

Prerequisites

The following skills will be assumed:

It will also help to have background in at least some of the following areas:

These topics will be briefly covered in class as needed, but if you do not have any background in any of them, you are likely to find it hard to keep up.

The appendix of the textbook reviews some background, and additional references for background reading can be found here

Grading and Policies

The grading will be based on homework (50%), quizzes (15%), and a cumulative exam (35%).
Students are expected to attend class, and to carefully go over each lecture before the next one. There will also be some required readings assigned, that the students will be responsible for.
No laptops, phones, or other electronic equipment are to be used during class, unless you have obtained prior approval from the instructor (I will approve any request that is for the purposes of taking notes on a device that will be used only for this purpose, with internet access and notifications disabled).


All students are presumed to be aware of the departmental policy regarding academic honesty.