COS 597C - Recent Developments in Program Obfuscation (Fall 2016)

Course Information

Instructor: Mark Zhandry
Time: TuTh 11:00am - 12:20pm
Location: Friend Center 111
Office Hours: By appointment
Grading: Based on homeworks every 2-3 weeks, scribing some lectures, final project

Course Description

A program obfuscator is a compiler that scrambles a program to make it unintelligible. Recently breakthroughs have lead to the development of obfuscators with very strong security properties, which have yielded numerous applications to cryptography and compter science theory in general. This course will cover a selection of these recent developments, including:
  1. Formal definitions of obfuscation
  2. Applications to cryptography
  3. Current obfuscators and attacks on them
  4. Obfuscation in the complexity landscape - P vs NP, PPAD hardness, relation to basic crypto primitives, etc.
Prerequisites: Basic familiarity with computability and complexity theory, such as that covered in COS 340 (Turing Machines, P vs NP, NP-completeness, etc). No prior knowledge of cryptography is assumed, though basic familiarity with crypto concepts (one-way functions, encryption, digital signatures, public key vs secret key cryptography, etc) is recommended.

Tentative Schedule (subject to change)

>
Lecture Topic Readings Scribe Notes
1 - Th, 9/15 Course introduction, definitions of obfuscation: indistinguishability obfuscation (iO), virtual black box obfuscation (VBB), and more [BGIRSVY'01] LN1
2 - Tu, 9/20 Impossibility for VBB obfuscation LN2
Part I: Applications of Obfuscation
3 - Th, 9/22 iO ==> digital signatures [SW'13] LN3
4 - Tu, 9/27 iO ==> public key encryption LN4
5 - Th, 9/29 iO ==> multiparty key agreement [BZ'14] LN5
6 - Tu, 10/4 iO ==> broadcast encryption LN6
7 - Th, 10/6 iO ==> fully homomorphic encryption [CLTV'14] LN7
8 - Tu, 10/11 iO ==> order revealing encryption LN8
9 - Th, 10/13 iO ==> zero knowledge [BP'14] LN9
Part II: Constructions and Attacks
10 - Tu, 10/18 Tools for building obfuscation: multilinear maps[GGH'13] LN10
11 - Th, 10/20 LN11
12 - Tu, 10/25 Obfuscation in the "generic multilinear map model" [BMSZ'16] LN12
13 - Th, 10/27
Tu, 11/1 No Class - Fall recess
Th, 11/3
14 - Tu, 11/8 Class Cancelled
15 - Th, 11/10 Attacks on multilinear maps, iO [MSZ'16a]
16 - Tu, 11/15 Defending iO from attacks [GMS'16] [MSZ'16b]
17 - Th, 11/17
Part III: Obfuscation in the Complexity Landscape
18 - Tu, 11/22 iO vs OWF[KMNPRY'14]
Th, 11/24 No Class - Thanksgiving
19 - Tu, 11/29 iO ==> PPAD hardness [BPR'14]
20 - Th, 12/1 Limits of iO
21 - Tu, 12/6 Barriers to building iO from traditional tools
22 - Th, 12/8 The plausibility of diO
23 - Tu, 12/13 Student Presentations
24 - Th, 12/15

Homework Assignments

Homework 0. Due September 19
Homework 1 (Updated Oct 3). Due October 6
Homework 2. New Due Date: Due November 15
Homework 3. Due December 6

Instructions for Homeworks: Please type up your solutions (LaTeX preferred). Either email your solutions to (preferred) or print them out and hand them in during class by the due date.

Final Project

Final Project Assignment

Due Dates:

Some Open Problems

Here are some open problems that could be the basis for a final project: