Paper 2019/308

Obfuscation from Polynomial Hardness: Beyond Decomposable Obfuscation

Yuan Kang, Chengyu Lin, Tal Malkin, and Mariana Raykova


Every known construction of general indistinguishability obfuscation ($\mathsf{i}\mathcal{O}$) is either based on a family of exponentially many assumptions, or is based on a single assumption -- e.g.~functional encryption ($\mathsf{FE}$) -- using a reduction that incurs an exponential loss in security. This seems to be an inherent limitation if we insist on providing indistinguishability for any pair of functionally equivalent circuits. Recently, Liu and Zhandry (TCC 2017) introduced the notion of decomposable $\mathsf{i}\mathcal{O}$ ($\mathsf{d}\mathcal{O}$), which provides indistinguishability for a restricted class of functionally equivalent circuit pairs, and, as the authors show, can be constructed from polynomially secure $\mathsf{FE}$. In this paper we propose a new notion of obfuscation, termed $\mathsf{radi}\mathcal{O}$ (repeated-subcircuit and decomposable obfuscation), which allows us to obfuscate a strictly larger class of circuit pairs using a polynomial reduction to $\mathsf{FE}$. Our notion builds on the equivalence criterion of Liu and Zhandry, combining it with a new incomparable criterion to obtain a strictly larger class.

Available format(s)
Publication info
Published elsewhere. Minor revision.SCN 2018: Security and Cryptography for Networks
indistinguishability obfuscationfunctional encryption
Contact author(s)
yjk2106 @ columbia edu
chengyu @ cs columbia edu
2019-03-20: revised
2019-03-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuan Kang and Chengyu Lin and Tal Malkin and Mariana Raykova},
      title = {Obfuscation from Polynomial Hardness: Beyond Decomposable Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2019/308},
      year = {2019},
      doi = {10.1007/978-3-319-98113-0_22},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.