Paper 2018/470

The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO

Thomas Agrikola, Geoffroy Couteau, and Dennis Hofheinz


We consider the problem of removing subexponential reductions to indistinguishability obfuscation (iO) in the context of obfuscating probabilistic programs. Specifically, we show how to apply complexity absorption (Zhandry, Crypto 2016) to the recent notion of probabilistic indistinguishability obfuscation (piO, Canetti et al., TCC 2015). As a result, we obtain a variant of piO which allows to obfuscate a large class of probabilistic programs, from polynomially secure indistinguishability obfuscation and extremely lossy functions. Particularly, our piO variant is able to obfuscate circuits with specific input domains regardless of the performed computation. We then revisit several (direct or indirect) applications of piO, and obtain -- a fully homomorphic encryption scheme (without circular security assumptions), -- a multi-key fully homomorphic encryption scheme with threshold decryption, -- an encryption scheme secure under arbitrary key-dependent messages, -- a spooky encryption scheme for all circuits, -- a function secret sharing scheme with additive reconstruction for all circuits, all from polynomially secure iO, extremely lossy functions, and, depending on the scheme, also other (but polynomial and comparatively mild) assumptions. All of these assumptions are implied by polynomially secure iO and the (non-polynomial, but very well-investigated) exponential DDH assumption. Previously, all the above applications required to assume the subexponential security of iO (and more standard assumptions).

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2020
indistinguishability obfuscationextremely lossy functionssubexponential assumptions
Contact author(s)
thomas agrikola @ kit edu
thomas agrikola @ gmail com
2020-01-23: last of 3 revisions
2018-05-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Agrikola and Geoffroy Couteau and Dennis Hofheinz},
      title = {The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO},
      howpublished = {Cryptology ePrint Archive, Paper 2018/470},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.