stuff/ideas

This section is meant to present some professional thoughts that might be useful for others.

Multiparty Shuffle (2011)

Multiparty Shuffle (2011)

I once asked myself whether it was possible to create a protocol without a trusted third party, where two players want to play a card game against each other, but they don't trust each other. The players are assumed to have their own card piles (a common pile should also work) and they are allowed to cheat by rearranging the cards or trying to play cards they didn't draw. Looking at cards not drawn yet is also supposed to be an act of cheating. Each player is also interested in hiding the state of the card pile (i.e. the arrangement of cards in the pile) and hiding some previously drawn cards.

The target of the protocol is to hide the states of the card piles and either prevent or detect an act of cheating.

More formally I define:
Two parties A and B (should work with more) want to play a card game G as opponents (i.e. don't want to give the other an advantage over oneself).
both have (possibly different) card piles P_A and P_B (not just one for both)
f: one-way function
s(d,P): permutation/shuffle algorithm, parametrized by d with input P (pile)
H(G): history of the game (A drew card, A played card x', ...)
: rule algorithm: check whether given the history H and piles at different time points of the game, the rules were followed (output true) or not (false)
The initial state of the card piles (pile of A at time 0) and (pile of B at time 0) is known to both parties.
The protocol goes as follows:

If we have multiple players, we should be able to do the same protocol by partitioning those players into teams A and B with and ( and being players); it shouldn't matter which player does the protocol with which player ; a player could also be responsible for a group of players , if all players in choose a player , that is responsible for ; the players wouldn't provide any nonces in that case; alternatively, one could create a common nonce of all players in , e.g. (however then each nonce must be known to player only and some number of players from A; in the end (after all nonces are sent) all nonces need to be revealed to all players involved).
If two players want to play on the same pile, we can do at about the same:
Assuming A wants to draw cards from the common card pile :

Now B wants to draw cards:

and so on...

So if the game ends or the other player wants to draw cards again, the history needs to be checked for cheaters again.
If it is important to keep the uppermost card of the pile private until the moment of drawing, we need to do a reshuffle with nonces before any drawing action.

ALSO NOTE: If the drawn cards must be unknown to both players all of the time, the above protocol doesn't work. Obviously no protocol can work in that case as one of the two players needs to control the pile and thus always knows its current state and the missing cards. This can only work for games with two card piles or by including a trusted third party into the protocol.

I did not prove the correctness of this protocol, it is just an idea. If you found a weakness or even an attack, feel free to contact me.