Commutative encryption and decryption

El Gamal Public Key Cryptosystem

The El Gamal public-key encryption scheme can be viewed as Diffie-Hellman key agreement in key transfer mode. Its security is based on the intractability of the discrete logarithm problem and the Diffie-Hellman problem.

Diffie-Hellman Key Exchange

The first system to make use of public-key or asymmetric cryptographic keys was the Diffie-Hellman algorithm (by Whitfield Diffie and Martin Hellman, 1976). These systems overcome the difficulties of private-key or symmetric key systems because asymmetric key management is much easier. In the symmetric key system it’s important for both sides of the communication to have identical keys; the secure exchange of the keys has always been a huge concern. This concern is alleviated using asymmetric key systems because they use two keys – one called the private key that secretly belongs to the user and another called the public key that can be shared with the world and thus is distributed without difficulty. Regrettably, the pros of asymmetric key systems are overshadowed by speed – they are very slow for any type of bulk encryption. Presently, the typical practice is to use a symmetric system to encrypt the data and then encrypt the symmetric keys used for distribution with an asymmetric system. And this is what Diffie-Hellman key exchange does.

Basic El Gamal encryption

Complete Diffie-Hellman Key Exchange Process

The Game: Mental Poker

Playing the game of poker without any cards over a telecommunications device (phone or more realistically internet) is known as Mental Poker. The game usually doesn’t include a trusted third party dealer or a source of randomness and as such it seems that someone (the dealer) will always know what cards have been given out or alternatively, that players will be able to lie about the cards they have.

The first serious attempt at the problem was by Adi Shamir, Ronald Rivest and Leonard Adleman in 1979 in [SRA]. It’s this scheme, which relies on commutative encryption. The authors first proved, in an information theoretic sense, that the problem is unsolvable and then went on to offer a solution. Their protocol worked for two players and didn’t require a trusted third party. However, it did not offer confidentiality of strategy, requiring the players to reveal their hands at the end of each game.

We assume two players and fifty-two cards. Five cards are dealt then one round of betting then all cards shown. Players have disjoint hands, any player can have any possible hand, no player can discover another players hand and any collusion has minimal effect.

The SRA protocol was shown to leak at least one bit of information: whether the card was a quadratic residue or not. There were suggestions to overcome this problem but there was still no guarantee that other information was not leaked.

The SRA protocol

The protocol relies on a commutative encryption scheme i.e.:

EA(EB(M)) = EB(EA(M))

Where EX denotes encryption using X’s public key. Likewise, we use DX to denote decryption using X’s private key.

Steps

1. Two players Alice and Bob together choose a large prime number n, then Alice chooses her key A s.t. gcd(A,n-1) = 1 and Bob chooses B similarly.
2. Encode the 52 cards as integers.
3. Encryption EA(M) = MA (mod n)
4. Decryption DA(M) = Minv(A) (mod n)
5. Bob permutes the cards to x1, x2, …, x52 encrypts them then sends to Alice EB(xi).
6. Alice chooses 5 cards for herself, encrypts them and sends to Bob EA(EB(xi)). Also chooses 5 cards for Bob and sends them to him (without encrypting) EB(xi).
7. Bob can now decrypt his cards to see his hand DB(EB(xi) = xi. He also decrypts Alice’s cards then sends them back to her. Here is where we need commutativity so DB(EA(EB(xi))) = EA(xi)
8. Alice receives her cards and decrypt them seeing her hand DA(EA(xi)) = xi.

Implementation of Game

Protocol Security

Efficiency of El Gamal encryption

The encryption process requires two modular exponentiations, namely ak mod p and (aa)k mod p. These exponentiations can be sped up by selecting random exponents k having some additional structure, for example, having low Hamming weights. Care must be taken that the possible number of exponents is large enough to preclude a search via a baby-step giant-step algorithm.

A drawback of El Gamal encryption is that there is message expansion by a factor of 2, i.e., the ciphertext is double the length of the corresponding plaintext.

Randomized Encryption

Among many other encryption schemes, El Gamal encryption utilizes randomization in the encryption process, an example of others include: McEliece encryption, and Goldwasser-Micali, and Blum-Goldwasser probabilistic encryption. Deterministic encryption schemes such as RSA may also utilize randomization in an effort to avoid some attacks. The basic idea behind randomized encryption techniques is to use randomization to increase the cryptographic security of an encryption process through one or more of the following methods:

1. increasing the effective size of the plaintext message space;
2. precluding or decreasing the effectiveness of chosen-plaintext attacks by virtue of a one-to-many mapping of plaintext to ciphertext; and
3. precluding or decreasing the effectiveness of statistical attacks by leveling the a priori probability distribution of inputs.

Security of El Gamal Encryption

The problem of breaking the El Gamal encryption scheme, specifically, recovering m given p, a, aa, ?, and d, is equivalent to solving the Diffie-Hellman problem. In reality, the ElGamal encryption scheme can be seen as merely comprising a Diffie-Hellman key exchange to verify a session key aak, and then encrypting the message by multiplication with that session key. Hence, the security of the El-

Gamal encryption scheme is said to be based on the discrete logarithm problem in mathbb{Z}_p !,*, although such an equivalence hasn’t been verified.

It is vital that different random integers k be used to encrypt different messages. Assume the same k is used to encrypt two messages m1 and m2 and the resultant ciphertext pairs are (?1,d1) and (?2,d2). Then d1/ d2 = m1/m2, and m2 could be easily computed if m1 were known.

Analysis of Mental Poker

Upon receiving the shuffled and encrypted pack of cards she can’t tell which is which, therefore, she picks randomly, that is, she is unable to see Bob’s hand. When Bob receives Alice’s double encrypted hand he would be unable to read it even when he partially decrypts it. But is there information leaked by the encryption process? Yes! It’s known as Quadratic Residues.

Quadratic Residues

An integer a, not divisible by an odd prime p, is a quadratic residue modulo p if there is a b in {1, 2,…, p-1} s.t. a = b2 (mod p). Otherwise a is a quadratic no residue.

So for p = 11, 1=12, 3=52, 4=22, 5=42, 9=32 are the quadratic residues and 2, 6, 7, 8, 10 are the quadratic no residues.

This works in general. For a prime p there are (p-1)/2 of both residues and no residues.

Cheating

• In 1981 R. Lipton showed for odd k, xk is a quadratic residue mod p if x is a quadratic residue mod p.
• So the cards whose representations are quadratic residues are still quadratic residues when they are encrypted.
• This allows Alice to find the cards that are residues and no residues, for the particular p used, and then choose (on average) high cards for herself and low cards for Bob.

Cheat Prevention

• The easiest way to prevent the attack we have discussed is to only represent cards with quadratic residues. However other, more general attacks have been shown to be effective so SRA isn’t a good protocol.
• Other protocols for the Mental Poker problem have been considered with the most successful ones using probabilistic encryption and zero knowledge proof. Crepeau solved the problem in 1987 although his protocol is not computationally feasible. Research is still going on.

Conclusion

Mental Poker is an important problem, both for use in the large internet poker business and as a metaphor for other multi-party computations were secrets need to be kept. It is possible to implement the SRA protocol efficiently and securely, however it has a major flaw in that it leaks one bit of information about the cards. Other protocols have been suggested with Crepeau solving the problem in 1987 although with a computationally infeasible algorithm.

Bibliography

http://www.ics.uci.edu/~goodrich/teach/ics247/W03/notes/poker.pdf

http://www.netip.com/articles/keith/diffie-helman.htm

http://www.ics.uci.edu/~goodrich/teach/ics247/W03/notes/elgamal.pdf

Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996.