From: Bill Stewart <stewarts@ix.netcom.com>
Date: Tue, 18 Nov 1997 16:20:23 +0800
To: Alexandre Maret <cypherpunks@toad.com>
Subject: Re: trusting untrusted platforms
In-Reply-To: <346DBAD1.C8632971@infomaniak.ch>
Message-ID: <3.0.3.32.19971117232412.00688de4@popd.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



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