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: |
|
|
|
|
|
Time: |
MW
1:30pm – 2:50pm |
|
Location: |
GHC
4215 |
|
TAs |
Lisa
Masserova <elisawem at
andrew.cmu.edu>, Yifan
Song <yifans2 at andrew.cmu.edu> |
|
Instructor |
Vipul
at cmu.edu |
|
Office Hours |
Important: Please CC the TAs on ALL
emails TA:
Friday from 1:30pm to 2:30pm Instructor:
please drop by after the class on Monday |
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:
4 Homeworks: 11% each
Midterm (in class): 25%
Final (take home): 25%
Class participation and attendance: 6%
Extra credits: improve lecture notes (up to 10%)
Exams
2 hour midterm: 10/21/2019 covering material up
to 10/09/2019 (Time: TBA)
Final Exam (take home): 12/12/2019 noon to 12/13/2019 midnight (36
hours given)
Tentative List
of Lectures
|
Date |
Topic |
Description |
Relevant
Reading |
|
08/28/2019 |
Introduction |
Course focus,
prerequisites, what will be covered, what is expected |
|
|
09/04/2019 |
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/09/2019 |
One Way Functions - I |
Definitions, motivation, candidate constructions |
|
|
09/11/2019 |
Pseudorandomness – I |
Pseudorandom generators (PRG), computational indistinguishability |
|
|
09/16/2019 |
Pseudorandomness – II |
Constructing PRGs |
|
|
09/18/2019 |
Pseudorandomness – III |
Pseudorandom functions (PRF), constructions |
|
|
09/23/2019 |
Secret-Key Encryption |
Defining encryption, why all deterministic encryption schemes are insecure, construction using PRF, a warning regarding mauling attacks |
|
|
09/25/2019 |
Number theory and hardness assumptions |
Groups, Euler’s function, discrete log problem, RSA function |
|
|
09/30/2019 |
Key Agreement |
Diffie-Hellman Key exchange, proof
of security |
|
|
10/02/2019 |
Public-Key Encryption – I |
Definition, trapdoor permutations, RSA based construction |
|
|
10/07/2019 |
Public-Key Encryption – II |
El-Gamal
encryption, others |
|
|
10/09/2019 |
MAC and Hash Functions |
Message Authentication Codes (MAC), Collision-resistant hash functions (CRHF), constructions |
|
|
10/14/2019 |
Digital Signatures |
Message Digital Signatures, constructions |
|
|
10/16/2019 |
|
|
|
|
10/21/2019 |
In Class
Midterm (2 hours) |
Covers material
up to 10/09, Open book |
|
|
10/23/2019 |
Midterm/Homework
Solutions |
Solutions from
Midterm and selected homework problems |
|
|
10/28/2019 |
No class! |
|
|
|
10/30/2019 |
Blockchains - I |
What are Blockchains, how mining works |
|
|
11/04/2019 |
Blockchains - II |
Merkle Tree, Smart Contracts, applications and limitations of Bitcoins |
|
|
11/06/2019 |
Blockchains - III |
Other interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains |
|
|
11/11/2019 |
Zero-Knowledge Proofs – I |
What is zero-knowledge (ZK), notion of simulation, Graph Isomorphism |
|
|
11/13/2019 |
Zero-Knowledge Proofs – II |
Commitment schemes, ZK for any NP statement |
|
|
11/18/2019 |
Secure
Computation – I |
Yao's millionaire problem, 1-out-of-2 oblivious transfer |
|
|
11/20/2019 |
Secure
Computation – II |
ZK proofs of honesty, 1-out-of-n oblivious transfer, secure computation for small inputs |
|
|
11/25/2019 |
Secure
Computation – III |
Yao’s garbled circuits |
|
|
11/27/2019 |
No class |
Thanksgiving! |
|
|
12/02/2019 |
Additional topics |
|
|
|
12/04/2019 |
|
|
|
Useful Reading
Look at previous versions of
this course for a list of topics covered + lecture notes:
Fall 2018: Introduction
to Cryptography (15503 and 15827)
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: