At 04:08 PM 11/15/1997 +0100, Alexandre Maret wrote:
Here is the problem: how to make sure that an untrusted computer really run the code you ask him to run.
In general, you can't. Many interesting problems are NP, so you can quickly tell from the output whether it matches the input, but many more interesting problems are not, especially in crypto. Often there's a special form that lets you detect false positives, but for false negatives you're usually out of luck. And for complex calculations other than searches, such as numerical stuff, you usually lose too.
Practically, we can take the example of the RC5 contest. If I ask an untrusted computer to search for the key in a particular sub-keyspace, how can I make sure that this machine really looked for the key, and that it doesn't just say "the key is not in this block, give me another block" just to get higher in the stats...
The common solution, which also covers "this machine started looking but stopped and didn't tell me", is to assign problem space to multiple users (and hope they don't collude :-). Random search is surprisingly effective, and has the advantage that it doesn't require coordination. It's sometimes helpful to structure the searches a bit so you can easily compare results from multiple players. Thanks! Bill Bill Stewart, stewarts@ix.netcom.com Regular Key PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639