Paper 2020/415

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

Shweta Agrawal and Alice Pellet-Mary


Candidates of Indistinguishability Obfuscation (iO) can be categorized as ``direct'' or ``bootstrapping based''. Direct constructions rely on high degree multilinear maps [GGH13,GGHRSW13] and provide heuristic guarantees, while bootstrapping based constructions [LV16,Lin17,LT17,AJLMS19,Agr19,JLMS19] rely, in the best case, on bilinear maps as well as new variants of the Learning With Errors (LWE) assumption and pseudorandom generators. Recent times have seen exciting progress in the construction of indistinguishability obfuscation (iO) from bilinear maps (along with other assumptions) [LT17,AJLMS19,JLMS19,Agr19]. As a notable exception, a recent work by Agrawal [Agr19] provided a construction for iO without using any maps. This work identified a new primitive, called Noisy Linear Functional Encryption (NLinFE) that provably suffices for iO and gave a direct construction of NLinFE from new assumptions on lattices. While a preliminary cryptanalysis for the new assumptions was provided in the original work, the author admitted the necessity of performing significantly more cryptanalysis before faith could be placed in the security of the scheme. Moreover, the author did not suggest concrete parameters for the construction. In this work, we fill this gap by undertaking the task of thorough cryptanalytic study of NLinFE. We design two attacks that let the adversary completely break the security of the scheme. To achieve this, we develop new cryptanalytic techniques which (we hope) will inform future designs of the primitive of NLinFE. From the knowledge gained by our cryptanalytic study, we suggest modifications to the scheme. We provide a new scheme which overcomes the vulnerabilities identified before. We also provide a thorough analysis of all the security aspects of this scheme and argue why plausible attacks do not work. We additionally provide concrete parameters with which the scheme may be instantiated. We believe the security of NLinFE stands on significantly firmer footing as a result of this work.

Note: The parameters provided at the end of Section 7 have been slightly updated since the published version. The ones in the present article are the correct ones.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Noisy linear FEObfuscation
Contact author(s)
shweta a @ gmail com
alice pellet-mary @ ens-lyon org
2020-04-13: received
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Alice Pellet-Mary},
      title = {Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE},
      howpublished = {Cryptology ePrint Archive, Paper 2020/415},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.