Research Abstracts - 2007

Securely Obfuscating Re-Encryption

Susan Hohenberger, Guy N. Rothblum, Abhi Shelat & Vinod Vaikuntanathan

Overview

We present the first positive obfuscation result for a traditional cryptographic functionality. This positive result stands in contrast to well-known 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 widely-used re-encryption 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 security-aware provisions.

Background

A 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 exist---i.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 general-purpose obfuscation, there are a few positive obfuscation results for simple functionalities such as point functions. Canetti [5] shows that under a very strong Diffie-Hellman 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 Work

In 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 re-encryption functionality. A re-encryption 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. Re-encryption 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 re-encryption 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 re-encryption program is executed by a third-party. 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 re-encryption program P. That is, we would like that a third party who has a re-encryption program learns no more from the re-encryption program than it does from interaction with a black-box oracle that provides the same functionality.

While several re-encryption 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 re-encryption scheme which meets this strong notion while remaining surprisingly practical.  As a side note, in our construction, ciphertexts that are re-encrypted from Alice to Bob cannot be further re-encrypted 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 re-encryption functionality. Moreover, the security of the obfuscation is proved under a (black-box) 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 predicate-based 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 black-box property gives a quantifiable guarantee that some information (namely, predicates) about the program is hidden by the obfuscated circuit, other “non-black-box 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 Support

This research was supported by NSF grant CNS-0430450 and NSF grant CFF-0635297.

References:

[1] Giuseppe Ateniese, Kevin Fu, Matthew Green, and Susan Hohenberger. Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage. ACM Trans.on Information and System Security, 9(1):1--30, February 2006. Previously, in NDSS: 29-43, 2005.

[2] Matt Blaze, Gerrit Bleumer, and Martin Strauss. newblock Divertible protocols and atomic proxy cryptography. EUROCRYPT 1998, volume 1403 of LNCS: 127--144, 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: 1-18.

[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: 455--469.

[6] Ran Canetti, Daniele Micciancio, and Omer Reingold. Perfectly one-way probabilistic hash functions (preliminary version). STOC 1998: 131--140.

[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: 654--663.

[9] Shafi Goldwasser, Yael Tauman Kalai. On the Impossibility of Obfuscation with Auxiliary Input. FOCS 2005: 553-562.

[10] Hoeteck Wee. On obfuscating point functions. STOC 2005: 523--532.