This is the third post in a set of blog posts about mental poker. The previous post can be found here: Mental Poker - A deep dive into random card generation.
The previous post examined the maths behind generating a single card within a game of mental poker, and contains the majority of the building blocks for playing an entire game. By repeating this card generation process and performing partial decryptions at the correct times, a full hand of poker can be dealt and played. However one key piece of the puzzle is missing: ensuring that the same card is not dealt twice.
Clearly there is the strict requirement that the current cards (non-table) cards in play must be kept secret. As a result, hence each new card must be drawn from the entire set of 52 possible cards. This necessitates a mechanism to check a generated card choice against the list of cards in play before dealing it. The real spanner in the works here is the fact that the generated card choice along with the list of current cards in play are all random ciphertexts representing the encryptions of the card values. Two separate encryptions of the same card value will not be equal and thus the ciphertexts cannot be compared directly. Clearly, the comparison can also not be achieved via decrypting then comparing as sensitive information would be revealed.
The collision check must instead be done via an oblivious test of plaintext equality which allows the players to determine whether two ciphertexts are the encryptions of the same value, but without revealing information about the plaintext values.
A protocol to achieve this is outlined in the paper by Jakobsson and Juels. The ideas in the paper nicely map to the distributed setting of mental poker and the chosen ElGamal encryption scheme described in the previous post. Given two ciphertexts \(E(m_1)=(a_1,b_1)\) and \(E(m_2)=(a_2,b_2)\), the protocol allows the joint holders of the decryption key to determine whether \(m_1=m_2\) without revealing any other information.
The fundamental idea behind the protocol is to combine the two ciphertexts \((a_1,b_1)\) and \((a_2,b_2)\) into a single ciphertext \((\epsilon,\gamma)=(\frac{a_1}{a_2}, \frac{b_1}{b_2})\) which has the useful property that it decrypts to 1 if, and only if, the original plaintexts \(m_1\) and \(m_2\) are equal. The combined ciphertext can be jointly decrypted by all participants using the same approach as revealing a chosen table card (explained in the previous post).
To avoid any information leakage about the plaintext messages, each player ‘blind’ their copy of the combined ciphertext using some randomly chosen blinding exponent before performing a partial decryption.
More formally, given the combined ciphertext \((\epsilon,\gamma)\), each player \(P_i\) computes their blinded ciphertext \((\epsilon_i,\gamma_i)=(\epsilon^{z_i},\gamma^{z_i})\) for some randomly chosen blinding exponent \(z_i\) which is not known to any other player. All players can then jointly decrypt the ciphertext \((\epsilon',\gamma')=(\prod\epsilon_i,\prod\gamma_i)\) to perform the oblivious test of plaintext equality.
Performing this ciphertext blinding phase adds noise to the decryption step whilst still retaining the necessity property of decrypting to 1 if, and only if the plaintexts are equal. This can be proven as follows:
Using the information provided in the previous post, the two ciphertexts representing \(E(m_1)\) and \(E(m_2)\) are defined as: \[(a_1,b_1)=(g^{r_1},h^{r_1}m_1)\] \[(a_2,b_2)=(g^{r_2},h^{r_2}m_2)\] for some ephemeral keys \(r_1\) and \(r_2\). The initial combined ciphertext can therefore be written as: \[ (\epsilon,\gamma)=(g^{r_1-r_2},h^{r_1-r_2}\frac{m_1}{m_2})=(g^{r_3},h^{r_3}\frac{m_1}{m_2}) \] for some random ephemeral key \(r_3\). Clearly if \(m_1=m_2\) then \((\epsilon,\gamma)=(g^{r_3},h^{r_3})=E(1)\).
If we raise the combined ciphertext to a random exponent \(z\) then we have: \[(\epsilon',\gamma')=(\epsilon^z,\gamma^z)=(g^{r_3z},h^{r_3z}(\frac{m_1}{m_2})^z)=(g^{r_4},h^{r_4}(\frac{m_1}{m_2})^z)\] for some random ephemeral key \(r_4\). If \(m_1=m_2\) then we have: \[(\epsilon',\gamma')=(g^{r_4},h^{r_4})=E(1)\] If \(m_1 \ne m_2\) then \((\epsilon',\gamma')\) will represent the encrpytion of the message \((\frac{m_1}{m_2})^z\). Hence the necessary property still holds.
From the paper, the full protocol to perform a distributed oblivious test of plaintext equality on two ciphertexts as above is:
Step 4 contains a majority of the complexity of this protocol. Clearly, as the player \(P_i\) cannot reveal their chosen parameters they must employ some oblivious proof for this (turtles all the way down...). The paper suggests this can be achieved using a referenced protocol and a zero-knowledge proof.
The main purpose of these steps is to prevent a malicious party from broadcasting some random, invalid value for their blinded ciphertext in step 3. If they are able to do this then the combined ciphertext \((\epsilon',\gamma')\) will not decrypt to \(1\) and therefore any collision check between two cards will always return false.
If we naively assume that a player will not be malicious and return an invalid value then the protocol can be greatly simplified. This is obviously not desirable but for the sake of an initial implementation it can be temporarily put aside.
The simplified protocol then becomes:
Note that it may seem like there is no edge that can be gained from such an attack as the proposed card is only decrypted and revealed after the collision check has been performed. However, due to the fact that a round must be voided and restarted when an invalid card is discovered, a malicious user can disrupt the collision check to attempt to force an invalid card to be dealt. For example if a player is in a large pot against another opponent and doesn't think they will win, they can force the collision check of the next dealt card to return false in an attempt to void the round and get their money back.
For the benefit of the reader (read: myself) I have refrained from going into the full protocol too much. This simplified protocol gives an initial mechanism to prevent collision checking which, along with the information provided in the previous post, can be used as the building blocks of an implementation.