Fall 2019

 

15356/15856:  Introduction to Cryptography

 

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

 

 

Time:

MW 1:30pm – 2:50pm

Location:

GHC 4215

TAs

Lisa Masserova <elisawem at andrew.cmu.edu>,

Yifan Song <yifans2 at andrew.cmu.edu>

Instructor

Vipul at cmu.edu

Office Hours

Important: Please CC the TAs on ALL emails

 

TA: Friday from 1:30pm to 2:30pm

Instructor: please drop by after the class on Monday

 

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: 11% each

Midterm (in class): 25%

Final (take home): 25%

Class participation and attendance: 6%

Extra credits: improve lecture notes (up to 10%)

 

  

Exams

2 hour midterm: 10/21/2019 covering material up to 10/09/2019 (Time: TBA)

Final Exam (take home): 12/12/2019 noon to 12/13/2019 midnight (36 hours given)

 

 

Tentative List of Lectures

 

Date

Topic

Description

Relevant Reading

08/28/2019

Introduction

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

09/04/2019

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/09/2019

One Way Functions - I

Definitions, motivation, candidate constructions

 

09/11/2019

Pseudorandomness – I

Pseudorandom generators (PRG), computational indistinguishability

 

09/16/2019

Pseudorandomness – II

Constructing PRGs

 

09/18/2019

Pseudorandomness – III

Pseudorandom functions (PRF), constructions

 

09/23/2019

Secret-Key Encryption

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

 

09/25/2019

Number theory and hardness assumptions

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

 

09/30/2019

Key Agreement

Diffie-Hellman Key exchange, proof of security

 

10/02/2019

Public-Key Encryption – I

Definition, trapdoor permutations, RSA based construction

 

10/07/2019

Public-Key Encryption – II

El-Gamal encryption, others

 

10/09/2019

MAC and Hash Functions

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

 

10/14/2019

Digital Signatures

Message Digital Signatures, constructions

 

10/16/2019

 

 

 

10/21/2019

In Class Midterm (2 hours)

Covers material up to 10/09, Open book

 

10/23/2019

Midterm/Homework Solutions

Solutions from Midterm and selected homework problems

 

10/28/2019

No class!

 

 

10/30/2019

Blockchains - I

What are Blockchains, how mining works

 

11/04/2019

Blockchains - II

Merkle Tree, Smart Contracts, applications and limitations of Bitcoins

 

11/06/2019

Blockchains - III

Other interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains

 

11/11/2019

Zero-Knowledge Proofs – I

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

 

11/13/2019

Zero-Knowledge Proofs – II

Commitment schemes, ZK for any NP statement

 

11/18/2019

Secure Computation – I

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

 

11/20/2019

Secure Computation – II

ZK proofs of honesty, 1-out-of-n oblivious transfer, secure computation for small inputs

 

11/25/2019

Secure Computation – III

Yao’s garbled circuits

 

11/27/2019

No class

Thanksgiving!

 

12/02/2019

Additional topics

 

 

12/04/2019

 

 

 

 

 

 

Useful Reading

 

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

 

Fall 2018: Introduction to Cryptography   (15503 and 15827)

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: