4
$\begingroup$

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:

  1. There is nobody sending or receiving information besides the two players.
  2. Each player can independently verify the information sent is true (storing previous data is of course allowed)
  3. All the functions of the intermediary are filled (players are aware of invalid moves, and of when pieces are taken.
  4. 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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Do you mean that the players cannot access the board to see opponent's pieces, but still keep track of opponent's moves to avoid cheating on the other side? Are you aware that this looks like a man-in-the-middle with the attacker, being the player, with physical access to the machine? $\endgroup$
    – Evil
    Sep 15, 2016 at 4:44
  • $\begingroup$ I am not clear as to why this is a computer science question. It seems to me you are facing practical challenges of designing a particular system. Please boil down your question to computer science concepts. $\endgroup$
    – Raphael ♦
    Sep 15, 2016 at 11:01
  • 1
    $\begingroup$ Can you ask a more specific question than "what would an implementation look like"? What is your threat model? Who is trusted (if anyone)? What do you mean by a peer-to-peer implementation, specifically? You might want to look at the literature on secure multi-party computation. $\endgroup$
    – D.W. ♦
    Sep 15, 2016 at 13:46
  • $\begingroup$ I find this question very interesting, and I will keep a eye out here to follow the development, unfortunately I don't have the specific knowledge to supply any answers. BUT this question is very closely related to distributed computing. You might find new answers searching in that domain. The thing you want, if I understand you correctly, is a encrypted data-structure that could still be modified, without being fully read. Maybe some sort of bloomfilter where only one lookup is allowed per move could be a starting point. $\endgroup$
    – Gabriel Tigerström
    Sep 15, 2016 at 18:11
  • $\begingroup$ @Raphael I am not asking about a specific program I am writing for this, so I think it would be too broad for stackoverflow. $\endgroup$
    – Rusty
    Sep 17, 2016 at 0:05

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How is OT related to referee responses? Can you expand that a bit? $\endgroup$
    – chi
    Sep 15, 2016 at 7:55
  • $\begingroup$ @chi: ​ For example, one part would likely be white computing a bitmap indicating which squares are [attacked by white knights but not possibly attacked by any of white's line pieces], so that black can learn the bit for the square black's king is on, to determine whether-or-not the referee announces "check by a knight". ​ ​ ​ ​ $\endgroup$
    – user12859
    Sep 15, 2016 at 8:23
  • $\begingroup$ Isn't that assume that players are at least a bit fair (sorry I do not know proper term)? $\endgroup$
    – Evil
    Sep 15, 2016 at 14:23
  • 1
    $\begingroup$ @Evil: ​ That's where the zero-knowledge protocols come in. ​ ​ ​ ​ $\endgroup$
    – user12859
    Sep 15, 2016 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.