Alice, Bob, Carol, Dave and Eve Play Mental Poker in Go

Okay. You have 52 cards, and you have five people in the game (with Alice, Bob, Carol, Dave and Eve), and they are all remote and none of them trusts any dealer. So how can you create a game, where we shuffle the cards, and where each player will get the same card dealt as each other? One method is defined within the following paper [here]:

What we want to do, is to generate 52 encrypted cards (E(ci)), and send them to each of the players. They will then shuffle them with a randomization factor for each encrypted card, and we should still be able to prove that the shuffle is still correct.

In this case, we will create a public key and a private key for the encryption, which we will share with all of the players. We will then use this to encrypt a number of cards (“1”, “2”,…). In ElGamal we create two values for each card: K and C. Once generated for each card, we can then distribute these to each of the players, and where they will shuffle the encrypted cards, and end up with the same shuffled sequence. We then need to prove that the shuffle and the re-randomization process has worked correctly. The ElGamal method has the advantage of implementing additive homomorphic encryption, and also in creating a shared public and private key.

The following is the code [uses this library here] [Sample run]:

package mainimport (
"go.dedis.ch/kyber"
"go.dedis.ch/kyber/group/edwards25519"
"go.dedis.ch/kyber/proof"
"go.dedis.ch/kyber/xof/blake2xb"
"go.dedis.ch/kyber/shuffle"
"fmt"
"encoding/hex"
"strconv"
"go.dedis.ch/kyber/util/random"
"os"
)
func ElEncrypt(group kyber.Group, pubkey kyber.Point, message []byte) (
K, C kyber.Point, remainder []byte) {
// Embed the message (or as much of it as will fit) into a curve point.
M := group.Point().Embed(message, random.New())
max := group.Point().EmbedLen() if max > len(message) {
max = len(message)
}
remainder = message[max:]
// ElGamal-encrypt the point to produce ciphertext (K,C). k := group.Scalar().Pick(random.New()) // ephemeral private key
K = group.Point().Mul(k, nil) // ephemeral DH public key
S := group.Point().Mul(k, pubkey) // ephemeral DH shared secret
C = S.Add(S, M) // message blinded with secret
return
}
func ElDencrypt(group kyber.Group, prikey kyber.Scalar, K, C kyber.Point) (
message []byte, err error) {
// ElGamal-decrypt the ciphertext (K,C) to reproduce the message.
S := group.Point().Mul(prikey, K) // regenerate shared secret
M := group.Point().Sub(C, S) // use to un-blind the message
message, err = M.Data() // extract the embedded data
return
}
func main() { var k = 4 argCount := len(os.Args[1:]) if (argCount>0) {k,_= strconv.Atoi(os.Args[1])} suite := edwards25519.NewBlakeSHA256Ed25519WithRand(blake2xb.New(nil))
rand := suite.RandomStream()
h := suite.Scalar().Pick(rand)
H := suite.Point().Mul(h, nil)
fmt.Printf("Private key %s\n",h) K := make([]kyber.Point, k)
C := make([]kyber.Point, k)

fmt.Println("\n==Encrypting cards==")
for i := 0; i < k; i++ {
m := []byte(strconv.Itoa(i))

K[i], C[i], _ = ElEncrypt(suite, H, m)
fmt.Printf("[%d] K: %s, C: %s\n",i,K[i],C[i])
}
fmt.Println("\n==Check for decryption==") for i := 0; i < k; i++ {
M_decrypted, _ := ElDencrypt(suite, h, K[i], C[i])
fmt.Printf("Decrypted %s\n",string(M_decrypted))
} fmt.Println("\n== Shuffling and re-randomising keys==") K2,C2, prover := shuffle.Shuffle(suite, nil, H, K, C, rand) for i := 0; i < k; i++ {
fmt.Printf("K: %s, C: %s\n",K2[i],C2[i])
}
fmt.Println("\n\n==Check for decryption==") for i := 0; i < k; i++ { M_decrypted, _ := ElDencrypt(suite, h, K2[i], C2[i])
fmt.Printf("Decrypted (after shuffle): %s\n",string(M_decrypted))
}
prf, _ := proof.HashProve(suite, "PairShuffle", prover) fmt.Printf("\n\nProof: %s\n",hex.Dump(prf)[:50])
verifier := shuffle.Verifier(suite, nil, H, K, C,K2, C2)
err := proof.HashVerify(suite, "PairShuffle", verifier, prf) if err == nil {
fmt.Printf("!!! Shuffle has been proven !!!")
}

}

A sample run is [Sample run]:

Private key 97bb9cebdd5e07e94d2980bb920b83e16cf4f6ed078f50cca8ba19cdd887ea0c==Encrypting cards==
[0] K: 80a2e471253f3b433b479df07af50bc68d1834982d495df8259a75644cf99ec7, C: 2e62d7debb40ffcbeeac7157114410f03cc968f18b1292f8c97bd896cda0e48a
[1] K: d0667997122e21c0431e24f9cb9faed10a0d5cce1491b40c7a13a93225e28311, C: c875538c70a3c46915e0407e6fb59477ede62782221cf97e3644a23f3c1e70ec
[2] K: da852b93029435e057c2242f13482193bfabf3ea51b05ae8f27b4094807370b9, C: c38826c5b9bd66b62113525f8f7d0b1974f7901b3d8f30ec38095ae346ada850
[3] K: 2e1040a2da7b39fc55665233410b15080d660e68ecd388d06b917cb8b0fb9992, C: e19ee90a74d3b7b310ec205507e8a641308611c2888153b9574e1bead7936429
==Check for decryption==
Decrypted 0
Decrypted 1
Decrypted 2
Decrypted 3
== Shuffling and re-randomising keys==
K: 2083c58a4e034cf8a028e7ae79fce104c4a548a67e71c9f9d1e3efe6ee5fcdb9, C: 3088aa97a6534ab4acc1a47cf978b7517c37235fdb9d6c1cf96626d05e8fca2f
K: 4c2fe6a7394aad1283ec1331e136d9b302c64768b68d5e999aab388ba3c1e9fe, C: 0e8e0ab480c0fe723ca0a2f192146da0c942628b5769df26fc5625e6e2a5d2a4
K: 6c765e342087be1371dfcdf36292e5d3869026df646a028b28da91bac789ce56, C: 4c5f050afef043f5fb6f88648d63e01aed096afac70d15faeb0aa044363692b9
K: 6d786036b091c83339ae7a34b446fa8dc307ef791482056f5af178ccae5092e3, C: f4fe8cf20d37c15a4179b8661a0764f7786ff9956abf66d88a72e67e9d55bc75
==Check for decryption==
Decrypted (after shuffle): 0
Decrypted (after shuffle): 2
Decrypted (after shuffle): 1
Decrypted (after shuffle): 3
Proof: 00000000 b2 f7 6c ce 78 57 fa 0d 0b d3 f6 0e b7
Proven

ASecuritySite: When Bob Met Alice

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade