The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
METADATA ONLY
Loading...
Author / Producer
Date
2020
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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). © International Association for Cryptologic Research 2020.
Permanent link
Publication status
published
External links
Book title
Public-Key Cryptography – PKC 2020
Journal / series
Volume
12110
Pages / Article No.
187 - 219
Publisher
Springer
Event
23rd IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Indistinguishability obfuscation; Extremely lossy functions; Subexponential assumptions
Organisational unit
09693 - Hofheinz, Dennis / Hofheinz, Dennis
Notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually. Conference rescheduled from May 4-7, 2020 to June 1-4, 2020.
Funding
724307 - Preparing Cryptography for Modern Applications (EC)