Instructor: 



Time: 
MW
1:30pm – 2:50pm 
Location: 
GHC
4303 
TA 
Yifan Song <yifans2@andrew.cmu.edu> 
Instructor 
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 15503 or 15827. 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
advanced undergraduate students. It is crosslisted with 15827. 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
Exams
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)
Homework
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
Date 
Topic 
Description 
Relevant
Reading 
09/05/2018 
Introduction 
Course focus,
prerequisites, what will be covered, what is expected 

09/10/2018 
Classical Ciphers and Perfect Secrecy 
Classical ciphers and why they were all broken, onetime pad, moving to modern cryptography based on hard problems like factoring 

09/12/2018 
One Way Functions  I 
Definitions, motivation 

09/17/2018 
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 


SecretKey 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 
DiffieHellman Key exchange, proof
of security 


PublicKey Encryption – I 
Definition, trapdoor permutations, RSA based construction 


PublicKey Encryption – II 
ElGamal
encryption, others 

10/22/2018 
In Class
Midterm (2 hours) 
Covers material
up to 10/10, Open book 

10/24/2018 
Midterm/Homework
Solutions 
Solutions from
Midterm and selected homework problems 


MAC and Hash Functions 
Message Authentication Codes (MAC), Collisionresistant 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 


ZeroKnowledge Proofs – I 
What is zeroknowledge (ZK), notion of simulation, Graph Isomorphism 


ZeroKnowledge Proofs – II 
Commitment schemes, ZK for any NP statement 


Secure
Computation – I 
Yao's millionaire problem, 1outof2 oblivious transfer 


Secure
Computation – II 
ZK proofs of honesty, 1outofn 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: