Homomorphic encryption with both algorithm and data encrypted?

Question

Is it theoretically possible to use homomorphic encryption to run an encrypted algorithm over encrypted data? If this is not possible, is it at least possible to run an encrypted algorithm over plain data (beyond a plain algorithm over encrypted data)? Ideally, can you cite papers where I can read about it?

Answer 1

Yes it is possible. An interpreter is an algorithm that takes a program $M$ and a datum $x$ as input and outputs the result of running program $M$ on input $x$. For any Turing-complete programming language, one might construct such an interpreter. See this Wikipedia entry for more details.

Say we have a universal interpreter $U$ that expects an input of the form $\langle M,x\rangle$ such that $U(\langle M,x\rangle)=M(x)$. Then you can produce the ciphertext $c=\mathrm{Enc}(\langle M,x\rangle)$ and evaluate $U$ homomorphically on this ciphertext $c'=\mathrm{Eval}(U,c)$. The correctness of the FHE scheme implies that $\mathrm{Dec}(c')=U(\langle M,x\rangle)=M(x)$. So the recipient learns $M$ applied to $x$ and the evaluator learns neither $M$ nor $x$.

I omit many details in this answer such as the fact that FHE schemes evaluate circuits of addition and multiplication over finite fields. If you restrict to boolean circuits, this paper and this one show how you can build a universal circuit for a fixed size. I am unaware if the same has been done with respect to arithmetic circuits over fields.

Answer 2

This can (sort of) be done. There are a few things to mention

1. One can take as input encrypted data, an encrypted function, and produce an encrypted output. The keywords to search on for this are "function-private fully-homomorphic encryption"

2. If one wants to take plaintext data, an encrypted function, and produce an encrypted output, this should also be able to be done with the same techniques.

3. If one wants to take plaintext data, an encrypted function, and produce plaintext output, the problem is significantly harder. I believe terms to search on are "indistinguishability obfuscation", and perhaps "white-box cryptography" (though the two topics are distinct).