<p>I think you can use <a href="http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption" rel="nofollow">fully homomorphic encryption</a> to solve this problem.</p>

<p>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:</p>

<blockquote>
  <p>The computation started at 'TimeStamp' and finished at 'TimeStamp' with the following result: $s$.</p>
</blockquote>

<p>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</p>

<blockquote>
  <p>The computation started at 'TimeStamp' and finished at 'TimeStamp' with the following result: </p>
</blockquote>

<p>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).</p>

CC BY-SA 3.0
2011-09-16T12:56:04.213Z
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
CC BY-SA 3.0
2011-09-16T13:47:35.423Z
@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
CC BY-SA 3.0
2011-09-16T13:53:17.113Z
@M. Alaggan Also, instead commenting that a ZK proof protocol would be better, why not say that as a new answer?
Tyson Williams
CC BY-SA 3.0
2011-12-15T15:01:33.903Z
A homomorphic cryptosystem is a public-key cryptosystem.
Mohammad Alaggan
CC BY-SA 3.0
2011-09-16T12:40:56.640Z
2011-09-16T12:40:56.640Z
Tyson Williams
<p>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.</p>

CC BY-SA 3.0
2011-09-08T17:04:09.240Z
If you are not asking the right question, what are other people supposed to do?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-08T17:57:16.757Z
this is done by [Folding at Home](http://en.wikipedia.org/wiki/Folding@home) which does use redundancies
ratchet freak
CC BY-SA 3.0
2011-09-09T06:29:40.043Z
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
<dc.distributed-comp><network-modeling>
How to check if an algorithm in a distributed system worked within restraints?
alfa64
# How to check if an algorithm in a distributed system worked within restraints?

(Asked by: username_0 on 2011-09-08)

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.

**Tags:** dc.distributed-comp, network-modeling

> **Comments:**
> **username_1**: If you are not asking the right question, what are other people supposed to do?  
> **username_2**: this is done by [Folding at Home](http://en.wikipedia.org/wiki/Folding@home) which does use redundancies  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2011-09-16. Score: 0

I think you can use [fully homomorphic encryption](http://en.wikipedia.org/wiki/Homomorphic_encryption#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).

> **Comments:**
> **username_5**: 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.  
> **username_4**: @M. Alaggan I am not sure how this is a counter example for my argument since I don't use a public encryption key.  
> **username_4**: @M. Alaggan Also, instead commenting that a ZK proof protocol would be better, why not say that as a new answer?  
> **username_5**: A homomorphic cryptosystem is a public-key cryptosystem.  

---

