[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
rHUcglR5G/d5acz1U+jzAdQ=
=RenH
-----END PGP SIGNATURE-----



More information about the rc5 mailing list