Fall 2018

 

15503/15827:  Introduction to Cryptography

 

Instructor:

Vipul Goyal

 

 

Time:

MW 1:30pm – 2:50pm

Location:

GHC 4303

TA

Yifan Song <yifans2@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 1:30pm to 2:30pm (GHC 4303)

Instructor: please setup an appointment by email or drop by after the class

 

NOTE: Course starts the week of 09/03 to allow for incoming PhD orientation course

 

NOTE: please join the class on piazza by searching for 15-503 or 15-827. 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 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:

4 Homeworks: 8% each

Scribe notes: 18%

Note: each student would be responsible for scribing 2 lectures (9% each)

Midterm (in class): 25%

Final (take home): 25%

Class participation: Extra credits

 

 

Exams

2 hour midterm: 10/22/2018 (1:30 to 3:30) covering material upto 10/10/2018

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

 

 

Homework

Will be posted here periodically

 

 

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.

 

 

List of Lectures

 

Date

Topic

Description

Relevant Reading

09/05/2018

Introduction

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

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

 

09/12/2018

One Way Functions - I

Definitions, motivation

 

09/17/2018

One Way Functions - II

Candidate construction, Hard core predicates

 

 

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, others

 

10/22/2018

In Class Midterm (2 hours)

Covers material up to 10/10, Open book

 

10/24/2018

Midterm/Homework Solutions

Solutions from Midterm and selected homework problems

 

 

MAC and Hash Functions

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

 

 

Digital Signatures

Message Digital Signatures, constructions

 

 

Blockchains - I

What are Blockchains, how mining works

 

 

Blockchains - II

Merkle Tree, Smart Contracts, applications and limitations of Bitcoins

 

 

Blockchains - III

Other interesting Blockchains and cryptocurrencies, GHOST, DAG based blockchains

 

 

Zero-Knowledge Proofs – I

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

 

 

Zero-Knowledge Proofs – II

Commitment schemes, ZK for any NP statement

 

 

Secure Computation – I

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

 

 

Secure Computation – II

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

 

 

Secure Computation – III

Yao’s garbled circuits

 

 

Additional topics

 

 

 

 

 

Useful Reading

 

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