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. Reading materials will be posted throughout the
class. Hower, the following are good references:
A good
overview on secure multiparty computation is available in
this
free textbook
Grading
There will be four homework assignments (to be solved in teams of two students), and a take home final (to be solved individually). The grading split will be, roughly: Homework (60%), Final (30%), Participation (10%)
Schedule
This is a tentative schedule meant to give
an overview of the topics we are going to cover. It will be expanded/refined as we proceed through the quarter.
Wk  Date  Lecture contents 
Reading 
1  3/27 
Introduction
 Formal details
 Examples of Cryptographic Applications
 Introduction to games and advantages


 3/29 
Unpredictability and Pseudorandomness I
 Generic attacks against UFCMA security
 Computational efficiency
 Concrete vs asymptotic security
 Reductions: Keyrecovery, random messages, and multiple verification queries


2  4/3 
Unpredictability and Pseudorandomness II
 Pseudorandom functions
 PRFs are good MACs


 4/5 
Construction pseudorandom functions
 Range Extension and the Hybrid Argument
 AES and practical PRFs


3  4/10 
Symmetric Encryption I
 Modes of operation
 ECB Insecurity
 INDR and INDCPA Security
 CTR and its security


 4/12 
Symmetric Encryption II
 Integrity attacks
 Plaintext and ciphertext integrity
 Generic composition: EncryptthenMAC
 WegmanCarter MACs


4  4/17 
Groups and Number Theory
 Finite Groups
 Modular Arithmetic
 Cyclic Groups
 Exponentiations and Discrete Logarithms
 Universal Hash Functions from Modular Arithmetic


 4/19 
Hard Problems in Groups
 The hardness of the DL problem
 Elliptic Curves
 DiffeHellman Key Exchange
 The DDH Assumption


5  4/24 
Publickey Encryption I
 INDCPA Security
 ElGamal Encryption
 One vs Many Encryptions


 4/26 
Publickey Encryption II
 RSA
 Trapdoor Functions
 Hardcore Functions
 INDCPA security from Trapdoor Functions


6  5/1 
ChosenCiphertext Security
 Motivation & definition
 The CramerShoup Lite Encryption Scheme


 5/3 
CCA Security & Random Oracles
 Cramer Shoup wrap up
 The Random Oracle Model
 CCA security from TDFs and random oracles


7  5/8 
Digital Signatures
 UFCMA security
 FullDomain Hash Signatures
 Authenticated Key Exchange


 5/10 
LatticeBased Cryptography
 A brief introduction to lattices and shortest vectors
 The LWE assumption
 Regev Encryption


8  5/15 
FullyHomomorphic Encryption
 The GSW Construction
 PIR from FHE


 5/17 
MultiParty Computation I
 2PC Security Definition
 Garbled Circuits and OT


9  5/22 
MultiParty Computation II
 2PC Wrapup: Point and permute
 Secret Sharing and the GWM Protocol
 Beaver Triples


 5/24 
ZeroKnowledge I
 Proving Knowledge of Discrete Logarithms and the Schnorr Protocol
 General formalism
 Proofs of homomorphim


10  5/29 
Memorial Day (No class)


 5/31 
ZeroKnowledge II
 Zeroknowledge proofs for NP
 Commitment Schemes
 The FiatShamir Transform and NIZKs

