Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE.

Candidates of Indistinguishability Obfuscation (\(\mathsf {iO}\)) can be categorized as “direct” or “bootstrapping based”. Direct constructions rely on high degree multilinear maps [28, 29] and provide heuristic guarantees, while bootstrapping based constructions [2, 7, 33, 36, 38, 39] rely, in the best case, on bilinear maps as well as new variants of the Learning With Errors (\(\mathsf {LWE}\)) assumption and pseudorandom generators. Recent times have seen exciting progress in the construction of indistinguishability obfuscation (\(\mathsf {iO}\)) from bilinear maps (along with other assumptions) [2, 7, 33, 38].