Paper 2017/275

Indistinguishability Obfuscation: Simpler Constructions using Secret-Key Functional Encryption

Fuyuki Kitagawa and Ryo Nishimaki and Keisuke Tanaka

Abstract

We propose simple generic constructions of indistinguishability obfuscator (IO). Our key tool is exponentially-efficient indistinguishability obfuscator (XIO), which is the same as IO except that the size of an obfuscated circuit (or the running-time of an obfuscator) is slightly smaller than that of a brute-force canonicalizer that outputs the entire truth table of a circuit to be obfuscated. A ``compression factor'' of XIO indicates how much XIO compresses the brute-force canonicalizer. In this study, we show that XIO is a powerful enough to achieve cutting-edge cryptography. In particular, we propose the following constructions: 1. A single-key weakly succinct secret-key functional encryption (SKFE) scheme is constructed from XIO (even with a bad compression factor) and one-way function. 2. A single-key weakly succinct public-key functional encryption (PKFE) scheme is constructed from XIO with a good compression factor and public-key encryption scheme. 3. A single-key weakly succinct PKFE scheme is constructed from XIO (even with a bad compression factor) and identity-based encryption scheme. It is known that sub-exponentially secure single-key weakly succinct PKFE scheme implies IO and that single-key weakly succinct (resp. multi-key non-succinct) SKFE implies XIO with a bad (resp. good) compression factor. Thus, we developed two methods of constructing IO. One uses multi-key SKFE and plain public-key encryption schemes and the other uses single-key weakly succinct SKFE (or XIO) and identity-based encryption schemes. It is not known whether single-key weakly succinct SKFE implies IO (if we use fully black-box reduction in a certain model, it is impossible), but our single-key weakly succinct SKFE scheme gives many interesting by-products.

Note: Revise the security of secret-key encryption in Preliminaries and fix minor typos.