The security of early cryptographic systems depended to a large degree on the ingenuity of its creators. Most were (and many still are) convinced of the absolute security of their own private cipher. Nearly all were sadly mistaken with predictably disastrous consequences. Cryptographers realized that if a system were likely to be broken, it would be best that their side was the one to do it first. This resulted in a cryptanalysis-drive approach to cryptographic design in which a system is proposed, then attacked, and if found wanting, redesigned. The process iterates until the system is deemed safe enough for the required applications.
Assurance of a cryptographic systems security is thus shared between clever cryptographers and shrewd cryptanalysis. There is something rather unsettling about relying on a system whose security depends on the fact that no one on your side has yet thought of a successful attack. Claude Shannon helped move the field from art to science in the late forties with the publication of Communication Theory of Secrecy Systems. Among other important ideas introduced in this paper, Shannon devised the notion of perfect security to describe cryptographic schemes in which given any two message M1 and M2, and any cipher text, the latter is just as likely to show up when M1 is the message as when M2 is. Such systems are in some sense provably security and are not particularly difficult to implement. The rub is that the number of message bits one can encrypt cannot exceed the number of bits in the key, a restriction that practically speaking puts absolute security out of reach for most.
Modern cryptography abandons absolute security in favor of a system that is provably secure against adversaries with limited computational power. Designing secures systems depends on an understanding of what makes a problem difficult in terms of available computational resources, the study of which is known as complexity theory. Security guarantees are probabilistic statements of the form: “Assuming the adversary uses no more than t computation cycles, her probability of breaking the scheme is at most t/2200”
Attacks against such systems are infeasible, not impossible. This seminar introduces the computational models that computer scientists use to design and evaluate cryptographic systems. We will cover the fundamental building blocks of modern cryptology including one-way functions, trapdoor functions, pseudorandom generators, and zero-knowledge proof systems. It is not expected that everyone have the same background; one participant's weakness may well turn out to be another's strength. Our goal is to collectively master an essential subset of modern cryptographic theory and to have fun along the way.
There is one textbook in this course from which I will assign readings: Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell.
Copies are available in the bookstore.
It is recommended that students have a quick look at chapter 1 of this book before coming to first lecture.
There will be weekly problem sets during the course. Many of the assignments will be challenging. Keep in mind that theory often consumes more time than you think it will. Start your assignments early! This will give you time to think about the problems and ask questions if you hit an impasse. Waiting until the last minute to begin an assignment is a recipe for disaster.
I will strive to have problem sets graded as soon as possible. At this time, solutions will be distributed with the graded homework.
Saad Nawaz, CISCO Certified Security Professional
Phone: +92 313 5111767
LecturesDay/Date Topics1Mon, 17 Sep 2012Principles of Modern Cryptography2Tue, 18 Sep 2012Perfect secrecy3 Wed, 19 Sep 2012Computational security 4 Thu, 20 Sep 2012Computational secure5 Fri, 21 Sep 2012Pseudorandomness + Problems6 Mon, 24 Sep 2012Chosen-plaintext attacks 7 Tue, 25 Sep 2012 Block ciphers 8 Wed, 26 Sep 2012Message integrity 9 Thu, 27 Sep 2012 Secure MACs 10 Fri, 28 Sep 2012Hash functions + Problems11 Mon, 1 Oct 2012Mid-Exam 12 Tue, 2 Oct 2012Confusion & defusion13 Wed, 3 Oct 2012Linear & differential analysis14 Thu, 4 Oct 2012Number theory 15Fri, 5 Oct 2012More number theory + Problems16 Mon, 8 Oct 2012Group theory 17 Tue, 9 Oct 2012
18 Wed, 10 Oct 2012
19 Fri, 12 Oct 2012Final Exam