CMSC 858K --- Advanced Topics in Cryptography
This course is an advanced course in cryptography, intended primarily for those interested in research in this area.
This course will not be an introductory survey of cryptography, as it was last year.
Instead, I will focus on more advanced topics and on more recent results.
The course will primarily be concerned with theoretical aspects of cryptography, and not with "algebraic" or "number-theoretic" techniques (although some basic group theory will be presented, as needed).
The course will emphasize definitions, foundations, and formal proofs of security.
There will be no assigned textbook for this class (there are not really any suitable texts).
However, the presentation will most closely match the "style" of the book Foundations of Cryptography, vol. 1, by O. Goldreich; we will also cover portions of Chapter 4 of that book.
Most of the course will be based on articles from the literature, to which appropriate references will be given.
Good background reading for this course includes the undergraduate lecture notes of Bellare and Rogaway, as well as my lecture notes from the undergraduate crypto course (CMSC 456).
There is no specific material from these notes that is required per se. Rather, the important thing is to get a sense of what modern cryptography is about, as well as to gain some familiarity with the types of proofs common in cryptography.
Unfortunately, this is not often taught in other cryptography courses.
It is my intention to make the course accessible to students who have not taken cryptography before.
However, students who take no other cryptography course will miss out on some fundamental aspects of cryptography that are covered in the survey course, but not covered here.
Also, students who have not had a prior course in cryptography may miss out on some of the context of what we discuss in this class (i.e., an understanding of why a particular problem is important, or how it relates to other results).
Finally, students who have not previously taken a course in modern cryptography may have to work harder and do more outside reading in order to keep up.
There are no official prerequisites for the course, but mathematical maturity (especially comfortability with proofs and the ability to think abstractly) is assumed.
It is expected that students taking this course are interested in cryptography and potential research in this area.
As such, it is hoped that none of the course requirements will present a problem for anyone taking the class.
The requirements are:
Note that there will not be any homeworks; I think scribing lecture notes is a better way to learn this sort of material anyway.
- Regular attendance
- Scribing lecture notes (in latex) for multiple lectures (the number of lectures to be scribed by each student will depend on how many students take the class; I expect that each student will scribe about 4-6 lectures)
- There will be a midterm and a final only for those students taking the course for grad credit
For further information about the scribing, see here.
The course lecture notes will be updated throughout the semester.
- Instructor: Jonathan Katz (jkatz AT cs). Office: 3225 AV Williams. Office hours: by appointment.
- The course meets Tuesday and Thursday from 9:30 - 10:45 in CSIC 3120
To some extent, the topics covered will depend upon the interests of the students.
A more detailed syllabus is also available.
The current plan is
tentatively to cover the following topics (topics marked "???" will be added as time permits):
- One-way functions and trapdoor permutations
- Hard-core predicates; the existence of a hard-core bit for every one-way permutation
- Rigorous definition of security for public-key encryption, and a construction of secure public-key encryption from trapdoor permutations
- Chosen-ciphertext security for public-key encryption
- Definitions and motivation: two "flavors" of chosen-ciphertext security
- Interactive proofs and zero-knowledge interactive proofs (briefly and informally, for now)
- Non-interactive zero-knowledge (NIZK) proofs: definitions and a construction based on trapdoor permutations
- The Naor-Yung construction of a "CCA1-secure" public-key encryption scheme
- The Dolev-Dwork-Naor construction of a "CCA2-secure" public-key encryption scheme
- Other constructions of CCA2-secure encryption based on general assumptions (???)
- Non-interactive zero-knowledge proofs of knowledge (???)
- Non-malleable NIZK (???)
- The Cramer-Shoup encryption scheme
- Chosen-ciphertext security in the random oracle model
- Interactive (zero-knowledge) proofs and proofs of knowledge
- Interactive proofs in more detail
- Zero-knowledge proofs and proofs of knowledge: definitions and constructions
- Constant-round zero-knowledge proofs of knowledge
- Other concerns (non-malleability, concurrency, etc.) (???)
- Secure distributed computation
- Information-theoretically secure computation (???)
- Two-party and multi-party secure computation (???)
- Byzantine agreement (???)
- Threshold cryptography (???)
- Other topics based on student interest.