[1397] in cryptography@c2.net mail archive
Re: Checking for cheaters in distributed challenges
daemon@ATHENA.MIT.EDU (Steve Reid)
Sun Aug 31 18:29:19 1997
Date: Sun, 31 Aug 1997 13:09:38 -0700 (PDT)
From: Steve Reid <sreid@sea-to-sky.net>
To: Black Unicorn <unicorn@schloss.li>
cc: cryptography@c2.net
In-Reply-To: <3.0.3.32.19970830213633.006ac7a4@schloss.li>
> Ok- let's assume that after searching 10% of the key space, we have an
> indication that there is a cheater. What's the next course of action?
The checking would be done on the individual keyspaces that are handed out
to each person, not just on the whole search.
Suppose each person takes 2^24 keys at a time. A "near miss" would be a
key that decrypts the ciphertext such that the first, say, 20 bits of the
resulting plaintext match the first 20 bits of the known correct plaintext
(or some other fixed value, maybe all zeros). If the cipher has no
statistical biases then the odds of finding a 20-bit match are one in
2^20. Each person searching a 2^24 keyspace should find, on average,
2^(24-20) or 16 near misses per block of keyspace.
Each time the key server receives a report of a searched block of keys, it
should also receive a list of keys that resulted in near misses. It would
take just one decrypt operation per near miss to verify each near miss. If
someone reports keyspace searched but reports bogus near misses, the
person is untrustworthy. The key server should ignore people deemed
untrustworthy.
If the number of near misses is unusually low, it may be that the person
hasn't really searched the keyspace, or it may just be that they were
unlucky. The keyspace should be searched again by a trusted participant.
If near misses are found that were not reported, the person in question
probably didn't search their whole block of keyspace and should be
considered untrustworthy.
