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 |

- 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.

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 |

Homework 1 (Updated Oct 3). Due October 6

Homework 2.

Homework 3. Due December 6

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.

- 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.