Can homomorphic encryption achieve program integrity (verification) in the cloud? As I understand it, homomorphic encryption can be used to keep data confidential while still allowing computations over the data. From another question, I found out that one can also verify the integrity of the computation, (by which I mean one can verify that a returned value is indeed the result of the requested computation) by re-computing the result.

I am interested in a scenario where re-computing is not possible. For example, the original data might not be available anymore or the original data is very large and re-computing is too expensive. Are there other ways to verify that a result corresponds to the required computation?

That is, say I want to perform the operation r = a + b + c using homomorphic encryption, in the cloud. Once the cloud returns the result r, how can I verify that r is the result of a + b + c and not, say, the result of a + b or some other computation?
Can I use homomorphic encryption to keep cloud computation confidential and also guarantee the integrity of computation?


You're looking for verifiable computing:


  Verifiable computing (or verified computation or verified computing) is enabling a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly.