Carnegie Mellon University - Spring 2016
Broadly, cryptography is the science of designing algorithms and protocols that guarantee privacy, authenticity, and integrity of data when parties are communicating or computing in an insecure environment. The recent explosion of electronic communication and commerce has expanded the significance of cryptography far beyond its historical military role into all of our daily lives.
While cryptography or "hidden writing" has been around for several millennia, it has been revolutionized in the last few decades. Firstly, cryptography has been transformed from an ad hoc collection of tricks into a rigorous science based on firm complexity-theoretic foundations, showing a path to break out of the "invent-break-tweak" cycle that characterized cryptography throughout history. Secondly, cryptography has enabled applications far beyond simple encryption codes, including several impossible sounding notions such as communicating secretly without a shared secret (public-key encryption), giving proofs that leak nothing but the validity of the statement claimed (zero-knowledge proofs), computing without revealing one's private data (secure multiparty computation), computing on encrypted data (fully homomorphic encryption), and so on.
This course will be an introduction to the modern, complexity-theoretic approach to cryptography with an emphasis on the fundamental ideas (as opposed to practical implementations -- in particular this will NOT be a course about computer security). We will see how cryptographic problems can be given precise mathematical definitions, and will then construct algorithms that provably satisfy these definitions, under precisely stated and widely believed assumptions about the intractability of certain computational problems.
Among the topics covered will be private key and public key encryption schemes, authentication schemes and digital signatures, one-way functions, pseudorandom generators, zero-knowledge proofs, and security against active attacks. As time permits, we may also cover more advanced topics such as two-party and multi-party secure computation, fully homomorphic encryption, and program obfuscation. See the linked syllabus above for more detailed information.
The formal prerequisite for the course is 15-251 "Great Theoretical Ideas in Computer Science."
The main skills that will be assumed are: the ability to understand and write formal mathematical definitions and proofs; comfort with reasoning about algorithms, such as proving their correctness and analyzing their runtime; and comfort with basic discrete probability and probabilistic reasoning.
The main background that will be helpful is some knowledge of
Complexity Theory: NP-completeness, reductions
Randomized Algorithms, such as a primality testing algorithm.
Basic Number Theory: modular arithmetic, Chinese Remainder Theorem.
Basic Algebra: Groups, fields, and polynomials over fields.
Probability Theory: independence, conditional probabilities, expectation, Bayes' Law.
The course will be mathematical in nature, and the homeworks and exams will involve challenging problems that require rigorous, clearly argued proofs.
The evaluation will be based on several problem sets, a midterm, and a final examination. There will be no projects or programming assignments.
Click the Edit button to add class information.
You have the option of deleting this announcement from just the course homepage or deleting this announcement from the course homepage and Q&A feed. What would you like to do?
You'll lose everything you typed, plus all the time it took to type it...