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!)
- 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 may 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.
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
- 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%).
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.