How to check if an algorithm in a distributed system worked within restraints?

I want to design a system in which a program is sent along with data and then it answers with the result. Is redundancy a must in this situation to check for correctness of the processed data? What is enough to trust the other system? Please be aware that I might not be asking the right question, this is almost a philosophical question.

• If you are not asking the right question, what are other people supposed to do? – Tsuyoshi Ito Sep 8 '11 at 17:04
• this is done by Folding at Home which does use redundancies – ratchet freak Sep 8 '11 at 17:57
• IMHO, the question is not stated in a way that can be answered, it is not clear enough. If there is not no reason that the computation will not be completed as expected then one would expect that the computation is done correctly without any need for extra proof. – Kaveh Sep 9 '11 at 6:29

I think you can use fully homomorphic encryption to solve this problem.

Encrypt the program and data using a fully homomorphic encryption scheme, send it to the system to be processed, and retrieve the result. Let the correct output be the string $s$. Since you say that you might not be able to tell if $s$ is the correct output, I would have the program concatenate a prefix which you can verify. Something like:

The computation started at 'TimeStamp' and finished at 'TimeStamp' with the following result: $s$.

If the system made a mistake (or tried to cheat by not executing your program exactly), I am sure you could prove that with high probability (under standard complexity-theoretic assumptions), the decrypted output would not begin with

The computation started at 'TimeStamp' and finished at 'TimeStamp' with the following result:

where both occurrences of 'TimeStamp' are not only in the proper form of a time stamp, but also make sense as times (i.e. the first time is after you send the program to the system while the second time is after the first and probably shortly before the time the system gave you the results).

• For a counter example to your argument consider an adversary which knows what should the prefix contain. As long as the prefix does not depend on the encrypted input data, then the adversary can just encrypt any conforming prefix using the public key for the homomorphic cryptosystem. On the other hand if we are willing to pay the cost of the very expensive fully-homomorphic cryptosystems, we could as well afford using zero-knowledge proofs of correctness for every step in the computation. – Mohammad Alaggan Sep 16 '11 at 12:56
• @M. Alaggan I am not sure how this is a counter example for my argument since I don't use a public encryption key. – Tyson Williams Sep 16 '11 at 13:47
• @M. Alaggan Also, instead commenting that a ZK proof protocol would be better, why not say that as a new answer? – Tyson Williams Sep 16 '11 at 13:53
• A homomorphic cryptosystem is a public-key cryptosystem. – Mohammad Alaggan Dec 15 '11 at 15:01