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

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

 

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:

 

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

 

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

 

01/23/2018

One Way Functions

Definition, candidate constructions

 

01/25/2018

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

 

 

Bitcoin

What are Blockchains, how mining works

 

 

Alt-coins

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: