Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Indistinguishability Obfuscation, Functional Encryption, Succinctness

Date: received 21 Mar 2017, last revised 5 Apr 2017

Contact author: ryo nishimaki at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20170405:112547 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]