This work studies a simple relaxation of VBB: Allow the simulator unbounded computation time, while still allowing only polynomially many queries to the oracle. We then demonstrate the viability of this relaxed notion, which we call Virtual Grey Box (VGB), in the context of fully composable obfuscators for point programs: It is known that, w.r.t. VBB, if such obfuscators exist then there exist multi-bit point obfuscators (aka ``digital lockers'') and subsequently also very strong variants of encryption that are resilient to various attacks, such as key leakage and key-dependent-messages. However, no composable VBB-obfuscators for point programs have been shown. We show fully composable {\em VGB}-obfuscators for point programs under a strong variant of the Decision Diffie Hellman assumption. We show they suffice for the above applications and even for extensions to the public key setting as well as for encryption schemes with resistance to certain related key attacks (RKA).
Category / Keywords: foundations / Obfuscation, Strong Simulation, Leakage-Resilience, Key-Dependent Messages, Related-Key Attacks, decision Diffie Hellman Original Publication (with minor differences): IACR-CRYPTO-2010 Date: received 25 Jul 2010, last revised 7 Sep 2013 Contact author: nirbitan at tau ac il Available format(s): PDF | BibTeX Citation Version: 20130907:203543 (All versions of this report) Short URL: ia.cr/2010/414 Discussion forum: Show discussion | Start new discussion