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 assumptions from cryptographic constructions based on indistinguishability obfuscation (iO). 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. 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

Date: received 17 May 2018, last revised 25 May 2018

Contact author: thomas agrikola at kit edu

Available format(s): PDF | BibTeX Citation

Version: 20180525:090855 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]