• Create Account

# Cryptographically secure p2p implementation of GG

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

13 replies to this topic

### #1mudslinger  Members   -  Reputation: 139

Like
0Likes
Like

Posted 13 April 2013 - 12:57 PM

Hello,

I have a question about how to create a mutual p2p trust between two players of this game. We have this stratego-like board game with game pieces of various ranks. When a there is a challenge between two pieces (they go to the same square) the winner (higher rank) is determined by a third party. The opponent's game pieces are never revealed to the other player.

How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?

Problems with some suggestions:

Mental Poker - no, because the cards are revealed at some point.
Homomorphic encryption - no, because this requires the same encryption key.
Yao's millionare problem - no, because the higher piece doesn't always win, there are exceptions (see Spy and Private in the wiki link below)

Edited by mudslinger, 13 April 2013 - 01:37 PM.

### #2hplus0603  Moderators   -  Reputation: 5309

Like
0Likes
Like

Posted 13 April 2013 - 01:31 PM

How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?

It is logically impossible to do so.
Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

You have two choices:
1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.
enum Bool { True, False, FileNotFound };

### #3mudslinger  Members   -  Reputation: 139

Like
0Likes
Like

Posted 13 April 2013 - 01:40 PM

1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.

This defeats the point of my question. I don't think it's entirely impossible. Yao's millionaire problem comes pretty close.

This isn't really for a game, it's more of a thought experiment.

EDIT: I believe the problem is Secure Multi-party Computation, I just don't know how to implement it exactly yet.

Edited by mudslinger, 13 April 2013 - 01:56 PM.

### #4hplus0603  Moderators   -  Reputation: 5309

Like
0Likes
Like

Posted 13 April 2013 - 03:49 PM

Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

What part of my argument are you saying is incorrect?
In the end, a compare-and-branch needs to happen in a CPU to decide that A is stronger than B.
To do that, you need to know the relative strengths of the pieces.
To do that, you need to impart strength information to the deciding side -- if not absolute, then at least relative enough that the other end *may* end up knowing the exact strength.

You can make some bit of obscuration by using some kind of binary search. "Is your pieces stronger than X?" If no, and I know is my piece, or weaker than my piece, then I know that the decision is made, without knowing exactly what the other piece is -- just that it is at least strong enough for X. If I choose X to not necessarily be my particular piece strength, sometimes some information can be held back. But, other times, the exact information is necessarily needed, when piece A is exactly one quantum stronger than piece B.
enum Bool { True, False, FileNotFound };

### #5mudslinger  Members   -  Reputation: 139

Like
0Likes
Like

Posted 13 April 2013 - 07:29 PM

But it is possible to compare two values from different parties without revealing those two values.

http://www.proproco.co.uk/million.html

I believe I currently have a solution in my head.

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

It's rough, but it looks doable.

Edited by mudslinger, 13 April 2013 - 09:11 PM.

### #6Hodgman  Moderators   -  Reputation: 30388

Like
0Likes
Like

Posted 13 April 2013 - 11:14 PM

As a simpler (and less secure) option to the millionaire solution, would be for Alice to send bob a table of 100 different units, and request that bob send back 100 booleans indicating if that unit would win the battle. Alice then picks out the vale for the actual unit there, and tells bob the result (and the system below detects lies later).
On average, there'll be 50 units on the list that match Alice's claimed outcome, so bob does know with a 1/50 chance what Alice's unit was... Alice also knows the strength of bob's unit, in that she knows the results for 100 hypothetical battles against it... Actually, maybe this isn't a good idea at all ;-/

both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

Some online card games work this way, and it should be extendable to any game with deterministic rules, as long as you're ok with deferring cheat detection until the very end of the game, when it's ok to reveal all the secrets. In a many-player game, if one player drops out half way through, there's no way to validate their actions (unless everyone gives their keys to a trusted 3rd party at the start).

### #7Bacterius  Crossbones+   -  Reputation: 8886

Like
0Likes
Like

Posted 17 April 2013 - 11:28 PM

But it is possible to compare two values from different parties without revealing those two values.

http://www.proproco.co.uk/million.html

I believe I currently have a solution in my head.

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

It's rough, but it looks doable.

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece. In some cases, or if you don't have many pieces, this may often be enough to deduce the other player's piece. For example, using cards, if my card is a king and you still win, then I know you have an ace, no matter how much cryptography and obfuscation you throw at the problem. A fix would be to increase the number of different pieces, or perform the comparison less often. Another method is to change the number of pieces dynamically, but this doesn't make for a very enjoyable game since the comparison is no longer consistent with what people would expect. If this caveat is unacceptable to you, your problem has no solution.

Otherwise, if this is fine (and hopefully it is) then Yao's approach seems doable since you probably don't have that many pieces. Now as for cheating, your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn. You could also send the encrypted game state every turn with no information leakage for faster failure response (1 turn) but perhaps it is not worth it. Make sure to implement a commitment scheme as well so that a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice but it can be done depending on your encryption scheme and the complexity of the game state).

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- Pessimal Algorithms and Simplexity Analysis

### #8mudslinger  Members   -  Reputation: 139

Like
0Likes
Like

Posted 18 April 2013 - 08:14 AM

...

if this is fine then Yao's approach seems doable since you probably don't have that many pieces.

...

your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn.

...

a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice

...

I thought of these, it is a yes on all three points. It is the nature of the game that the strength of a piece is partially revealed after a challenge (e.g. opponent's piece won, it's stronger than mine).

Edited by mudslinger, 18 April 2013 - 08:23 AM.

### #9rip-off  Moderators   -  Reputation: 8224

Like
0Likes
Like

Posted 18 April 2013 - 11:35 AM

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece.

I believe that is by design in such games. This partial information is what the player uses to formulate their plan.

Just a thought, if you could impose a strict weak ordering on the ranks, I believe you can have a simple protocol to resolve the combat. Conceptually, each peer starts at the lowest value piece and asks if the other peer can beat it using their actual piece. If not, the peer asks if the next highest rank can beat it. And so on, stopping as soon as one player reveals they can beat that particular value. No more information is leaked than necessary.

For example, player A has a middling piece (e.g. "Lt. Colonel") but player B has a highly ranked piece (e.g. "Major General"). The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes

A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: yes

A -> B: Can you beat a private: yes
B -> A: Can you beat a private: yes

A -> B: Can you beat a sergeant: yes
B -> A: Can you beat a sergeant: yes

// ...

A -> B: Can you beat a major: yes
B -> A: Can you beat a major: yes

A -> B: Can you beat a Lt. Colonel: no
B -> A: Can you beat a Lt. Colonel: yes



Thus both players conclude that player B wins, without B revealing the exact value of the winning piece.

Unfortunately, the game you linked to does not appear to have this property, in particular due to the "Spy". Forcing the game logic to fit a strict weak ordering would probably also reduce some of the "strategy", by eliminating such interesting ranks; potentially making the game considerably less fun.

Maybe there is a clever way to handle such a case, but I cannot see it. The protocol would have be modified such that if a spy would lose, the spying peer can "reveal" the spy to allow the protocol to continue. Such an implementation would reduce the information being leaked to "just" spies (though they are quite a notable piece).

For example, player A has a their officer level piece (e.g. "Sergeant") and player B has a spy. The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes

A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: no, but I am a spy

A -> B: Can you beat a private: yes
B -> A: Can you beat a private: no, but I am a spy

A -> B: Can you beat a sergeant: no
B -> A: Can you beat a sergeant: yes


So the sergeant would be removed.

Maybe some of the uncertainty could be reclaimed by adding more special pieces to the mix, though the protocol itself might break down entirely too. Just thinking out loud, I may have made a mistake in my reasoning.

### #10hplus0603  Moderators   -  Reputation: 5309

Like
0Likes
Like

Posted 18 April 2013 - 09:52 PM

That's very open to cheating. I can pretend to have another piece, and thus get a good read on what your piece is.
The same holds for the Millionaire's problem -- if I can force a comparison with an arbitrary value, I can gain information.

If it were me, I wouldn't worry about players who are attaching to my game and reading that level of game state out of RAM.
If you need to play this for money or in tournament play, play should be on controlled hardware (e g in a physical location.)
For casual play, someone cheating online will just end up getting matched against other players also cheating online if your matchmaking is good enough :-)
enum Bool { True, False, FileNotFound };

### #11Hodgman  Moderators   -  Reputation: 30388

Like
0Likes
Like

Posted 18 April 2013 - 10:11 PM

That's very open to cheating. I can pretend to have another piece, and thus get a good read on what your piece is.
But he's got a secondary system to detect lies at the end of the game. So you can gain extra information, but you'll end up being disqualified at the end of the match when your lie is exposed.

### #12rip-off  Moderators   -  Reputation: 8224

Like
0Likes
Like

Posted 19 April 2013 - 02:53 AM

Yes, I was assuming there would be a anti-cheating mechanism in the end game as Hodgman described.

In addition, an assumption I made that I perhaps wasn't clear on is that the protocol would only be started once one peer commits to making a move. Thus the gamestate is altered by running it, so one cannot query your peer in a speculative manner for the value of an arbitrary piece.

### #13hplus0603  Moderators   -  Reputation: 5309

Like
0Likes
Like

Posted 20 April 2013 - 08:50 PM

Yes, it seems like that will work for a system where you can assign a unique score to each piece and the strength is fully linear.
I don't quite see how that can be adapted to partial ordering graphs, or cycles, like the spy unit in Stratego, though.
Maybe someone has a really smart solution for that?
enum Bool { True, False, FileNotFound };

### #14rip-off  Moderators   -  Reputation: 8224

Like
0Likes
Like

Posted 21 April 2013 - 11:50 AM

There is weakness in that protocol compared with the ideal of having a trusted third party resolve the combat. While it (mostly) protects the identity of the winning piece, it leaks the precise identity of the losing piece. This means with each win the winner gains an additional data point, they know how many pieces of a given rank have been eliminated, allowing the winner to slowly build a better statistical model of the pieces that remain than they could with the trusted third party.

I would note that this is at least "fair" in that both players can potentially benefit from it, even though it unfortunately benefits a player who is doing better. However I feel this could be an acceptable trade-off to achieve peer to peer play in the absence of a trusted third party.

If we accept this limitation, I believe I have developed a modified protocol which protects the identity of the spy in the "Game of Generals" linked in the OP, however it allows for the identity of the Sergeant to be revealed in some circumstances.

First, flag combat is "easy" as it always ends the game. If either peer is using a flag, they must reveal that information and the game ending can be determined immediately. Please note that this might not be strictly necessary, it might naturally fall out of the rest of the protocol, but let us treat this as an early special case to simplify.

That case aside, the protocol begins at the first officer rank (i.e. Sergeant), rather than the "lowest" rank. Instead of asking if one can beat the rank, ask if one would lose to this rank. Identical ranks "lose" to one another in this protocol.

In general, if both peers say "I would lose", then it is a draw and both pieces are eliminated. If both players say "I would not lose", test the next highest rank. Otherwise, the combat is resolved and the piece belonging to the peer who said "I would lose" is eliminated.

When all the officer ranks are exhausted without conclusively determining the combat, then both pieces are removed as they must both be spies. This does not leak information, even with a trusted third part when any two pieces are removed together each player knows that their opponent had the same piece.

I believe this handles all the cases where an officer better than a Sergeant and a Spy are involved. However when there is a draw or a loss on the first round, we have ambiguity. We know that one of the peers has a piece that would lose to a Sergeant, but there are two pieces that qualify, a Sergeant and a Private. We also have to handle the case where a Spy, who can beat a Sergeant, loses to a Private.

If both players say "I would lose" on the first round, there are the following combinations:

• Private VS Private

• Sergeant VS Private

• Sergeant VS Sergeant

We can resolve this by getting each player to reveal the identity of their piece. Here is the case that leaks information compared with the previous protocol, where a Sergeant eliminates a Private, the losing player has learned the location of the Sergeant. The other two cases do not leak information for the same reason as the spy case above.

Where one player says "I would not lose" and the other says "I would lose" on the first round, we have the following cases:

• Private VS (Officer > Sergeant)

• Private VS Spy

• Sergeant VS Spy

• Sergeant VS (Officer > Sergeant)

Let the "losing" player reveal the identity of their piece. If it is a Sergeant it must lose either case. If it is a Private, the "winner" must specify whether they have a Spy (i.e. a boolean piece of information, they do not need to reveal the identity of their piece if it is not a spy). Resolve the combat as per the game rules. Note that this isn't leaking information compared with a trusted third party, in any case a Private wins without also being eliminated, we can infer the losing piece must have been a Spy.

This revised protocol still has the property that the exact nature of the losing piece is revealed in all cases. However, we no longer leak the identity of the Spy (until it is killed, and as noted these cases are obvious even with a trusted third party). In the context of the overall game rules, this is much better than revealing the identity of the spy in every combat. There is only a single sergeant, and it is (arguably) the second least interesting/valuable piece. There are two spies, and they are probably the most interesting piece - their potential presence puts one into a real dilemma about whether there is an easily defeated spy rampaging through one's officers or a high ranking piece which can only be defeated with similar strength.

Unless I've made a mistake in my reasoning somewhere?

Edited by rip-off, 21 April 2013 - 11:54 AM.
Forum is eating my list formatting

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS