Hello everyone,
I have recently been working on a theoretical game that requires some advanced cryptography. I have made multiple forum posts about it. They all looked something like this:
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, 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?
Some people suggested me to check out private set intersection (PSI), shared secret keys, and key switching.
Because chess has so many rules and intricacies, I decided to use a simpler game while trying to solve the cryptography part. Consider battleship. A similar problem in battleship would be to keep the coordinates of the shots private while still learning the correct outcome (hit/miss).
My questions to this forum:
- A protocol that I came up with for battleship is the following: Player A fires a shot. It is apparently possible for PSI to reveal the intersection to only one party. For the PSI, player A’s set will contain its shot coordinate, while player B’s set will contain the squares that are occupied by player B’s ships. If they intersect, player A learns that the outcome is a hit, otherwise it’s a miss. They will also send each other zero-knowledge proofs to ensure that the elements in the sets are what they are supposed to be. Would a protocol like this work? How can this game be implemented using shared keys?
- I read that private set intersection can be implemented using homomorphic encryption. Can Zama’s Concrete be used to implement the games that I described?
Thank you very much!
