Spring 2018


15503:  Introduction to Cryptography



Vipul Goyal




TR 3pm – 4:20pm


GHC 4101


Yanzun Huang <yanzunh@andrew.cmu.edu>


Vipul at cmu.edu

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




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:


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





Relevant Reading



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

Course basics


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

Definition, candidate constructions



Hard Core Predicates

Definition, construction, Goldreich-Levin theorem



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



Secret Sharing

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



Hash Functions

Collision-resistant 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




What are Blockchains, how mining works




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



Zero-Knowledge Proofs – I

What is zero-knowledge (ZK), notion of simulation, an example



Zero-Knowledge Proofs – II

Commitment schemes, ZK for any NP statement



Zero-Knowledge Proofs – III

ZK proofs of honesty, non-interactive ZK, ZK proofs for cryptocurrencies (such as ZCash)



Secure Computation – I

Coin-flipping over the internet



Secure Computation – II

Yao’s millionaire problem, oblivious transfer



Secure Computation – III

Yao’s garbled circuits



Non-malleable 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: