Can a fully homomorphic encryption be used for oblivious code execution?

Question

After reading this answer a while ago, I took an interest in fully homomorphic encryption. After reading the introduction of Gentry's thesis, I started wondering if his encryption scheme could be used for oblivious code execution as defined in the third paragraph.

In a fully homomorphic encryption scheme we typically encrypt some data, send it to a hostile environment where a certain function is computed on the data, the result of which is then sent back (encrypted), without the adversary finding out what the received data or the result of the function is.

With oblivious code execution I mean that we encrypt a piece of code $C$ designed to solve some problem $P$ and send it to a hostile environment. The adversary wants to use $C$ to solve $P$, but we don't want him to know how $C$ works. If he has an input $I$ for $P$, he can encrypt $I$ and then use (some encryption scheme on) $C$ with $I$, which then returns the (not encrypted) output $O$ (the solution of $P$ for the input $I$). The encryption scheme makes sure the adversary never finds out how the piece of code works, ie to him it works like an oracle does.

The main practical use (I can think of) for such an encryption scheme would be to make piracy more difficult or even impossible.

The reason I think this may be possible using a fully homomorphic encryption scheme is because we can execute arbitrary circuits on encrypted data, in particular an universal Turing machine. We could then encrypt the code as if it were data and then use the circuit for an universal Turing machine on this encrypted data to execute the code.

I pose this as a question here because I don't know whether this idea is usable: I never got much further than the introduction of Gentry's thesis, and my knowledge about cryptography is limited. Also, I don't know if there already is a often-used term for oblivious code execution: I tried searching Google for the idea but not knowing the proper term I found nothing.

There are multiple problems I can think of which may cause problems with this approach. Firstly, if we use a fully homomorphic encryption without modification, the result of the computation ($O$) would be encrypted. It would therefore be useless for the adversary who wishes to use your code to solve $P$. While this could still be useful for, say, cloud computing, this is not what I want to achieve.

Secondly, because we're using circuits and not arbitrary Turing machines, we can't use arbitrary amounts of memory: we're limited to a predetermined amount of memory. This means that if we want to run a program in this way, it's memory footprint will always be the same, namely it's peak memory usage.

Lastly, the constants involved would almost certainly kill off any practical use of such a system, but I think the idea is interesting nonetheless.

Answer 1

Unfortunately, there is a result that theoretically forbids "oblivious code execution":

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (Im)possibility of Obfuscating Programs, ADVANCES IN CRYPTOLOGY — CRYPTO 2001.

Here are the links:

• http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html
• http://eprint.iacr.org/2001/069
• http://www.springerlink.com/content/telalqdcx3n600uf/

The abstract reads:

Informally, an obfuscator $\cal O$ is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) $P$ and produces a new program $\cal O(P)$ that has the same functionality as $P$ yet is "unreadable" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the "unreadability" condition in obfuscation as meaning that $\cal O(P)$ is a "virtual black box," in the sense that anything one can efficiently compute given $\cal O(P)$, one could also efficiently compute given oracle access to $P$.

In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of functions $\cal F$ that are inherently unobfuscatable in the following sense: there is a predicate $\pi$ such that (a) given any program that computes a function $f$ in $\cal F$, the value $\pi(f)$ can be efficiently computed, yet (b) given oracle access to a (randomly selected) function $f$ in $\cal F$, no efficient algorithm can compute $\pi(f)$ much better than random guessing.

We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only approximately preserve the functionality, and (c) only need to work for very restricted models of computation $\rm{TC}$ $0$). We also rule out several potential applications of obfuscators, by constructing "unobfuscatable" signature schemes, encryption schemes, and pseudorandom function families.

Answer 2

Indeed, while fully homomorphic encryption is very useful for executing code between multiple untrusting parties (see for example, this paper), you need some kind of interaction, when the party that computes the encrypted output sends it to the party that knows the secret key.

The notion you're looking for does sound suspiciously close to software obfuscation, for which we proved an impossibility result mentioned above. I also wrote once an informal overview of that paper, that some people may find useful.

Given this impossibility result, there are two (non disjoint) ways one can relax the definition: either by restricting the classes of programs/functions one is required to obfuscate, or giving a looser notion of security.

The second approach is perhaps possible, and we remark on some weak obfuscation-like notions in our paper. However, note that our attack completely recovers the original source code of some program, no matter how it's obfuscated. So you'd have to somehow make a security definition which trivializes for the case of our counterexamples.

The first approach was done for every restricted functionalities (e.g., point functions), but again one has to make sure the class doesn't contain our counterexample, which roughly means it shouldn't contain pseudorandom functions.