Hello everyone,
Here is a theoretical problem that I have been thinking about for the past week. Any help would be appreciated!
TL;DR: How can one implement Dark chess without relying on a third party?
Zero-knowledge tools make it possible to play some games without having to rely on and trust a third party. A common example is battleship. Both player A and player B keep the arrangements of their ships private throughout the game. When player A fires a shot on player B’s grid, player B replies with a zero-knowledge proof telling player A whether it was a hit or a miss. When it is player B’s turn to fire, it simply picks a coordinate on player A’s grid that it hasn’t picked before. When it is their turn, each player knows what their options are – they do not need to know anything about the other player’s private game state (in this case, the arrangement of their ships on the grid) to know every valid move.
This contrasts with Dark chess (playable on chess.com), where “a player does not see the entire board – only their own pieces and the squares that they can legally move to.” For a player to know which squares their pieces can move to, they frequently need to know where their opponent’s pieces are, which is private information! So, players should 1) keep the positions of their pieces private, 2) zero-knowledge prove the validity of their moves, 3) somehow reveal the positions of the pieces that can be captured by the opponent’s pieces. The catch is that the opponent’s pieces are hidden, which makes #3 nontrivial.
If there is a trusted third party, the players can just share the positions of their pieces with it and rely on it for the management of the board. The challenge is to implement Dark chess without relying on a third party. It seems to me that zero-knowledge proofs would not be enough and that we would need homomorphic encryption in some form. When player A makes a move, they can send 1) a zero-knowledge proof proving that their move is valid, 2) a homomorphically-encrypted copy of the positions of their pieces. Player B can pass #2 and the positions of their own pieces to a function, which can somehow tell only the positions of the pieces that player B is supposed to see. Now that player B has updated its board after player A’s latest move, they send a homomorphically-encrypted copy of the positions of their own pieces to player A. Player A passes this data to the same function that player B used and updates their own board.
Do we currently have the math/software tools that can implement this? Does anyone have any ideas?