Download all lecture notes here.
See YouTube
lecture videos.
Important Note regard Change in Course Numbers: This course used to be 15503/15827. The course numbers have changed (however the content would remain the same). This course would still satisfy all requirements which 15503/15827 used to (e.g., for security and theory concentrations).
|
Instructor |
Vipul Goyal <Vipul at cmu.edu> |
|
Time |
MW
1:30pm – 2:50pm |
|
Location |
CMU
Remote (Zoom) |
|
TAs |
Lisa Masserova <elisawem@andrew.cmu.edu>, |
|
Office
Hours |
TA:
(Lisa) Tuesday 3pm to 4pm, (Justin) Wednesday 8:30am to 9:30am |
NOTE: please join the class on piazza. Here
is a direct link.
All further course material and updates will only be posted on piazza.
Prerequisites
This is an introduction to cryptography course. The course is open to graduate and undergraduate students. It is cross-listed with 15-856. This is the website for both the course sections. The course does not assume any prior background in cryptography or computer security. However a basic level of mathematical maturity is expected. It is recommended that you must have taken a course either in: algorithms or theoretical computer science (such as 15-251) or probability/discrete math (such as 21-228).
Currently the prerequisites for this course are 15-251 (OR) 21-228. However if you haven’t taken either of these course but you still believe you can handle the material (e.g., because you did very well in 15-151 or you have special interest in Crypto), please enroll in the waitlist and send the instructor an email.
Grading Policy
Grading policy for both the sections is the same:
5 Homeworks: 10% each
Midterm (in class): 25%
Final (take home): 25%
Class participation and attendance: extra credits (up to 5%)
Improve lecture notes: extra credits (up to 10%)
Exams
2 hour in class midterm: 10/26/2020 covering material up to 10/14/2020 (Tentative Time: 1:30pm to 3:30pm)
Final Exam (take home): 12/14/2020 noon to 12/15/2020 midnight (36 hours given to accommodate other finals)
Tentative List of Lectures
|
Date |
Topic |
Description |
Relevant Reading |
|
09/02/2020 |
Introduction |
Course
focus, prerequisites, what will be covered, what is expected |
|
|
09/09/2020 |
Classical
Ciphers and Perfect Secrecy |
Classical
ciphers and why they were all broken, one-time pad, moving to modern
cryptography based on hard problems like factoring |
|
|
09/14/2020 |
One
Way Functions |
Definitions,
motivation, candidate constructions |
|
|
09/16/2020 |
Pseudorandomness – I |
Pseudorandom
generators (PRG), computational indistinguishability |
|
|
09/21/2020 |
Pseudorandomness – II |
Constructing
PRGs, Hybrid arguments |
|
|
09/23/2020 |
Pseudorandomness – III |
Pseudorandom
functions (PRF), constructions |
|
|
09/28/2020 |
Secret-Key
Encryption |
Defining
encryption, why all deterministic encryption schemes are insecure,
construction using PRF, a warning regarding mauling attacks |
|
|
09/30/2020 |
Number
theory and hardness assumptions |
Groups,
Euler’s function, discrete log problem, RSA function |
|
|
10/05/2020 |
Key
Agreement |
Diffie-Hellman
Key exchange, proof of security |
|
|
10/07/2020 |
Public-Key
Encryption – I |
Definition,
trapdoor permutations, RSA based construction |
|
|
10/12/2020 |
Public-Key
Encryption – II |
El-Gamal
encryption, others |
|
|
10/14/2020 |
MAC
and Hash Functions |
Message
Authentication Codes (MAC), Collision-resistant hash functions (CRHF),
constructions |
|
|
10/19/2020 |
Digital
Signatures |
Message
Digital Signatures, constructions |
|
|
10/21/2020 |
Secret
Sharing |
XOR
secret sharing, Shamir Secret Sharing, Applications |
|
|
10/26/2020 |
In
Class Midterm (2 hours) |
Covers
material up to 10/09, Open book |
|
|
10/28/2020 |
Midterm/Homework
Solutions |
Solutions
from Midterm and selected homework problems |
|
|
|
|
|
|
|
11/02/2020 |
Blockchains
- I |
What
are Blockchains, how mining works |
|
|
11/04/2020 |
Blockchains
- II |
Merkle
Tree, Smart Contracts, applications and limitations of Bitcoins |
|
|
11/09/2020 |
Blockchains
- III |
Other
interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains |
|
|
11/11/2020 |
Zero-Knowledge
Proofs – I |
What
is zero-knowledge (ZK), notion of simulation, Graph Isomorphism |
|
|
11/16/2020 |
Zero-Knowledge
Proofs – II |
Commitment
schemes |
|
|
11/18/2020 |
Zero-Knowledge
Proofs – III |
ZK
for any NP statement |
|
|
11/23/2020 |
Secure
Computation – I |
Yao's
millionaire problem, 1-out-of-2 oblivious transfer |
|
|
11/30/2020 |
Secure
Computation – II |
Coin-Flipping,
ZK proofs of honesty, secure computation for small inputs |
|
|
12/02/2020 |
Secure
Computation – III |
Yao’s
garbled circuits, additional topics |
|
|
12/09/2020 |
Finals
Preparation |
|
|
Useful Reading
Look at previous versions of this course for a list of topics covered + lecture notes:
Fall 2019: Introduction to Cryptography
Spring 2018: Introduction to Cryptography (15503 and 15827) (lecture notes available online)
There is no required textbook for the course. Following is some other recommended material for the course: