COS 597C - Recent Developments in Program Obfuscation (Fall 2016)
|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 |
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 ||LN2|
| 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|
| 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 ||LN13|
| 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 ||LN17|
| 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 || |
. Due September 19
(Updated Oct 3). Due October 6
. New Due Date: Due November 15
. 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 Assignment
- 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.