Instructor: 



Time: 
TR
3pm – 4:20pm 
Location: 
GHC
4101 
TA 
Yanzun Huang <yanzunh@andrew.cmu.edu> 
Instructor 
Vipul
at cmu.edu 
Important: When sending me an email
about the course, make sure your title starts with "[Teach]"
(without the quotes). 
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:
3 Homeworks: 10%
each
Scribe notes: 25%
Note: each
student would be responsible for scribing 2 lectures
(10% each)
Midterm (in
class): 20%
Final (take
home): 25%
Class
participation: Extra credits
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 

01/23/2018 
One Way
Functions 
Definition,
candidate constructions 

01/25/2018 
Hard Core
Predicates 
Definition,
construction, GoldreichLevin theorem 


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


Secret Sharing 
Secret sharing
for AND, OR. Shamir secret sharing, threshold decryption 


Hash Functions 
Collisionresistant
hash functions (CRHF), constructions 


Digital
Signatures and Authentication 
Message Authentication
Codes (MAC), Digital Signatures, constructions 


Random Oracle
Model 
Why provable
security can sometimes be too costly, Random Oracle heuristic, constructions
for encryption/signature 


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 
Smart
contracts, smarts assets, future
research required on scalability, usability, anonymity 


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 


Nonmalleable
and CCA secure encryption 



Reviews of
Material Covered 


Useful Reading
There is no
required textbook for the course. Here are some general resources for
background on cryptography: