4
$\begingroup$

I'm trying to design a zero-knowledge protocol for the creation of a shuffled deck of cards for use by two players. Naturally this requires that neither player knows the order of the cards after the shuffle, nor what card was drawn by the other during play, but I'd also like to be able to do this without needing a trusted third party as well.

My best efforts so far only require a trusted third party ("dealer") for game set up (which is better than requiring a dealer for every draw) but I'd love to be able to remove even that, if possible!

My protocol so far — game set up:

  1. Both players send their public keys to the dealer.
  2. Dealer generates 52 AES keys for player 1, and 52 for player 2.
  3. Dealer pairs off the keys for player 1 and 2, and XORs them to make 52 combined keys.
  4. Dealer pairs off each of the (shuffled) cards ("K♥", "2♣️", "A♦", …N) with each of the combined keys, and symmetrically encrypts the card with the key — this is the "shuffled deck".
  5. Dealer encrypts all player 1's keys (in order) for player 1's eyes only using their public key, then does the same with player 2.
  6. Dealer publishes these two encrypted blocks, and the shuffled deck (signed with a dealer's key, to demonstrate authenticity) — this is used by the players for their game, and is the end of the need for the dealer.

Protocol for player 1 "drawing a card":

  1. Player 2 decrypts their key stack (with their private key), finds the top-most unused AES key from their list (recording it as "dealt to player 1") and shares it with Player 1.
  2. Player 1 decrypts & finds their top-most unused AES key from their own list in the same way, recording it as used by themselves, and XORing it with the received key from Player 2.
  3. Player 1 uses this combined key to decrypt the top-most unused card from the "shuffled deck" and now has drawn a card!

(Player 2 does not know what the card is, so when player 1 plays that card in-game, they can prove it's genuinely one they've drawn by sharing the relevant AES key back to player 2, so they can validate)

Can anyone offer a suggestion as to how I could approach removing the need of a trusted third party for the initialisation, so neither player is advantaged?

[I think this is a "zero-knowledge" problem — but I'm not certain of terminology, please do edit or let me know if you think there are better tags!]

$\endgroup$
3
  • 2
    $\begingroup$ The thing you're looking for is Mental Poker. I've deleted my answer after discovering it's just a re-implementation. $\endgroup$ Commented Jul 16, 2023 at 15:17
  • 1
    $\begingroup$ See also crypto.stackexchange.com/questions/15289/… for some practical advice on a specific cipher. See also crypto.stackexchange.com/questions/6573/… (though frustratingly, most of the answers seem to devolve into "this can only be secured if the commutativity isn't exploitable in the protocol" without explaining how to achieve that; my suspicion is it's an open question.) $\endgroup$
    – Rob Napier
    Commented Jul 16, 2023 at 16:19
  • 2
    $\begingroup$ This is a reasonable intro hackmd.io/@nmohnblatt/SJKJfVqzq and leads to a library implementing their solution. It looks like this is a fairly well solved problem. $\endgroup$ Commented Jul 16, 2023 at 18:16

1 Answer 1

3
$\begingroup$

Mental poker is a fairly well studied problem in cryptography.

There are existing libraries that implement it:

One approach is to use a commutative encryption system. Suppose Alice and Bob are playing a card game. They can choose a set of numbers to represent their cards and then each picks a pair of encryption and decryption functions. The function pairs each one chooses are inverses so $Dec(Enc(x))=x$ and they're commutative so $Enc_A(Enc_B(x))=Enc_B(Enc_A(x))$. One reasonable option is for encryption to be multiplication of a group element by a secret scalar value in a prime order group. So $Enc_A(A)=xA$ where $A$ is some input point and $x$ is Alice's secret scalar value. Decryption is similarly multiplying by the multiplicative inverse of $x$. The group used can be an elliptic curve, Diffie-Hellman group or similar.

The group must be one where the DDH(Decisional Diffie–Hellman assumption) is hard.

  • Bob gives alice two points $A$ and $B$ where $A\neq B$.
  • Alice has some public key $Y$ known to Bob where $Y=xG$.
  • Alice computes $A'=xA$ and $B'=xB$ then gives Bob either $(C,D)=(A',B')$ or $(C,D)=(B',A')$.
  • Bob cannot tell which order the encrypted points are in. In fact he cannot tell them apart from randomly chosen points.

The usual approach to mental poker then is to use such a scalar multiplication encryption function to encrypt a set of values representing the cards, then shuffle the encrypted values. Bob cannot tell which outputs correspond to which inputs. Alice must also prove that the shuffled outputs are a valid shuffling of the correctly multiplied input points and not just some points she chose at random, but that can be done with zero knowledge proofs without revealing the shuffling permutation. Alice, Bob and any other participants who want to ensure the deck is honestly shuffled perform this "encrypt and shuffle" operation sequentially to produce the final encrypted deck.

A concrete implementation of the above might be:

  • Cards are represented by a set of 52 randomly chosen elliptic curve points $C[i],\{i=0\ ...\ 51\}$
    • No one knows the discrete log of these curve points. They can be chosen via hash to curve or similar.
  • Alice chooses a public key $Y_a=x_aG$
  • Bob chooses a public key $Y_b=x_bG$
  • Alice takes the $C[i]$ points, multiplies them by her private scalar $x_a$, shuffles the results, giving these points to Bob
  • Bob takes those points, multiplies them by his private scalar $x_b$, shuffles the results and these become the shuffled, masked deck points.
  • Alice and Bob produce proofs that their output points are a valid shuffling of the multiplied input points.
  • to unmask a masked card, divide it by both $x_a$ and $x_b$ in any order then match the result against the $C[i]$ array.
    • Alice or Bob can perform one division along with a proof of correctness) then hand this to their peer. Now only the peer knows that card's value.
  • to find a card (EG:ace of spades) in the shuffled deck. Take that card's $C[i]$ point and multiply by $x_a$ and $x_b$ then find that point in the shuffled deck. The last multiplication can be performed by one peer and not shared so only they have that information.

Re-shuffling without decrypting

Because encryption and decryption operations are order independent, cards can be re-encrypted and re-shuffled without revealing their value. If the current combined encryption key is $x=x_a x_b$, Alice and Bob can choose a new $x_a'$ and $x_b'$ to give a new masking key $x'=x_a 'x_b'$.

Cards can be converted to the new masking key by multiplying by $x'/x$. In practice each participant multiplies by their own $x_p'/x_p$. This can be combined with distributed shuffling operations.

As an example, suppose that some discarded cards are to go back to the deck which is then re-shuffled.

  • The discard cards and all deck cards are put through a distributed shuffle.
  • cards held by players are just multiplied with no shuffling.

An individual player can change their own masking key individually while perhaps, shuffling their own hand of cards and re-masking everyone else's. This is useful in games like go fish where cards are not acquired all at once.

When re-shuffling the deck though all players must change their masking key and contribute to the distributed shuffle or other players could cooperate to load the deck against them.

Multiplication proofs

Multiplication proofs are used during distributed encryption/decryption to prove that a multiplication is correct.

To prove that some list of points $[A,B,C,...]$ when multiplied by $x$ produces $[A',B',C',...]$ where $Y=xG$ is the relevant public key:

  • $R_1=eY+sG$
  • $R_2=eA'+sA$
  • $R_3=eB'+sB$
  • $R_4=eC'+sC$
  • $...$
  • $e=Hash(Y||R_1||A||A'||R_2||B||B'||R_3||C||C'||R_4\ ...)$
    • Note that the points that are part of the proof must be included in the challenge generation process so they can't be changed in response to the pseudorandom challenge.

If the recipient already has $Y$ and the $[A,B,C,...]$,$[A',B',C',...]$ arrays, the proof only requires sending $(e,s)$. You can also skip the $Y$ equation if all you're doing is proving the hidden scalar $x$ is the same for all the relations.

Proving shuffle correctness

There are a number of interactive and non-interactive protocols to prove a shuffle and encrypt operation is valid. Searching for "mental poker nizk shuffle proof" will turn up some good results.

Current proofs are really quite nice and scale quite well but are quite complicated to implement correctly.

Efficient Zero-Knowledge Argument for Correctness of a Shuffle

  • O(sqrt(n)) proof size
  • verification for a 100,000 element shuffle in about 2 minutes.
  • includes references to other shuffle proofs

If you want something simpler, the following approach gives $O(N*log2(n)^2)$ proof size and verification time roughly

easy to implement shuffle proof

Assume Bob gives Alice two points $A$ and $B$ where $A\neq B$. Alice has some public key $Y$ known to Bob where $Y=xG$. Alice computes $A'=xA$ and $B'=xB$ then gives Bob either $(C,D)=(A',B')$ or $(C,D)=(B',A')$.

Alice can construct something of a cross between a DH tuple proof and a ring signature to show that either $P=xA$ or $P=xB$ for some point $P$. Two such proofs for the points $(C,D)$ will convince Bob that Alice gave him a valid shuffling as long as $C\neq D$.

Here's the equations for that:

  • $Bind=Hash(Y||P||A||B)$
    • This prevents the prover from changing their input points during the proof
  • $R_{1a}=e_1Y+s_1G$
  • $R_{1b}=e_1P+s_1A$
    • This set of equations can be solved if $P=A'$
  • $e_2=Hash(Bind||R_{1a}||R_{1b})$
  • $R_{2a}=e_2Y+s_2G$
  • $R_{2b}=e_2P+s_2B$
    • This set of equations can be solved if $P=B'$
  • $e_1=Hash(Bind||R_{1a}||R_{1b})$

Like in a ring signature, set 1 generates a challenge for set 2 and set 2 generates a challenge feeding back into set 1. Only one set has to be solved to create a valid proof though so a valid ring proof proves either $P=xA$ or $P=xB$.

Obviously you can add more equations to the ring to prove a given $P$ is the scalar product of one of $N$ points but this scales poorly. To shuffle $N$ points this way requires $O(N^2)$ equation sets ($N$ proofs with $2*N$ equation sets each). A Sorting Network-like structure can be used instead. The number of equation sets required scales with $N*log(N)^2$, which is much better.

One complication is that each 2-way shuffle involves a multiplication. Alice can choose a secret scalar $z$ and perform all the two way shuffles using that $z$. The output points can then be multiplied by $x/z^{layer\_count}$ to correct for this. Alternately fix things up by using a corrective multiplication factor in the last layer of shuffles. When shuffling a non-power-of-2 sized list, some points won't participate in a shuffle on a given layer. These points must still be multiplied by that layer's secret scalar before passing to the next layer.

$\endgroup$
1
  • $\begingroup$ This is a wonderful and comprehensive answer! Thank you so much! $\endgroup$
    – JP.
    Commented Jul 30, 2023 at 15:06

Your Answer

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

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