Theoretical Foundations of Cryptography

Have you wondered how one might define security -- even for a cryptographic concept as simple and familiar as encryption? What makes public-key cryptography possible? (Well, what is public-key cryptography?) What other tools can cryptography offer? Are there limits to the magic of cryptography?

This course is an introduction to the theoretical foundations of cryptography. Emphasis will be on developing fundamental concepts, aided by simple -- but precise and comprehensive -- mathematical definitions of security.

Prerequisite. CS 173 and 273 or consent of instructor. Some mathematical maturity will be expected. Familiarity with basic theory of computation and complexity theory will be helpful.

Course objectives. This course familiarizes you with fundamental concepts of cryptography. By the end of the course, you should have a sound understanding of the methodology of the theory of cryptography: probability based definitions, various constructions, complexity theoretic primitives and proofs of security. You should be able to interpret security guarantees and verify their proofs. You would also gain familiarity with some of the most important cryptographic tasks, and schemes to realize them. For those interested in pursuing research in theoretical cryptography, this course would be a sound background.

Work involved. Attend the lectures and solve the assignments; read and ponder over textbook(s)/references or handouts given in class. Grading will be based on assignments (60%), easy/short class-tests (20%) and class-participation (20%). Assignments will typically be given out on a Wednesday and will be due in next week's Friday lecture. Class-tests will be announced a week in advance. Class participation includes, well, participation in the classroom, and contributing to the wiki. In addition, the graduate section of the course involves reading up and making a presentation on an advanced/specialized topic.

No Class Test 2! There won't be a second class-test. Instead Assignment 5 will carry extra weight.

Course contents. The initial part of the course will cover secure communication (encryption and authentication). A good reference would be the Bellare-Rogaway notes. Towards the end of the course we will focus on other important topics that lead up to secure multi-party computation. As time permits, we will also see glimpses of a variety of other concepts and tools. Through out the course we will develop and use basic mathematical background, definitional methodology and proof-techniques.

Here's the list of lectures from the last edition of the course (expect several significant changes).

Office hours. Prof. Prabhakaran's office hours are Wednesday 1:30-2:30pm, every week (unless otherwise announced in the class). TA Maji's office hours will be on Tuesdays, 3:30-5:00pm. Please do come for the office hours if you found anything mysterious (or missed anything) in the lectures, class-tests or assignments. You are also welcome to drop by and chat about the content/structure of the course during the office hours. Feel free to send us e-mails anytime if you have any questions or comments.

Lectures so far