[1393] in cryptography@c2.net mail archive
Checking for cheaters in distributed challenges
daemon@ATHENA.MIT.EDU (Secret Squirrel)
Sat Aug 30 17:28:53 1997
Date: 30 Aug 1997 20:56:01 -0000
From: Secret Squirrel <nobody@secret.squirrel.owl.de>
To: cryptography@c2.net
One problem with DES challenges is that someone could grab some key
space and claim to have searched it, but they actually didn't. Here is a
solution.
Make searchers not just report when they are done, but also to report
"near misses". These could be cases when the ciphertext and encrypted
plaintext match in the first n bits. n can be chosen so that a typical
batch produces some reasonable number of hits - enough so that it will
be clear when the number of hits is statistically plausible, but few
enough that the amount of data uploaded to report a batch completion
is not too big.
The server can store (and perhaps check) the reported near misses, to
make sure that they are correct. The only way to generate enough near
misses is essentially to search (almost) the whole key space. So this can
confirm that searchers are at least doing what they claim to.
This doesn't solve the problem of the person who finds the key and then
claims that it was not present in his search range. Such a person may have
an interest in seeing the challenge fail (he invests in technology which
would be threatened by success) or he may want to pass the key on to
a confederate who will claim to have discovered it on his own, and who
then seeks to acquire the whole prize for himself.
Prize issuers could also demand to see some minimum number of near
misses in order to award the prize, in order to determine that searchers
really did the work. Of course the searchers could claim to have just
gotten lucky and found the key far sooner than expected, but this would
be awfully suspicious, to say the least.
