
Research
Abstracts  2007 
Securely Obfuscating ReEncryptionSusan Hohenberger, Guy N. Rothblum, Abhi Shelat & Vinod VaikuntanathanOverviewWe present the first positive obfuscation result for a traditional cryptographic functionality. This positive result stands in contrast to wellknown negative impossibility results [1] for general obfuscation and recent negative impossibility and improbability [9] results for obfuscation of many cryptographic functionalities. Whereas other positive obfuscation results in the standard model apply to very simple point functions, our obfuscation result applies to the significantly more complicated and widelyused reencryption functionality. This functionality takes a ciphertext for message m encrypted under Alice's public key and transforms it into a ciphertext for the same message m under Bob's public key. To overcome impossibility results and to make our results meaningful for cryptographic functionalities, we use a new definition of obfuscation. This new definition incorporates more securityaware provisions. BackgroundA recent line of research in theoretical cryptography aims to understand whether it is possible to obfuscate programs so that a program's code becomes unintelligible while its functionality remains unchanged. A general method for obfuscating programs would lead to the solution of many open problems in cryptography. Unfortunately, Barak et al. [3] show that for many notions of obfuscation, a general program obfuscator does not existi.e., they exhibit a class of circuits which cannot be obfuscated. A subsequent work of Goldwasser and Kalai [9] shows the impossibility and improbability of obfuscating more natural functionalities. In spite of these negative results for generalpurpose obfuscation, there are a few positive obfuscation results for simple functionalities such as point functions. Canetti [5] shows that under a very strong DiffieHellman assumption point functions can be obfuscated. Further work of Canetti, Micciancio and Reingold [8], Wee [10] and Dodis and Smith [6] both relaxes the assumptions required for obfuscation and considers other (related) functionalities. Despite these positive results, obfuscators for traditional cryptographic functionalities (such as those that deal with encryption) have remained elusive. Our WorkIn this work, we present the first obfuscator for a more traditional cryptographic functionality. Namely, we show how to obfuscate a family of circuits implementing a reencryption functionality. A reencryption program for Alice and Bob takes a ciphertext for a message m encrypted under Alice's public key, and transforms it into a ciphertext for the same message m under Bob's public key. Reencryption programs have many practical applications such as the iTunes DRM system, secure distributed file servers [1] and secure email forwarding. The straightforward method to implement reencryption is to write a program P which decrypts the input ciphertext using Alice's secret key and then encrypts the resulting message with Bob's public key. When P is run by Alice, this is a good solution. In the practical applications noted above, however, the reencryption program is executed by a thirdparty. When this is the case, the straightforward implementation has serious security problems since P's code may reveal Alice's secret key to the third party. A better solution is to design an obfuscator for the reencryption program P. That is, we would like that a third party who has a reencryption program learns no more from the reencryption program than it does from interaction with a blackbox oracle that provides the same functionality. While several reencryption schemes have been proposed before [4,2,7,1], none of these prior works satisfy the strong obfuscation requirement informally stated above. Our main technical contribution is the construction of a novel reencryption scheme which meets this strong notion while remaining surprisingly practical. As a side note, in our construction, ciphertexts that are reencrypted from Alice to Bob cannot be further reencrypted from Bob to Carol. This may be a limitation in some scenarios, but it is nonetheless sufficient for the important practical applications noted above. Our main contribution is an obfuscation for a family of circuits implementing a reencryption functionality. Moreover, the security of the obfuscation is proved under a (blackbox) definition that also guarantees its security for the cryptographic applications mentioned above. This is in contrast to previous work that provided both negative and positive results under predicatebased definitions (e.g. [3]) that do not provide a meaningful security guarantee when the obfuscated program is used as part of a larger cryptographic system. Intuitively, while the predicate blackbox property gives a quantifiable guarantee that some information (namely, predicates) about the program is hidden by the obfuscated circuit, other “nonblackbox information” may still leak. Moreover, this leaked information might compromise the security of a cryptographic scheme which uses the obfuscated circuit. The definition of obfuscation that we use both sidesteps impossibility results by considering randomized functionalities, and is more meaningful for cryptographic applications than definitions of obfuscation used in previous work. Research SupportThis research was supported by NSF grant CNS0430450 and NSF grant CFF0635297. References:[1] Giuseppe Ateniese, Kevin Fu, Matthew Green, and Susan Hohenberger. Improved Proxy Reencryption Schemes with Applications to Secure Distributed Storage. ACM Trans.on Information and System Security, 9(1):130, February 2006. Previously, in NDSS: 2943, 2005. [2] Matt Blaze, Gerrit Bleumer, and Martin Strauss. newblock Divertible protocols and atomic proxy cryptography. EUROCRYPT 1998, volume 1403 of LNCS: 127144, 1998. [3] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit, Sahai, Salil P. Vadhan, Ke Yang. On the (Im)possibility of Obfuscating Programs. CRYPTO 2001: 118. [4] Matt Blaze and Martin Strauss. Atomic proxy cryptography. Technical report, AT&T Research, 1997. [5] Ran Canetti. Towards realizing random oracles: Hash functions that hide all partial information. CRYPTO 1997, volume 1294: 455469. [6] Ran Canetti, Daniele Micciancio, and Omer Reingold. Perfectly oneway probabilistic hash functions (preliminary version). STOC 1998: 131140. [7] Yevgeniy Dodis and Anca Ivan. Proxy cryptography revisited. NDSS, 2003. [8] Yevgeniy Dodis and Adam Smith. Correcting errors without leaking partial information. STOC 2005: 654663. [9] Shafi Goldwasser, Yael Tauman Kalai. On the Impossibility of Obfuscation with Auxiliary Input. FOCS 2005: 553562. [10] Hoeteck Wee. On obfuscating point functions. STOC 2005: 523532. 

