General description
Cryptography delivers tools for protecting
confidentiality and integrity of data. These tools are already used at
scale to protect billions of daily online transactions, e.g., within
the TLS protocol, in endtoend encrypted messaging applications
(like Signal), and in a myriad of other applications. At the same
time, modern cryptography has developed a number of tools whose end goal extends
beyond that of solely protecting confidentiality and integrity, such
as zeroknowledge proofs, secure multiparty computation, and fullyhomomorphic encryption. In addition to its benefits to computer security, a unique aspect of modern cryptography is how it interfaces with theoretical computer science  both by adopting tools and techniques, but also by inspiring problems and directions.
This course gives a comprehensive introduction to cryptography. The focus is on (1) understanding how existing tools work; (2) how to formalize the security goals they achieve, and (3) how to prove that they achieve these goals. The class will aim to be both of interest to theory students, as well as to a broader audience interested in using cryptography in a sound way. In partcular, a main objective is exposure to the paradigm of provable security which allows us to reason rigorously about cryptographic security.
Topics will include (tentative): Cryptographic pseudorandomness, encryption (secret and publickey), keyagreement, authentication, hash functions, digital signatures, basics of postquantum cryptography, introduction to cryptographic protocols (multiparty computation and zeroknowledge proofs)
Required background: Students are expected to be ready to
understand and write mathematical definitions and proofs. Exposure to basic probability, discrete mathematics, and theory of computing is also expected. (If in doubt, please reach out to the instructor.)
Resources
There is no mandatory
textbook. Notes and reading material will be posted
here.
The following is a list of great resources to reference to (most of these are available for free):
Grading
(This is subject to minor changes, as we adapt to the challenges of online teaching.)
There will be four homework assignments, and one takehome
final exam. Each student is responsible for scribing
the note for one class, which will be posted online.
Each homework accounts for 15% of points, the
final accounts for 30% of points. Participation is 10%. Your final grade will be
based on the weighted total points.
Schedule
This is a tentative schedule meant to give
an overview of the topics we are going to cover. It will be expanded as proceed in the quarter.
Wk  Date  Lecture contents 
Assignments / Reading 
1  03/30 
Introduction
 Welcome / organizational details
 What is cryptography?
 Example applications
 The provable security paradigm
[Slides Lecture 1]


 04/01 
Symmetric encryption: Perfectsecrecy, informationtheoretic vs computational security
 Syntax of symmetric encryption
 Shannon secrecy and perfect secrecy
 Onetime pad and keylengt lower bound for perfect secrecy
[Slides Lecture 2] [Scribed Notes]


2  04/06 
Pseudorandom Generators I
 Definition of PRGs
 Asymptotic vs Concrete Security
[Slides Lecture 3] [Scribed Notes]


 04/08 
Pseudorandom Generators II
 Refresher: Group theory and number theory
 The Discrete Logarithm Problem
 BlumMicali PRG
[Slides Lecture 4] [Scribed Notes]


3  04/13 
Pseudorandom Generators III
 Hybrid arguments
 BlumMicali PRG  security proof
[Slides Lecture 5] [Scribed Notes]


 04/15 
Pseudorandom Functions I
 Oneway functions and PRGs
 PRG expansion
 PRF definition and the GGM construction
[Slides Lecture 6] [Scribed Notes]


4  04/20 
Symmetric Encryption
 Block ciphers
 PRP security
 The Switching Lemma
[Slides Lecture 7] [Scribed Notes]


 04/22 
Symmetric Encryption
 Definition of INDCPA security
 Randomized countermode encryption
 Proof of INDCPA security for countermode
[Slides Lecture 8] [Scribed Notes]


5  04/27 
Message Authentication & Authenticated Encryption
 Padding Oracle Attacks
 Messageauthentication codes / UFCMA security
 PRFs and MACs
[Slides Lecture 9] [Scribed Notes]


 04/29 
Authenticated Encryption
 Universal Hashing
 MAC construction
 INTCTXT
 EncryptthenMAC
[Slides Lecture 10] [Scribed Notes]


6  05/04 
Publickey encryption I
 DiffieHellman Key Exchange
 The DDH assumption
 ElGamal Encryption
[Slides Lecture 11] [Scribed Notes]


 05/06 
Publickey Encryption II
 Trapdoor Functions
 The RSA Trapdoor Function
 Encryption from Trapdoor Functions
 Definition of CCA security
[Slides Lecture 12] [Scribed Notes]


7  05/11 
CCASecure Encryption
 Trapdoorfunction based CCAsecure encryption
 The random oracle model
[Slides Lecture 13] [Scribed Notes]


 05/13 
Digital Signatures
 Definition and UFCMA security
 The FullDomain Hash (FDH)
 Security of FDH in the randomoracle model
 Introduction to Authenticated KeyExchange
[Slides Lecture 14] [Scribed Notes]


8  05/18 
Latticebased cryptography I
 Certificates via Digital Signatures
 Introduction to LWE
 Regev's scheme
[Slides Lecture 15]


 05/20 
Latticebased cryptography II
 Fullyhomomorphic encrytpion
 The GSW construction
 Noise management and bootstrapping
[Slides Lecture 16]


9  05/25 
No Class: Memorial Day!


 05/27 
Zeroknowledge Proofs
 Definition of Interactive Proofs and ZeroKnowledge
 The GMR protocol for 3coloring
 Schnorr Proof of Knowledge for Discrete Logarithm
[Slides Lecture 17] [Scribed Notes]


10  06/01 
MultiParty Computation I
 Proofofknolwedge for Discrete Logarithm HVZK
 The FiatShamir Transform
 Definition of twoparty computation
 Oblivious Transfer
 A protocol for AND
[Slides Lecture 18] [Scribed Notes]


 06/03 
MultiParty Computation II
 Yao's Protocol
 Introduction to MultiParty Computation
[Scribed Notes]

