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:

Formal definitions of obfuscation
Applications to cryptography
Current obfuscators and attacks on them
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	[BGIRSVY'01]	LN2
Part I: Applications of Obfuscation
3 - Th, 9/22	iO ==> digital signatures	[SW'13]	LN3
4 - Tu, 9/27	iO ==> public key encryption	[SW'13]	LN4
5 - Th, 9/29	iO ==> multiparty key agreement	[BZ'14]	LN5
6 - Tu, 10/4	iO ==> broadcast encryption	[BZ'14]	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	Tools for building obfuscation: multilinear maps	[GGH'13]	LN11
12 - Tu, 10/25	Obfuscation in the "generic multilinear map model"	[BMSZ'16]	LN12
13 - Th, 10/27	Obfuscation in the "generic multilinear map model"	[BMSZ'16]	LN13
Tu, 11/1	No Class - Fall recess
Th, 11/3	No Class - Fall recess
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	Defending iO from attacks	[GMS'16] [MSZ'16b]	LN17
Part III: Obfuscation in the Complexity Landscape
18 - Tu, 11/22	iO vs OWF	[KMNPRY'14]	LN18
Th, 11/24	No Class - Thanksgiving
19 - Tu, 11/29	iO ==> PPAD hardness	[BPR'14]
20 - Th, 12/1	Limits of iO		LN20
21 - Tu, 12/6	Barriers to building iO from traditional tools		LN21
22 - Th, 12/8	The plausibility of diO		LN22
23 - Tu, 12/13	Student Presentations
24 - Th, 12/15	Student Presentations

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:

Project Proposal: Monday, November 14, 11:59pm
Presentation: In class during the last week of class.
Project Report: Dean's Date, Tuesday, January 17, 11:59pm.

Some Open Problems

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

Devise a plausible security definition for obfuscation that captures the goal of preventing reverse engineering of software.
New applications of iO/improved constructions of existing applications. Concrete ideas will be given throughout Part I of the course.
Devise an attack on iO candidates over CLT'13 multilinear maps or GGH'15 multilinear maps. For CLT'13 attacks, see here and here. For GGH'15 attacks, see here.
Devise a classical polynomial-time attack on GGH13 multilinear maps that does not fit within the "refined generic multilinear map model."
Construct diO for a wider class of circuits than just those that differ on a polynomial number of points, assuming just iO and possibly other basic crypto tools.
Prove that diO for general circuits does not exist. See here and here for a start.
Construct iO for Turing Machines with unbounded inputs, or prove it is impossible.
Formalize the intuition that reducing iO to a single "simple" assumption requires an exponential loss in the reduction.