Cryptology ePrint Archive: Report 2018/470

The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO

Thomas Agrikola and Geoffroy Couteau and Dennis Hofheinz

Abstract: 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).

Category / Keywords: foundations / indistinguishability obfuscation, extremely lossy functions, subexponential assumptions

Original Publication (with major differences): IACR-PKC-2020

Date: received 17 May 2018, last revised 23 Jan 2020

Contact author: thomas agrikola at kit edu, thomas agrikola at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200123:123800 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]