On Fri, 3 Oct 2003, Benja Fallenstein wrote:
>bear wrote: >> Why should this not be applicable to chess? There's nothing to >> prevent the two contestants from making "nonce" transmissions twice a >> move when it's not their turn. > >I.e., you would need a protocol extension to verify the nonces somehow-- >if that's possible at all-- or are you just faster than me, and have >thought about a way to do that already? Not "faster" per se, but I do happen to know the solution to that problem. :-) Suppose Alice picks a nonce A(zero). Then for n=one to a thousand (presumably no chess game will last 1000 moves) she calculates A(n) = hash (A(n-1)). Note, this has to be a ONE WAY hash function rather than any kind of encryption that can be decrypted. I'd suggest seventeenth-power mod K where K is prime, but lots of good irreversible hashing functions that aren't so expensive in CPU cycles are around. Bob also picks a nonce B(zero) on his side, and produces the same kind of sequence of B(one...one thousand) using the same hash function. Now let the moves of the chess game be numbered from 1000 down to 0. (ie, the first move they play will be move 1000, the second will be move 999, etc.) When it's Bob's turn, he sends his move padded with B(n), and Alice sends a random move padded with A(n). When it's Alice's turn, she sends her move padded with A(n) and Bob sends a random move padded with B(n). Bob can rapidly check to make sure that the A(n) recieved with each message has the right relation to the A(n+1) he recieved with the previous move, but there is no way he (or Mitch) can possibly predict A(n-1) to know what he'll get in the next move. Likewise Alice can rapidly check to make sure that the B(n) recieved with each move has the right relation to the B(n+1) she recieved with the previous move, but there is no way she (or Mitch) can predict B(n-1) to know what she'll get the next move. The only change to the rules of chess this requires is that if they ever exhaust the finite sequence of generated nonces, they have to call that game a draw. But a thousand moves, really, shouldn't be a problem for chess, and if it is you can just make the sequence longer and start a new game. Bear --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]