Spring 2018

15503: Introduction to Cryptography

Instructor:	Vipul Goyal
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 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 (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, non-negligible means noticeable.

HW2.pdf

HW3.pdf Note: in problem 3, for the scheme that doesn't satisfy the binding property, it still accepts the committed message.

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	Course basics
01/18/2018	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	Scribes #2 [Pandey] Section 1.3 [Pass-Shelat] 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.		cv_security_2018
02/01/2018	Hard Core Predicates	Definition, construction, Goldreich-Levin 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
02/13/2018	Pseudorandomness – III	Pseudorandom functions (PRF), constructions	Scribe note pdf
02/15/2018	Secret-Key Encryption	Defining encryption, why all deterministic encryption schemes are insecure, construction using PRF, a warning regarding mauling attacks	Scribe note pdf
02/20/2018	Number theory and hardness assumptions	Groups, Euler’s function, discrete log problem, RSA function	Scribe note pdf
02/22/2018	Key Agreement	Diffie-Hellman Key exchange, proof of security	Scribe note pdf
02/27/2018	Public-Key Encryption – I	Definition, trapdoor permutations, RSA based construction	Scribe note pdf
03/01/2018	Public-Key Encryption – II	El-Gamal encryption, LWE based encryption	Scribe note pdf
03/06/2018	MAC and Hash Functions	Message Authentication Codes (MAC), Collision-resistant hash functions (CRHF), constructions	Scribe note pdf
03/08/2018	Digital Signatures	Message Digital Signatures, constructions	Scribe note pdf
03/20/2018	Midterm	Note: Open book
03/22/2018	Midterm / homework Solutions
03/27/2018	Bitcoin - I	What are Blockchains, how mining works	Scribe note pdf
03/29/2018	Bitcoin - II	Merkle Tree, Smart Contracts, applications and limitations of Bitcoins	Scribe note pdf
04/03/2018	Alt-coins	Other interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains	Scribe note pdf
04/05/2018	Guest lecture: Proof of stake and Byzantine	Proof of stake based chains, AlgoRand	Scribe note pdf
04/10/2018	Zero-Knowledge Proofs – I	What is zero-knowledge (ZK), notion of simulation, Graph Isomorphism	Scribe note pdf
04/12/2018	Zero-Knowledge Proofs – II	Commitment schemes, ZK for any NP statement	Scribe note pdf
04/17/2018	Zero-Knowledge Proofs – III	Non-interactive ZK, ZK proofs for cryptocurrencies (such as ZCash)	Scribe note pdf
04/24/2018	Secure Computation – I	Yao's millionaire problem, 1-out-of-2 oblivious transfer	Scribe note pdf
04/26/2018	Secure Computation – II	ZK proofs of honesty, 1-out-of-n oblivious transfer, secure computation for small inputs	Scribe note pdf
05/01/2018	Secure Computation – III	Yao’s garbled circuits	Scribe note pdf
05/03/2018	Additional topics	Fully homomorphic encryption, non-malleable commitments, position-based cryptography, identity based encryption, and attribute based encryption

Useful Reading

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

• Recommended Lecture notes 1: Scribes / Lecture notes by Omkant Pandey
• Recommended Lecture notes 2: Lecture notes by Abhishek Jain
• Other lecture notes: Pass-Shelat, Bellare-Goldwasser
• Katz and Lindell's book: Introduction to Modern Cryptography (not free)
• Rosulek's upcoming book: The Joy of Cryptography
• Boneh and Shoup's upcoming book: A Graduate Course in Applied Cryptography