This is the second post in a set of blog posts about mental poker. The previous post can be found here: Mental Poker - An overview of approaches.
Following on from the previous discussion about the general approaches to mental poker, this post takes a deeper look on what is actually required to randomly generate a card in a distributed way. Firstly, standard ElGamal encryption is discussed before investigating how it can be modified to work in a distributed setting.
Warning - Here be dragons. If you are not interested in an overly verbose look into how each step could work then save yourself and get out now. If you're interesting in learning more about the maths behind random card generation then read on!
As discussed in the previous post, the multiplicatively homomorphic property of the ElGamal encrpytion scheme is the key ingredient that enables individuals encypted card choices to be combined to form a global card choice. The standard version of ElGamal encryption is an asymmetric key encryption algorithm, hence a public and private key pair must be generated in order to encrypt and decrypt messages. In order for Bob to send Alice an encrypted message the three components must be combined:
ElGamal encryption is defined over a cyclic group \(G\) of order \(q\), where \(q\) is usually a large prime. In order for Alice to receive messages that only she can decrypt she must first generate the key pair as follows:
The public key consists of the quadruple \((G,q,g,h)\) which is then published and becomes known to Bob. The private key \(x\) is (obviously) kept secret.
Given Bob has learned Alice's public key, he can now send her a message \(M\) via the following steps:
The ciphertext that Bob sends to Alice is the pair \((c_1,c_2)\). Note that if someone knows the mapped plaintext value \(m\) and the cipher text \((c_1,c_2)\) then they can easily work out the ephemeral key \(s\) by computing \(s = c_2m^{-1}\). Hence, as the name suggests, ephemeral key \(s\) (and \(k\) value) should be computed every time a message is sent.
Given Alice has recieved Bob's ciphertext \((c_1,c_2)\), she can decrypt it using her private key \(x\) as follows:
As noted above, during the encryption phase any plaintext message \(M\) must be first mapped to some value \(m \in G\) in a reversible way. As \(g\) is a generator for \(G\), we know that \(g^i \in G\). Furthermore, for the application of mental poker, we know that the the plaintext messages \(M\) will always represent card choices, and hence the message space is reduced to integers in the set \(\{1,...,52\}\). Thereforewe the reverse mapping function can be acquired by simply computing the two way map from all card choices \(\{i\}_{i=1}^{52}\) to their mapped messages \(\{g^i\}_{i=1}^{52}\) and performing lookups of each \(m\) or \(M\) value when necessary.
The standard ElGamal encryption scheme above assumes communication between two parties. However in the mental poker setting we have a variable number of players, usually between 2 and 8, and hence the scheme needs to be adjusted to enable joint encryption and decryption.
This can be achieved by creating a sharded private key which is distributed amongst all players using Pedersen’s protocol. Given \(n\) parties, Pedersen's protocol generates a distributed ElGamal key pair with private key \(x\) defined as: \[x = \sum_{j=1}^n x_j \mod q\] Each player \(P_j\) learns a unique share \(x_j\) of the distributed private key, meaning that no single players or subset of players can know the entirety of \(x\). The public key \(h\), by definition, becomes known to all players. Hence this adjustment allows all players to collectively encrypt a message \(M\) in such a way that the result can only be decrypted by all players jointly.
From Pedersen’s paper, the first step towards generating the ElGamal key pair is choosing a prime pair \((p,q)\) such that \(q\) divides \(p-1\). The simplest way to do this is to find a safe prime \(p\) of the form \(p=2q+1\) by repeatedly selecting a random, sufficiently large prime \(q\) until \(p=2q+1\) is also prime.
The next step is to choose a generator function \(g\) of a cyclic subgroup \(G\) of \(\mathbb{Z}^*_p\) such that \(G\) has order \(q\). Algorithm 4.80 from the Handbook of Applied Cryptography provides a way for us to compute a generator of \(\mathbb{Z}^*_p\):
Input: A cyclic group \(G\) of order \(n\), where \(n\) has prime factorization \(n = p_1^{e_1} p_2^{e_2}... p_k^{e_k}\)
Output: A generator \(\alpha\) of \(G\)
- Choose a random element \(\alpha \in G\)
- For \(i = 1,...,k\):
- Compute \(b ← \alpha^{n/{p_i}}\)
- If \(b = 1\) then go to step 1
- Return \(\alpha\)
As we have \(G=\mathbb{Z}^*_p\) with order \(p-1\) we know that the prime factorisation is \(2q\). Therefore there can be at most two iterations within step 2 and hence we only have to check that the two conditions hold: \[\alpha^{\frac{p-1}{2}} = \alpha^q \ne 1\] \[\alpha^{\frac{p-1}{q}} = \alpha^2 \ne 1\]
One final step remains: transform the generator \(\alpha\) of \(\mathbb{Z}^*_p\) into our desired generator \(g\) of \(G\). This can be achieved using the relation: \[g = \alpha^{\frac{p-1}{q}} \mod p\] \[ = \alpha^2 \mod p\] The above means that we now have the required \((p,q,g)\) for Pedersen's protocol. For brevity, the exact method by which these variables are decided upon between players is mainly skipped over here. A simple but not so rhobust approach is to have a random player perform the calculations and propose these, with the the players being able to validate the size and correctness of the chosen values.
Note: Seeing why this relation holds requires a quick crash course in groups and generators. \(\mathbb{Z}_n\) represents the group of integers modulo \(n\), i.e. \(\mathbb{Z}_n = \{0,1,...,n\}\). An integer \(x \in \mathbb{Z}_n\) is called a unit (and has an inverse) if the greatest common divisor of \(x\) and \(n\) is \(1\), i.e. \(\gcd(x,n)=1\). \(\mathbb{Z}_n^*\) represents the set of all units of the group \(\mathbb{Z}_n\).
This group is closed under modular multiplication. That is, for units \(x_1\) and \(x_2\), the element \(x_1 x_2 \mod n\) is also a unit and therefore in the group \(\mathbb{Z}_n^*\). Clearly, for some prime \(p\), we know that \(\mathbb{Z}_p^*\) has order \(p-1\) as \(\gcd(x,p) = 1 \, \forall \, x \in \{1,...,p-1\}\).
Given we have an efficient generator \(\alpha\) of \(\mathbb{Z}_p^*\) we know that \(\{\alpha^i\}_{i=0}^{p-1}\) describes the group \(\mathbb{Z}_p^*\). It follows that the generator \(g = \alpha^{\frac{p-1}{q}} \mod p\) describes a subgroup of \(\mathbb{Z}_p^*\) with order \(q\). The final deduction can be done using the fact that \(\mathbb{Z}_p^*\) is a cyclic group and that a subgroup of a cyclic group is itself a cyclic group. Therefore we know that \(g\) is an efficient generator of the cyclic group \(G\) with order \(q\).
As the card choice is generated via combining each players individual card choices there is good reason to ensure that players cannot change their choice after seeing others. In reality this is unlikely as each choice is encrypted so an attacker should not be able to deduce any information to help them change their initial choice, however a second layer of protection can still be added in via cryptographic commitments. These essential lock each player into their original choice in a verifiable way, preventing any retrospective changes. It also ensures that each player has actually submitted a card choice before anyone reveals their value.
A commitment scheme is a two party protocol that allows a committer Alice to send an unintelligible representation of a message \(m\), denoted by \(C(m,r)\), to a receiver Bob and a later date reveal the message \(m\) (by ‘opening’ her commitment).
Two key properties of a commitment scheme are unconditional hiding and computational binding. That is, the following two properties should hold:
A commitment is said to be non-malleable if, for a given commitment \(C(m,r)\) to message \(m\), it is impossible to efficiently generate a related commitment \(C(m',r')\) for message \(m'\). This property prevents any man-in-the-middle (MIM) attacks in which a malicious user can intercept and replace Alice’s messages to Bob without Bob discovering. Note that the risk of MIM attacks can be somewhat offset using other mechanisms such as end-to-end encryption of messages between parties.
One commitment scheme that shares many similarities with the ElGamal encryption scheme above is Pedersen commitments. The steps for Alice to make a Pedersen commitment to value m and send to Bob are as follows:
Bob chooses the public parameters:
Alice makes a commitment to a value \(m\):
At a later date, when Alice wants to open her commitment, she can send the values \((m,r)\) to Bob. Bob can then compute \(c' = C(m,r)\) using these values and verify that \(c'\) matches Alice's original commitment \(c\). If Alice attempts to change her message from the original value \(m\) then \(c' \ne c\) and Bob will know she is lying and terminate the session.
The above can now all be put together to form the protocol to generate the public and distributed private ElGamal encryption keys:
The private key is formed from the combination of all private key parts: \(x = \sum x_i \mod q\) which can only be known by someone who knows all private key parts. Therefore a ciphertext can only be decrypted if all participants work together. Furthermore, as long as there exists a player \(P_i\) that chooses their private key part \(x_i\) at random then the distribution of the private key \(x\) is computationally indistinguishable from the uniform distribution.
Note that the mental poker application somewhat simplifies the requirements of the key pair as, due to collusion, we do not require nor desire the private key to be recoverable by a subset of players. That is, no threshold scheme is required.
Within the distributed key setting encryption works similarly to normal ElGamal. The main difference is that, due to the homomorphism of the encryption scheme, a shared and unknown encrypted message is created by combining each players individual encrypted messages.
In the mental poker scenario, we have each player \(P_i\) randomly choosing their card choice \(c_i\). Using the mapping function defined above, the partial encryption of each card choice is defined as \(E(c_i) = (g^{r_i}, g^{c_i}h^{r_i})\), where \(r_i\) is \(P_i\)'s private ephemeral key and \(h\) is the shared public key.
The jointly encrypted final card choice \(c\) is defined as: \[E(c) = E(\sum c_i) = \prod E(C_i) = (\prod g^{r_i}, \prod g^{c_i}h^{r_i})\] As all arithmetic is done modulo \(p\) the final card choice \(c\) will a random card choice, unknown to all players.
Once \(E(c)\) has been computed, it can only be jointly decrypted by all the holders of the private key parts. For a given ciphertext \(E(c) = (\alpha, \beta)\) as above, the complete decryption of plaintext message \(m\) is defined as: \[m = D(\alpha, \beta) = \frac{\beta}{\alpha^x} = \frac{\beta}{\alpha^{\sum x_i}} = \frac{\beta}{\prod \alpha^{x_i}}\] Therefore, each player can partially decrypt the message using their private key part \(x_i\) by computing the value \(\alpha^{x_i}\). Due to the discrete logarithm problem, this value is assumed to not reveal any information about each players private key part \(x_i\). The final plaintext card choice \(c\) can be obtained by combining these partial decryptions, computing the message \(m\) and then using the previously computed set \(\{g^i\}_{i=1}^{52}\) to reverse map \(m\) to \(c\).
This allows the final card choice \(c\) to be either dealt face up the table, via having everyone broadcasting their partial decryptions, or to a single player \(P_j\) face down, via having all other players share their partial decryption with \(P_j\).
Given this tidal wave of information, it should now be possible to deal a single card in a game of mental poker. Obviously there is far more to do but thankfully a lot of the heavy lifting is done. The next challenge is determining whether a subsequently generated card \(c'\) matches any cards already in play. Despite sounding simple, this task becomes quite involved as the only values available are the list of encrypted cards in play and \(E(c')\). The next blog post will aim to tackle this and move closer towards a complete mental poker protocol.