15356/15856:  Introduction to Cryptography


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).



Vipul Goyal <Vipul at cmu.edu>
Important: Please CC the TAs on ALL emails


MW 1:30pm – 2:50pm


CMU Remote (Zoom)


Lisa Masserova <elisawem@andrew.cmu.edu>,
Justin Raizes  <jraizes@andrew.cmu.edu>

Office Hours

TA: (Lisa) Tuesday 3pm to 4pm, (Justin) Wednesday 8:30am to 9:30am
Instructor: Monday 3pm to 4pm


NOTE: please join the class on piazza. Here is a direct link. All further course material and updates will only be posted on piazza.



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:

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%)



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




Relevant Reading



Course focus, prerequisites, what will be covered, what is expected

Lecture notes


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


One Way Functions

Definitions, motivation, candidate constructions


Pseudorandomness – I

Pseudorandom generators (PRG), computational indistinguishability


Pseudorandomness – II

Constructing PRGs, Hybrid arguments



Pseudorandomness – III

Pseudorandom functions (PRF), constructions



Secret-Key Encryption

Defining encryption, why all deterministic encryption schemes are insecure, construction using PRF, a warning regarding mauling attacks



Number theory and hardness assumptions

Groups, Euler’s function, discrete log problem, RSA function



Key Agreement

Diffie-Hellman Key exchange, proof of security



Public-Key Encryption – I

Definition, trapdoor permutations, RSA based construction



Public-Key Encryption – II

El-Gamal encryption, others



MAC and Hash Functions

Message Authentication Codes (MAC), Collision-resistant hash functions (CRHF), constructions



Digital Signatures

Message Digital Signatures, constructions



Secret Sharing

XOR secret sharing, Shamir Secret Sharing, Applications



In Class Midterm (2 hours)

Covers material up to 10/09, Open book



Midterm/Homework Solutions

Solutions from Midterm and selected homework problems







Blockchains - I

What are Blockchains, how mining works



Blockchains - II

Merkle Tree, Smart Contracts, applications and limitations of Bitcoins



Blockchains - III

Other interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains



Zero-Knowledge Proofs – I

What is zero-knowledge (ZK), notion of simulation, Graph Isomorphism



Zero-Knowledge Proofs – II

Commitment schemes



Zero-Knowledge Proofs – III

ZK for any NP statement



Secure Computation – I

Yao's millionaire problem, 1-out-of-2 oblivious transfer



Secure Computation – II

Coin-Flipping, ZK proofs of honesty, secure computation for small inputs



Secure Computation – III

Yao’s garbled circuits, additional topics



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: