Abstract
We describe a new approach to indistinguishability obfuscation, which yields candidate schemes that are secure under assumptions having a "circular security" flavor. Furthermore the approach is relatively simple to describe and can be instantiated using LWE-style techniques, which makes our candidates presumably post-quantum secure.
We start by reducing the task of constructing iO to that of constructing a "functional encoding scheme", which is a fully homomorphic encryption (FHE) scheme that allows us to give out succinct hints to reveal some specified function outputs. We then present two approaches for constructing functional encodings. The first approach relies on a new notion: "shielded randomness leakage" (SRL), which allows to leak "properly blurred" information about the randomness of FHE ciphertexts. While basic SRL security provably follows from LWE, the construction relies on circular variant where security is assumed to hold even if the FHE ciphertext encrypts its own secret key (or, more generally, is part of some key-cycle or key-randomness cycle). The second approach is based on obliviously sampling LWE instances without knowing the corresponding secrets. The scheme is secure under an assumption that involves circularity between a pseudorandom function (PRF) and the randomness of a ciphertext encrypting the PRF key. Both approaches rely on a packed variant of the Gentry-Sahai-Waters (GSW) FHE as a building block
The talk will be divided into three parts based roughly on the outline above. The first part presents the general framework and the reduction to functional encodings. The second part presents the SRL approach, and the third part presents the oblivious sampling approach. We will conclude by discussing the difference and similarities between the different flavors, and the plausibility of our assumptions.
Based on the following works:
[BDGM20a] Brakerski, Döttling, Garg, Malavolta: "Candidate Obfuscation from Homomorphic Encryption Schemes"
[GP20] Gay, Pass: "Indistinguishability Obfuscation from Circular Security"
[BDGM20b] Brakerski, Döttling, Garg, Malavolta: "Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices"
[WW20] Wee, Wichs: "Candidate Obfuscation via Oblivious LWE Sampling"