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.
