Cryptology ePrint Archive: Report 2013/689

Differing-Inputs Obfuscation and Applications

Prabhanjan Ananth and Dan Boneh and Sanjam Garg and Amit Sahai and Mark Zhandry

Abstract: In this paper we study of the notion of differing-input obfuscation, introduced by Barak et al. (CRYPTO 2001, JACM 2012). For any two circuit C_0 and C_1, differing-input obfuscator diO guarantees that non-existence of a adversary that can find find an input on which C_0 and C_1 differ implies that diO(C_0) and diO(C_1) are computationally indistinguishable. We show many applications of this notion:

- We define the notion of differing-input obfuscator for Turing machines and give a construction for the same (without converting it to a circuit) with input-specific running times. More specifically, for each input our obfuscated Turning machine takes times proportional to the running time of the Turing machine on that specific input rather than the machines worst-cast running time.

- We give a functional encryption scheme that is fully-secure even when the adversary can obtain an unbounded number of secret keys. Furthermore our scheme allows for secret-keys to be associated with Turing machines and thereby achieves input-specific running times and can be equipped with delegation properties. We stress that this is the first functional encryption scheme with security for an unbounded number of secret keys satisfying any of these properties.

- We construct a multi-party non-interactive key exchange protocol with no trusted setup where all parties post only logarithmic-size messages. It is the first such scheme with such short messages. We similarly obtain a broadcast encryption system where the ciphertext overhead and secret-key size is constant (i.e. independent of the number of users), and the public key is logarithmic in the number of users.

Both our constructions make inherent use of the power provided by differing-input obfuscation. It is not currently known how to construct systems with these properties from the weaker notion of indistinguishability obfuscation.

Category / Keywords: applications / Multilinear Maps, Obfuscation

Date: received 24 Oct 2013, last revised 31 Oct 2013

Contact author: prabhanjan va at gmail com, dabo@cs stanford edu, sanjamg@gmail com, amitsahai@gmail com, mzhandry@stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20131031:060024 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]