[RC5] Do not forget about the cheaters :)

Décio Luiz Gazzoni Filho decio at revistapcs.com.br
Wed Jan 7 19:49:09 EST 2004

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Actually your system can be simplified further. I will assume from now on that
the cyphertext is DECRYPTED and checked against the plaintext. Now choose at
random a key belonging to the interval you're going to issue. Decrypt the
RSA-provided cyphertext with this key, and extract the (most or least)
significant x bits. x is a parameter that allows you a tradeoff between
overhead (mainly communication) and probability of catching a cheater. Now
you ask the client to return *all* instances of cyphertext matching the bits
you gave them. Now the server checks each of these instances and (this is the
important part) whether the key he picked at random, before issuing the
block, is included.

Heuristically, this is very resilient to an early-abort strategy -- the
cheater can't know when to abort the computation, since the server could have
picked a key anywhere on the interval. Perform an early-abort at n%
completion of the block and you have n% chance of being caught. It's that
simple.

Choosing x is not so simple, and one must look into the theory of stochastic
processes to do so. An analysis might, as a crude first-order approximation,
take the number of matches within a block as a Poisson-distributed random
variable with \lambda = b/2^x, where b is the number of keys in a block. It
isn't in fact, since by construction there always is at least one match in
any given block; however, for b >> 2^x, I conjecture the approximation is
reasonable. From there, it's possible to compute the expected value of
matches within a block to assess the overhead of a given value of b, and
decide whether it is reasonable (while also giving enough protection against
cheaters).

A pleasant side effect of the system is that it becomes possible to catch
those overclockers who went beyond the capabilities of their CPUs and are
actually churning out wrong results.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQE//KkFFXvAfvngkOIRArSAAJ4gMwvnaJ172OwAUPwowNCsmPKlsgCfbMhA