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.

Section 002 meets Tuesdays and Thursdays 8:40-9:55.
Section 001 meets Tuesdays and Thursdays 10:10-11:25.
Both sections meet in 633 Mudd. All lecures in the first two weeks will be online, you can find the zoom link through courseworks (open to all Columbia students during the shopping period).
Due to covid, in-person attendance is not required, but encouraged (as long as it is safe to do so). Section 001 lectures will be recorded by CVN, and the recordings will be made available to all enrolled students, through courseworks.

Communication: We will be using gradescope and edstem, both accessible from courseworks. Announcements will be sent by email through courseworks, as well as posted on this webpage.
For any administrative issues email 4261spring2022teachingstaff at gmail dot com (reaches the instructor and teaching staff), or if it's a sensitive issue you may email the professor directly.
For questions about the material (lectures, homeworks, etc) use the edstem discussion board.
Regrade requests should be submitted in writing through Gradescope, within one week after the assignment is returned.

Teaching Staff and Office Hours

The names of the teaching staff are listed below, together with their typical office hours. You can reach us by emailing 4261spring2022teachingstaff at gmail dot com (please use that for administrative issues -- class content issues should be posted on edstem)

Instructor

• Prof. Tal Malkin
  • Email: tal at cs dot columbia dot edu
  • Office: 514 CSB
  • Office hours: Tuesday 3:00pm-4:30pm (typically in person), Friday 8:30am-10:00am (typically online)

Teaching and Course Assistants

• Miranda Christ
  • Office hours: Wednesday 2:30pm-4:30pm
• Zeyu (Thomas) Liu
  • Office hours: Friday 8:00pm-10:00pm
• Asif Mallik
  • Office hours: Monday 10:00am-1:00pm
• Cassandra Marcussen
  • Office hours: Thursday 7:00pm-9:00pm
• Sandip Dilip Nair
  • Office hours: Tuesday 11:30am-12:30pm, Thursday 11:30-1:30pm
• SWAPNIL PALIWAL
  • Office hours: Tuesday 5-6pm, Friday 5-6pm

Class Description and Syllabus 

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!)

• Definitions:  Why and how to identify, conceptualize and rigorously formalize goals (e.g., what does it mean for communication to be secure?) 
• Protocol design and analysis:  Constructions and proofs of security (according to established definitions). 
• Foundations: Limits of what is possible to achieve, computational assumptions and their implications in cryptography. 

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 will be omitted.

• Information-theoretic (perfect) secure encryption: one-time pad, Shannon's impossibility result 
• Pseudorandom generators, functions, and permutations, one-way functions and permutations, hard-core predicates 
• Number theory and computational hardness:  factoring, RSA, discrete-log, DH, DDH, LWE
• Private-key encryption: definitions of security and constructions,  block-ciphers and (a little) cryptanalysis
• Trapdoor functions and permutations,  key exchange 
• Public-key encryption:  definitions of security and constructions 
• Message authentication codes, digital signatures, hash functions
• If time permits, we will touch on more advanced topics such as zero knowledge proofs, secret sharing, secure computation, fully homomorphic encryption, obfuscation, cryptocurrencies.

What You Will Not Learn in This Class

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

• Details of specific protocols and standards currently used:  We focus on the general underlying principles in cryptography (with examples to illustrate them), rather than describing the many specific schemes currently in use.
•  How to implement the studied protocols:  We focus on the theoretical aspects, including asymptotic efficiency and provable security.  Implementation of the protocols involves additional issues, both in terms of security and efficiency, depending on the architecture, operating system, hardware, and so on.
• How to secure your computer:  Keep in mind that cryptography is only one (quite important) part of security.  Having good cryptography is necessary, but not sufficient, to assure the security of your system.
• Social and legal issues:  We focus on cryptographic technology.  How this technology could and should be used, and towards which goals, is a fascinating subject, not addressed here.
• Everything worth knowing about cryptography:  We focus on the main underlying ideas and the basic primitives.  This should prepare you to study further on your own (or take an advanced cryptography class), in order to explore the many exciting cryptographic topics that we will not get to here.

Required Text

We will use the book “Introduction to Modern Cryptography” by Jonathan Katz and Yehuda Lindell, Chapman and Hall/CRC Press, 3rd edition. This book will be on reserve in the science and engineering library.   Recommendations for some other textbooks (not required) appear here. 

Prerequisites

• Mathematical maturity, comfort with abstract reasoning, ability to understand and write formal definitions and proofs. 
• Strongly recommended:  one of COMS W4231 (analysis of algorithms) or COMS W3261 (CS Theory) or COMS W4236 (introduction to computational complexity), or equivalent.

The following skills will be assumed:

• Comfort with basic discrete math and probability (COMS W3203 or equivalent)
• Comfort with Big-O notation, ability to reason about algorithms (correctness, running time)

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

• Complexity theory (polynomial time algorithms, NP-completeness, reductions)
• Randomized algorithms (what is a randomized polynomial time algorithm?)
• Probability theory (what is conditional probability? how to compute expectation?) 
• Basic number theory (modular arithmetic, Chinese Remainder Theorem, ...) 

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%) (tentatively on Tue May 10 at 9am, but this is not final yet).
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.

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