CS276: Cryptography (F2015)

Basics


Instructor(s): Alessandro Chiesa
Teaching Assistant(s): Manuel Sabin (msabin[at]eecs[dot]berkeley[dot]edu)
Time: TR 14.00-15.30
Location: 320 Soda Hall
Office Hours: MW 16:00-17:00 in 651 Soda Hall with Manuel

Course Description


This course offers a graduate introduction to cryptography, the science of securing data and computation against various adversarial behaviors. Topics covered include fundamental tools (such as encryption, pseudorandomness, digital signatures, zero knowledge, and secure computation) as well as a selection of tools with more advanced security properties (options include fully-homomorphic encryption, obfuscation, delegation protocols, and others).

The Piazza website is here.

Prerequisites


The official prerequisite is CS 170 (or equivalent). All students with "mathematical maturity" (ease with proofs, algorithms, elementary number theory, and discrete probability) and curiosity about cryptography are welcome.

Requirements


Completing the course requires completing four (4) homework assignments and a final project; in addition, students will rotate in producing scribe notes for the lectures. Grading will be based 60% on the problem sets, 30% on the final project, and 10% on class attendance and participation.

The TeX template for homework assigments is here, and the that for scribe notes is here.

Reading and Resources


This course has no required textbook, but essentially all the material covered in class can be found online. For example, the following references could be useful.

Books:

Lecture notes:

Also useful:

Assignments


Collaboration policy: You are free to collaborate with other students on the assignments, but you must turn in your individually written up solution, specifying the names of any collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used.

Schedule


# Date Topic Reading
1 2015.08.27
  • introduction to the course
  • negligible and noticeable functions
  • (uniform and non-uniform) probabilistic polynomial time algorithms
  • one-way functions (strong and weak)

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 2.2 , One-way functions: definitions
  • Introduction to Modern Cryptography
    • § 7.1, One-way functions

Papers:

Videos:

Scribe notes: by Brian Gluzman

2 2015.09.01
  • hardness amplification: from weak to strong one-way functions

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 2.3, Weak one-way functions imply strong ones

Videos:

Scribe notes: by David Dinh

3 2015.09.03
  • universal one-way functions
  • hardcore predicates
  • Goldreich–Levin predicate

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 2.4.1, Universal one-way function
    • § 2.5, Hard-core predicates
  • Introduction to Modern Cryptography
    • § 7.3, Hard-core predicates from one-way functions

Videos:

Scribe notes: by Akshayaram Srinivasan

4 2015.09.08
  • statistical vs computational indistinghuishability of distributions
  • hybrid argument
  • pseudorandomness generators (PRGs)
  • one-way permutations imply PRGs with 1-bit expansion

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 3.1, Motivating discussion
    • § 3.2, Computational indistinguishability
    • § 3.3.1, Standard definition of pseudorandom generators
    • § 3.4, Constructions based on one-way permutations
  • Introduction to Modern Cryptography
    • § 7.8, Computational indistinguishability
    • § 7.4, Constructing pseudorandom generators

Videos:

Scribe notes: by Tobias Boelter

5 2015.09.10
  • PRGs evaluated on independent seeds
  • PRGs with 1-bit expansion imply PRGs with polynomial expansion
  • pseudorandom functions

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 3.3.2, Increasing the expansion factor
    • § 3.6, Pseudorandom functions
  • Introduction to Modern Cryptography
    • § 7.5, Constructing pseudorandom functions

Videos:

Scribe notes: by Pratyush Mishra

6 2015.09.15
  • PRGs imply pseudorandom functions
  • pseudorandom permutations
  • Feistel permutations

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 3.6, Pseudorandom functions
    • § 3.7, Pseudorandom permutations
  • Introduction to Modern Cryptography
    • § 7.5, Constructing pseudorandom functions
    • § 7.6, Constructing (strong) pseudorandom permutations

Videos:

Papers:

Scribe notes: by Brian Gluzman

7 2015.09.17
  • Luby–Rackoff construction of pseudorandom permutations
  • commitment schemes
  • one-way permutations imply 1-bit commitment schemes

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 3.7, Pseudorandom permutations
    • § 4.4.1, Commitment schemes

Papers:

Scribe notes: by Rohan Mathuria

8 2015.09.22
  • 1-bit commitment schemes imply multi-bit commitment schemes
  • intro to encryption schemes
  • single-message perfect message indistinguishability
  • one-time pad and its limitations
  • single-message computational message indistinguishability

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 5.1, The basic setting
    • § 5.2, Definitions of security
  • Introduction to Modern Cryptography
    • § 2, Perfectly secret encryption
    • § 3.1, Computational security
    • § 3.2, Defining computationally secure encryption

Papers:

Videos:

Scribe notes: by Pratyush Mishra

9 2015.09.24
  • equivalence of message indistinguishability and semantic security
  • shrinking one-time pad's key with PRGs
  • multi-message computational message indistinguishability
  • security against chosen plaintext attacks

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 5.3.3, Private-key encryption schemes
    • § 5.4.3, Chosen plaintext attack
  • Introduction to Modern Cryptography
    • § 3.3, Constructing secure encryption schemes
    • § 3.4, Stronger security notions

Papers:

Videos:

Scribe notes: by Eleanor Cawthon

10 2015.09.29
  • PRFs imply security against chosen plaintext attacks
  • modes of encryption
  • security against CPA vs CCA1 vs CCA2

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 5.4.4, Chosen ciphertext attack
  • Introduction to Modern Cryptography
    • § 3.5, Constructing CPA-secure encryption schemes
    • § 3.6, Modes of operation
    • § 3.7, Chosen-ciphertext attacks

Papers:

Videos:

Scribe notes: by Joseph Hui

11 2015.10.01
  • message authentication codes
  • constructions based on PRFs
  • CPA security and MACs imply CCA2 security

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 6.1, The setting and definitional issues
    • § 6.3, Constructions of message authentication schemes
    • § 6.1.5.1, Augmenting the attack with a verification oracle
  • Introduction to Modern Cryptography
    • § 4.1, Message integrity
    • § 4.2, Message authentication codes - definitions
    • § 4.3, Constructing secure message authentication codes
    • § 4.4, CBC-MAC

Papers:

Videos:

Scribe notes: by David Fifield

12 2015.10.06
  • CPA security and MACs imply CCA2 security
  • combining CPA security and MACs in other (insecure) ways
  • collision-resistant functions
  • Merkle–Damgård transform

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 6.2.3, Constructing collision-free hashing functions
  • Introduction to Modern Cryptography
    • § 4.5, Authenticated encryption
    • § 5.1.1, Collision resistance
    • § 5.2, Domain extension: the Merkle–Damgård transform
    • § 5.4, Generic attacks on hash functions

Papers:

Videos:

Scribe notes: by Tongzhou Wang

13 2015.10.08
  • intro to public-key cryptography
  • public-key encryption schemes
  • trapdoor one-way permutations
  • TOWPs imply public-key encryption schemes
  • RSA as a TOWP
  • hybrid encryption

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 5.1.1, Private-key versus public-key schemes
    • § 5.1.2, The syntax of encryption schemes
    • § 5.3.4, Public-key encryption schemes
    • § 5.5.1, On using encryption schemes
  • Introduction to Modern Cryptography
    • § 11.1, Public-key encryption - an overview
    • § 11.2, Definitions
    • § 11.5, RSA encryption
    • § 13.1, Public-key encryption from trapdoor permutations

Papers:

Scribe notes: by Xingyou Song

14 2015.10.13
  • finish hybrid encryption
  • DDH assumption (and where it might hold)
  • ElGamal encryption scheme
  • CCA2 security in the asymmetric setting

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 5.5.3, On some popular schemes
  • Introduction to Modern Cryptography
    • § 8.3, Cryptographic assumptions in cyclic groups
    • § 11.3, Hybrid encryption and the KEM/DEM paradigm
    • § 11.4, CDH/DDH-based encryption

Papers:

Scribe notes: by Peter Manohar

15 2015.10.15
  • CCA2 security in the random oracle model
  • definition of signature schemes

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 6.1, The setting and definitional issues
  • Introduction to Modern Cryptography
    • § 11.5.5, A CCA-Secure KEM in the random-oracle model
    • § 12.1, Digital signatures - an overview
    • § 12.2, Definitions

Papers:

Scribe notes: by Lynn Chua

16 2015.10.20
  • one-time signatures
  • hash-then-sign paradigm
  • key refreshing

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 6.2, Length-restricted signature scheme
    • § 6.4.1, One-time signature schemes
  • Introduction to Modern Cryptography
    • § 12.2, The hash-and-sign paradigm
    • § 12.6.1, Lamport's signature scheme
    • § 12.6.2, Chain-based signatures

Papers:

Scribe notes: by Benjamin Caulfield

17 2015.10.22
  • from one-time signatures to full security
  • signatures in the random oracle model
  • signcryption

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 2
    • § 6.4.2, From one-time signature schemes to general ones
  • Introduction to Modern Cryptography
    • § 12.4.2, RSA-FDH
    • § 12.6.3, Tree-based signatures
    • § 12.9, Signcryption

Papers:

Scribe notes: by Willem Y. Van Eck

18 2015.10.27
  • interactive proofs
  • graph isomorphism is in IP
  • honest-verifier zero knowledge

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 4.1, Zero-knowledge proofs: motivation
    • § 4.2, Interactive proof systems
    • § 4.3, Zero-knowledge proofs: definitions

Papers:

Videos:

Scribe notes: by Pasin Manurangsi

19 2015.10.29
  • interactive proofs
  • honest-verifier zero knowledge
  • (malicious-verifier) zero knowledge
  • perfect zero knowledge for graph isomorphism

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 4.1, Zero-knowledge proofs: motivation
    • § 4.2, Interactive proof systems
    • § 4.3, Zero-knowledge proofs: definitions

Papers:

Videos:

Scribe notes: by Chenyang Yuan

20 2015.11.03
  • computational zero knowledge for graph 3-coloring

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 4.4, Zero-knowledge proofs for NP

Papers:

Scribe notes: by Praagya Singh

21 2015.11.05
  • computational zero knowledge for graph 3-coloring
  • zero knowledge is not closed under parallel composition
  • witness indistinguishability
  • parallel composition for witness indistinguishability

Lecture notes:

Textbooks:

  • Foundations of Cryptography, Volume 1
    • § 4.4, Zero-knowledge proofs for NP
    • § 4.5.4, Zero-Knowledge and parallel Composition
    • § 4.6, Witness indistinguishability and hiding

Papers:

22 2015.11.10
  • VBB obfuscation for TMs and circuits
  • impossibility of VBB obfuscation

Lecture notes:

Papers:

23 2015.11.12
  • indistinguishability obfuscation (iO)
  • witness encryption
  • iO implies witness encryption
  • iO and OWFs imply public-key encryption
  • best-possible obfuscation (BPO)
  • VBBO implies BPO
  • BPO vs IO

Lecture notes:

Papers:

Videos:

Scribe notes: by Joseph Hui

24 2015.11.17
  • iO amplification: from NC1 to all circuits
  • iO and coRP != NP implies OWFs

Lecture notes:

Papers:

Videos:

Scribe notes: by Linyue Zhu

25 2015.11.19
  • iO and coRP != NP implies OWFs
  • VBB implies OWFs
  • differing-inputs obfuscation
  • extractable witness encryption

Papers:

Videos:

Scribe notes: by Akshay Ramachandran

26 2015.11.24

Class project presentations:

  • Tobias Boelter, Akshay Srinivasan
  • Alex Irpan
  • Tongzhou Wang
  • Brian Gluzman
  • Pratyush Mishra
  • Gil Lederman
X 2015.11.26

No class.

No class.

27 2015.12.01

Class project presentations:

  • Joseph Hui, Chenyang Yuan
  • Rohan Mathuria
  • Akshay Ramachandran
  • Qi Zhong, Linyue Zhu
28 2015.12.03

Class project presentations:

  • Lynn Chua, Pasin Manurangsi
  • David Dinh
  • Peter Manohar, Xingyou Song
  • Willem Van Eck
  • Ben Caulfield
  • Praagya Singh

Parting materials: