The final will be during the last class, 12/10.
There will be no office hours 11/24.
Problem set 5 is now available and due 12/03. Problem sets can be submitted physically at the beginning of class, or electronically. Electronic submissions should be sent by email to the course TA as a single file in PDF format, with the filename including your uni and the problem set number.
As mentioned in class, early submissions can be submitted electronically by 11/12 for comments to be returned by my 10/28 office hours. Partial submissions are fine for this.
CVN lectures available.
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 suitable class for undergrads
as well.
We meet Tuesday and Thursday, 1:10-2:25pm at 1024 Mudd.
Use the links above to navigate the class pages.
Questions? Email the instructors and/or the TAs.
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
While cryptography is an ancient field, the emergence of modern cryptography
in the last three 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.
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.
The following is an ambitious list of topics to be covered. Depending on time, some of the topics may be omitted.
The following topics are outside of the scope of this class. Some aspects of these topics are taught in COMS W4180 (Network Security), COMS 4187 (Security Architecture and Engineering), and COMS E6184 (Anonymity and Privacy) classes.
We will use the book “Introduction to Modern Cryptography” by Jonathan Katz and Yehuda Lindell, Chapman and Hall/CRC Press. This book will be on reserve in the 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.
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, 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.
The grading will be based on homework (50%), and midterm(s)/final
(50%) – more details TBA.
Homework: There will be about 7 homework assignments,
counting for 50% of the grade. Typically, between one and two
weeks will be given for each homework. You may consult outside
references when doing the homework, as long as these sources are
properly referenced, you write up the solution yourself in your own
words, and you understand the answer.
Collaboration is allowed for groups of at most 3 students, under the
following conditions:
Homework will usually be due at the beginning of
class, in paper form (typed or legibly handwritten).
You are allowed 6 late days for the semester, of which at most 2 late days may
be used for any single homework assignment. Late days are counted in
increments of 24 hours (for example, 10 minutes late is considered as 1 day
late). You may submit late homeworks in person to the instructor or the TA, or leave the homework in the instructor's mailbox
and send an email. If you do not submit in person, we will send you an
ack upon receipt of your email.
All students are presumed to be aware of the departmental policy
regarding academic honesty.