trusting untrusted platforms

hello

Here is the problem: how to make sure that an untrusted
computer really run the code you ask him to run.

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...

I've heard about smartcards being helped by ATMs, so
maybe this could be a direction to look into...

Any pointer, info, help, ... very appreciated

  alex

-- 
\\-----------------------------------------------------------\\
// Alexandre Maret -- Linux : The choice of a GNU generation //
\\ amaret@infomaniak.ch -- http://www.infomaniak.ch/~amaret  \\
//-----------------------------------------------------------//

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