15356/15856:  Introduction to Cryptography

 

Download all lecture notes here. See YouTube lecture videos.

 

Important Note regard Change in Course Numbers: This course used to be 15503/15827. The course numbers have changed (however the content would remain the same). This course would still satisfy all requirements which 15503/15827 used to (e.g., for security and theory concentrations).

 

Instructor

Vipul Goyal <Vipul at cmu.edu>
Important: Please CC the TAs on ALL emails

Time

MW 1:30pm – 2:50pm

Location

CMU Remote (Zoom)

TAs

Lisa Masserova <elisawem@andrew.cmu.edu>,
Justin Raizes  <jraizes@andrew.cmu.edu>

Office Hours

TA: (Lisa) Tuesday 3pm to 4pm, (Justin) Wednesday 8:30am to 9:30am
Instructor: Monday 3pm to 4pm

 

NOTE: please join the class on piazza. 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 undergraduate students. It is cross-listed with 15-856. 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 (such as 15-251) or probability/discrete math (such as 21-228).

Currently the prerequisites for this course are 15-251 (OR) 21-228. However if you haven’t taken either of these course but you still believe you can handle the material (e.g., because you did very well in 15-151 or you have special interest in Crypto), please enroll in the waitlist and send the instructor an email.

 

Grading Policy

Grading policy for both the sections is the same:

Homeworks: 10% each
Midterm (in class): 25%
Final (take home): 25%
Class participation and attendance: extra credits (up to 5%)
Improve lecture notes: extra credits (up to 10%)

 

Exams

2 hour in class midterm: 10/26/2020 covering material up to 10/14/2020 (Tentative Time: 1:30pm to 3:30pm)

Final Exam (take home): 12/14/2020 noon to 12/15/2020 midnight (36 hours given to accommodate other finals)

 

Tentative List of Lectures

Date

Topic

Description

Relevant Reading

09/02/2020

Introduction

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

Lecture notes

09/09/2020

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

09/14/2020

One Way Functions

Definitions, motivation, candidate constructions

09/16/2020

Pseudorandomness – I

Pseudorandom generators (PRG), computational indistinguishability

09/21/2020

Pseudorandomness – II

Constructing PRGs, Hybrid arguments

 

09/23/2020

Pseudorandomness – III

Pseudorandom functions (PRF), constructions

 

09/28/2020

Secret-Key Encryption

Defining encryption, why all deterministic encryption schemes are insecure, construction using PRF, a warning regarding mauling attacks

 

09/30/2020

Number theory and hardness assumptions

Groups, Euler’s function, discrete log problem, RSA function

 

10/05/2020

Key Agreement

Diffie-Hellman Key exchange, proof of security

 

10/07/2020

Public-Key Encryption – I

Definition, trapdoor permutations, RSA based construction

 

10/12/2020

Public-Key Encryption – II

El-Gamal encryption, others

 

10/14/2020

MAC and Hash Functions

Message Authentication Codes (MAC), Collision-resistant hash functions (CRHF), constructions

 

10/19/2020

Digital Signatures

Message Digital Signatures, constructions

 

10/21/2020

Secret Sharing

XOR secret sharing, Shamir Secret Sharing, Applications

 

10/26/2020

In Class Midterm (2 hours)

Covers material up to 10/09, Open book

 

10/28/2020

Midterm/Homework Solutions

Solutions from Midterm and selected homework problems

 

 

 

 

 

11/02/2020

Blockchains - I

What are Blockchains, how mining works

 

 11/04/2020

Blockchains - II

Merkle Tree, Smart Contracts, applications and limitations of Bitcoins

 

 11/09/2020

Blockchains - III

Other interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains

 

 11/11/2020

Zero-Knowledge Proofs – I

What is zero-knowledge (ZK), notion of simulation, Graph Isomorphism

 

 11/16/2020

Zero-Knowledge Proofs – II

Commitment schemes

 

 11/18/2020

Zero-Knowledge Proofs – III

ZK for any NP statement

 

 11/23/2020

Secure Computation – I

Yao's millionaire problem, 1-out-of-2 oblivious transfer

 

 11/30/2020

Secure Computation – II

Coin-Flipping, ZK proofs of honesty, secure computation for small inputs

 

 12/02/2020

Secure Computation – III

Yao’s garbled circuits, additional topics

 

12/09/2020 

Finals Preparation

 

 

 

 

Useful Reading

Look at previous versions of this course for a list of topics covered + lecture notes:

Fall 2019: Introduction to Cryptography

Spring 2018: Introduction to Cryptography  (15503 and 15827)   (lecture notes available online)

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