Full-Duplex-Chess Grandmaster (was: anonymous DH & MITM)

[Zooko O'Whielacronx]

It's clear that my challenge about the Chess Grandmaster Problem has thrown 
more shadow than light.

This is partly because it is an inherently tricky problem, but also because 
I confused the issue by talking about both traditional Chess Grandmaster (a 
problem that I am interested in) and Full-Duplex-Chess Grandmaster (a problem 
that is more or less solved by the Interlock Protocol).

So allow me to try again, focussing solely on one case: the Full-Duplex-Chess 
Grandmaster Attack.

Full-Duplex-Chess is a funny chess variant that isn't much played.  In Full-
Duplex-Chess each player chooses a move to make from the current position, 
writes down the move on a slip of paper, and holds the slip of paper out face 
down over the board.  This commits the player to that move.  Once both players 
are committed to their moves, then both moves are revealed, and both moves are 
made on the chess board simultaneously.  The rules of chess have to be amended 
to handle cases such as "we both tried to move into the same square", but that 
doesn't concern us.

Now, here's the Full-Duplex-Chess Grandmaster problem:

Alice and Bob are each grandmasters at Full-Duplex-Chess.  They each wish to 
play a game against another player -- they don't care who.  At the beginning 
of the game, each player will generate a new public key pair, and during the 
game, that public key will be used to encrypt and verify that player's moves.  
Afterwards, the losing player is going to send a message, encrypted with his 
or her opponent's public key, that says "Wow, you sure are a good Full-Duplex-
Chess player!".  (If the game is a draw, each player will send such a message 
to the other.)

Now Mitch's goal is to acquire such a message from one of the players.  (Why 
he wants this isn't clear to me.  I've never understood why some people enjoy 
winning by cheating.)

Alice's and Bob's goals are that whoever actually plays the best game of Full-
Duplex-Chess receives the congratulatory note.

I reiterate that Alice and Bob share no shared state at the beginning of the 
protocol nor do they have any friends in common whom they can trust.  The only 
things that they have in common are knowledge of the rules of Full-Duplex-
Chess, and knowledge of how to perform a cryptographic protocol of your choice.

Now it is essential to differentiate between Mitch winning a congratulatory 
note by proxying the moves from Alice and Bob while replacing their public 
keys, which is the "(Full-Duplex) Chess Grandmaster Attack", and Mitch winning 
a congratulatory note by playing a game of Full-Duplex Chess against one of 
them and winning.

I certainly don't claim that the Interlock Protocol can prevent Mitch from 
playing a game with one person and also playing a game with a second person, 
but I do claim that it can prevent Mitch from pulling the "Full-Duplex-Chess 
Grandmaster" trick.

Regards,

Zooko

http://zooko.com/log.html

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com