Fall 2018


15503/15827:  Introduction to Cryptography



Vipul Goyal




MW 1:30pm – 2:50pm


GHC 4303


Yifan Song <yifans2@andrew.cmu.edu>


Vipul at cmu.edu




Office Hours

Important: Please CC the TA on ALL emails. When sending me an email about the course, make sure your title starts with "[Teach]" (without the quotes).

TA: Friday 1:30pm to 2:30pm (GHC 4303)

Instructor: please setup an appointment by email or drop by after the class


NOTE: Course starts the week of 09/03 to allow for incoming PhD orientation course


NOTE: please join the class on piazza by searching for 15-503 or 15-827. 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 advanced undergraduate students. It is cross-listed with 15-827. 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 or probability/combinatorics.



Grading Policy


Grading policy for both the sections is the same:

4 Homeworks: 8% each

Scribe notes: 18%

Note: each student would be responsible for scribing 2 lectures (9% each)

Midterm (in class): 25%

Final (take home): 25%

Class participation: Extra credits




2 hour midterm: 10/22/2018 (1:30 to 3:30) covering material upto 10/10/2018

Final Exam (take home): 12/13/2018 noon to 12/14/2018 midnight (36 hours given)




Will be posted here periodically



Scribe Notes


Scribe notes must be written in latex. Please use this template. The first draft is due 3 days after the class (please send to the TA and CC the instructor). Please incorporate feedback from TA/Instructor and upload on the website no later than 1 week after the class.



List of Lectures





Relevant Reading



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


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 - I

Definitions, motivation



One Way Functions - II

Candidate construction, Hard core predicates



Pseudorandomness – I

Pseudorandom generators (PRG), computational indistinguishability



Pseudorandomness – II

Constructing PRGs



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



In Class Midterm (2 hours)

Covers material up to 10/10, Open book



Midterm/Homework Solutions

Solutions from Midterm and selected homework problems



MAC and Hash Functions

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



Digital Signatures

Message Digital Signatures, constructions



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, ZK for any NP statement



Secure Computation – I

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



Secure Computation – II

ZK proofs of honesty, 1-out-of-n oblivious transfer, secure computation for small inputs



Secure Computation – III

Yao’s garbled circuits



Additional topics






Useful Reading


There is no required textbook for the course. Following is some recommended material for the course: