- Wiki: CRYPTUTOR
- Book: Katz-Lindell (coming soon)
- Notes: Bellare-Rogaway
- Book: Goldreich (Also A Primer)
- Notes: Goldwasser-Bellare

- CS 498: Special Topics

__Theoretical Foundations of Cryptography__

Prof. Manoj M. Prabhakaran

TA: Hemanta Maji [office: 3301 SC] - 9:30 AM - 10:45 AM Wednesday/Friday

1111 Siebel Center - Section PR3 (CRN 40094)

3 credits (grad and undergrad) - Section PR4 (CRN 47171)

4 credits (grad only) - Directory Listing

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.

- Lecture 00 [anim | pdf | print] (Aug 24): Introduction
- Lecture 01 [anim | pdf | print] (Aug 29): One-message Encryption: Perfect Secrecy and SIM-onetime security
- Lecture 02 [anim | pdf | print] (Aug 31): One-message Encryption: Perfect Secrecy, SIM-onetime security and IND-onetime security
- Assignment 1
- Lecture 03 [anim | pdf | print] (Sep 5): Computational Indistinguishability, IND-CPA, SIM-CPA
- Lecture 04 [anim | pdf | print] (Sep 7): Pseudorandomness Generator, Hybrid arguments, One-way Permutations and Hardcore predicates
- Lecture 05 [anim | pdf | print] (Sep 12): One-way Functions, Goldreich-Levin predicate
- Lecture 06 [anim | pdf | print] (Sep 14): Stream Ciphers, Block Ciphers, Pseudorandom Functions, PRF from PRG
- Assignment 2
- Lecture 07 [anim | pdf | print] (Sep 19): Block Ciphers, Pseudorandom Permutations, Feistel Networks, Luby-Rackoff, Block cipher operation modes
- Lecture 08 [anim | pdf | print] (Sep 21): Public-Key Encryption, IND-CPA and SIM-CPA, Discrete-Log and DDH assumptions, El Gamal encryption
- Lecture 09 [anim | pdf | print] (Sep 26): DDH assumption and El Gamal encryption, Trapdoor PRG and Trapdoor OWP
- Lecture 10 [anim | pdf | print] (Sep 28): Candidate Trapdoor OWPs. Chinese Remainder Theorem and Composite Order Groups
- Assignment 3
- Lecture 11 [anim | pdf | print] (Oct 3): Chosen Ciphertext Attack, SIM-CCA and IND-CCA
- Lecture 12 [anim | pdf | print] (Oct 5): Equivalence of SIM-CCA and IND-CCA, MAC and its use in SIM-CCA SKE
- Lecture 13 [anim | pdf | print] (Oct 10): SIM-CCA PKE: Cramer-Shoup, Hybrid Encryption, Random-Oracle Model
- Lecture 14 [anim | pdf | print] (Oct 12): Message Authentication Codes
- Lecture 15 [anim | pdf | print] (Oct 17): Hash Functions: UHF, UOWHF, CRHF.
- Lecture 16 [anim | pdf | print] (Oct 19): Merkle Trees for domain extension of UOWHF, CRHF. Domain extension of MAC. Digital Signatures.
- Lecture 17 [anim | pdf | print] (Oct 24): Digital Signatures from OWF, and in the Random Oracle Model.
**Class Test 1**(Oct 26)- Assignment 4
- Lecture 18 [anim | pdf | print] (Oct 31): Secure communication wrap up. Taking stock.
- Lecture 19 [anim | pdf | print] (Nov 02): Secret Sharing.
- Lecture 20 [anim | pdf | print] (Nov 07): Introduction to Secure Multi-Party Computation.
- Lecture 21 [anim | pdf | print] (Nov 09): Secure Multi-Party Computation: Yao's Garbled Circuit
- Lecture 22 [anim | pdf | print] (Nov 14): Zero-Knowledge Proofs
- Assignment 5
- Lecture 23 [anim | pdf | print] (Nov 16): Zero-Knowledge Proofs and Composition
- Lecture 24 [anim | pdf | print] (Nov 28): Universal Composition
- Lecture 25 [anim | pdf | print] (Nov 30): Quantum Cryptography
- Lecture 26 [anim | pdf | print] (Dec 5): That's all! (And student presentation #1.)
- (Dec 7): Student presentations. [Pavithra Prabhakar| John Lenz]