**Problem Detail:**

Kriegspiel chess is a variant of chess in which each player is not aware of where the opponent's pieces are. In a human match, a trusted intermediary relays piece losses, legality of moves etc. This is, of course possible on a computer as well. What would a peer to peer implementation of Kriegspiel look like, in terms of algorithms for authentication, one in which:

- There is nobody sending or receiving information besides the two players.
- Each player can independently verify the information sent is true (storing previous data is of course allowed)
- All the functions of the intermediary are filled (players are aware of invalid moves, and of when pieces are taken.
- No player is sent information which makes him certain of information he shouldn't know (e.g the position of the opponent's pieces) besides logical means, of course.

I have looked into zero knowledge proofs somewhat, and was interested in a way they could be implemented in a situation like this.

How would a cheat-proof version of P2P Kriegspiel be implemented?

or, alternatively since that question was deemed too vague

What computer science concepts, protocols, and general algorithms would go into the implementation of such a game?

###### Asked By : Rusty

#### Answered By : Ricky Demer

It would use secure 2-party computation. There would probably be commitments to the statuses of the pieces and oblivious transfers to simulate referee responses and zero-knowledge protocols to show that the players are behaving as they should with respect to the above 2 parts.

If you're taking the oblivious transfer functionality as given and assuming the players are semi-honest, then I'm willing to try coming up with more details here. On the other hand, if you're interested in how the oblivious transfers would be performed or how the zero-knowledge protocols would work, then you should ask on crypto.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63477

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback