Generation of alignment for card games
I would like to propose to the public an algorithm for a card game that excludes “cheating”. Those. the game is generated by the participants jointly, and the “opening” of a particular card can be done only for one player.
The algorithm for simplicity is described for three people, but it is easily extended to any N> = 3.
Each player generates three random permutations: A1..3. The product A = A3 * A2 * A1 is the game layout. Now, if it is necessary to open the card with number i, the first player transfers to the second A1 (i), the second transfers to the third A2 (A1 (i)) = A2 * A1 (i), the third publishes A (i) = A3 * A2 * A1 ( i). If the card needs to be opened only for the third player - A (i) he does not publish.
The third player generates a random permutation of C3 and transfers it to the first player, and transfers the second player D3 = (C3 ^ (- 1)) * A3. Now, if it is necessary to open the card only for the second player, the first player transfers the second A1 (i), the second one passes the first one back D3 * A2 * A1 (i) and the first one calculates C3 * D3 * A2 * A1 (i) = A (i) .
')
Further, the third player generates a random permutation F and transfers it to the second player, he transfers the first player G3 = A3 * F3 ^ (- 1). Now, if it is necessary to open the card only for the first player, he sends the second A1 (i), the second one passes him back F3 * A2 * A1 (i) and the first one calculates G3 * F3 * A2 * A1 (i) = A (i).
Before the start of the game, each player publishes for each random permutation X a hash of the number X + k * n, where 0 <x <= N! -1 is the ordinal number of the permutation, n = N! - the number of permutations, k - a random large number, the “salt” of the hash. At the end of the game, players publish their permutations and k in the open and check the hashes of other players.
Algorithm limitations:
- the data exchanged between the two peers is transmitted over an encrypted channel, the certificates of the participants are known to everyone in advance.
- the possibility of collusion between the two participants should be excluded.
The algorithm for simplicity is described for three people, but it is easily extended to any N> = 3.
Each player generates three random permutations: A1..3. The product A = A3 * A2 * A1 is the game layout. Now, if it is necessary to open the card with number i, the first player transfers to the second A1 (i), the second transfers to the third A2 (A1 (i)) = A2 * A1 (i), the third publishes A (i) = A3 * A2 * A1 ( i). If the card needs to be opened only for the third player - A (i) he does not publish.
The third player generates a random permutation of C3 and transfers it to the first player, and transfers the second player D3 = (C3 ^ (- 1)) * A3. Now, if it is necessary to open the card only for the second player, the first player transfers the second A1 (i), the second one passes the first one back D3 * A2 * A1 (i) and the first one calculates C3 * D3 * A2 * A1 (i) = A (i) .
')
Further, the third player generates a random permutation F and transfers it to the second player, he transfers the first player G3 = A3 * F3 ^ (- 1). Now, if it is necessary to open the card only for the first player, he sends the second A1 (i), the second one passes him back F3 * A2 * A1 (i) and the first one calculates G3 * F3 * A2 * A1 (i) = A (i).
Before the start of the game, each player publishes for each random permutation X a hash of the number X + k * n, where 0 <x <= N! -1 is the ordinal number of the permutation, n = N! - the number of permutations, k - a random large number, the “salt” of the hash. At the end of the game, players publish their permutations and k in the open and check the hashes of other players.
Algorithm limitations:
- the data exchanged between the two peers is transmitted over an encrypted channel, the certificates of the participants are known to everyone in advance.
- the possibility of collusion between the two participants should be excluded.
Source: https://habr.com/ru/post/147241/
All Articles