Instructor: 



Time: 
TR
3pm – 4:20pm 
Location: 
GHC
4101 
TA 
Yanzun Huang <yanzunh@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 3pm to 4pm (GHC 4101) Instructor:
please setup an appointment by email 
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
(updated)
Grading policy for
both the sections is the same:
3 Homeworks: 10%
each
Scribe notes: 20%
Note: each
student would be responsible for scribing 2 lectures
(10% each)
Midterm (in
class): 25%
Final (take
home): 25%
Class
participation: Extra credits
Homework
HW1.pdf Note: in problem 4, nonnegligible means noticeable.
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.
You may sign up here. Please sign up for ONE lecture only.
List of
Lectures
Date 
Topic 
Description 
Relevant
Reading 
01/16/2018 
Introduction 
Course focus, prerequisites,
what will be covered, what is expected 

01/18/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 
Scribes #2
[Pandey] Section 1.3
[PassShelat] Scribe note pdf 
01/23/2018 
One Way
Functions  I 
Definitions, motivation 
Scribes #3
[Pandey] Chapter 2
[Jain] Scribe note pdf 
01/25/2018 
One Way
Functions  II 
Candidate
construction, Yao’s theorem 
Scribes #4
[Pandey] Chapter 2
[Jain] Scribe note pdf 
01/30/2018 
Guest Lecture: Connected Vehicle Security: Successes and Challenges. 


02/01/2018 
Hard Core
Predicates 
Definition,
construction, GoldreichLevin theorem 
Scribes #5
[Pandey] Chapter 3
[Jain] Scribe note pdf 
02/06/2018 
Pseudorandomness – I 
Pseudorandom generators
(PRG), computational indistinguishability 
Chapter 4
[Jain] Scribe note pdf 
02/08/2018 
Pseudorandomness – II 
Constructing
PRGs 
Scribe note pdf 

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, LWE based encryption 


MAC and Hash Functions 



Digital Signatures 



Midterm 



Midterm / homework Solutions 



Bitcoin 
What are
Blockchains, how mining works 


Altcoins 
Other
interesting Blockchains and cryptocurrencies, differences from Bitcoin, how
they work 


Applications and Limitations of Current Blockchains 



ZeroKnowledge
Proofs – I 
What is
zeroknowledge (ZK), notion of simulation, an example 


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


ZeroKnowledge
Proofs – III 
ZK proofs of
honesty, noninteractive ZK, ZK proofs for cryptocurrencies (such as ZCash) 


Secure
Computation – I 
Coinflipping
over the internet 


Secure
Computation – II 
Yao’s
millionaire problem, oblivious transfer 


Secure
Computation – III 
Yao’s
garbled circuits 


Reviews of
Material Covered 


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