Proving an Encrypted Shuffle With ElGamal and ECCIn this case we will encrypt some cards with a public key, and then shuffled and re-created as randomized pairs. We will then prove that the shuffled and re-randomized values are still correct [article]: |
Outline
The following is the code [taken from here]:
package main import ( "go.dedis.ch/kyber/v3" "go.dedis.ch/kyber/v3/group/edwards25519" "go.dedis.ch/kyber/v3/proof" "go.dedis.ch/kyber/v3/xof/blake2xb" "go.dedis.ch/kyber/v3/shuffle" "fmt" "encoding/hex" "strconv" "go.dedis.ch/kyber/v3/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]) } rand := blake2xb.New([]byte("Bob")) suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand) // 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==") fmt.Printf("Decrypted (before shuffle): ") for i := 0; i < k; i++ { M_decrypted, _ := ElDencrypt(suite, h, K[i], C[i]) fmt.Printf(" %s ",string(M_decrypted)) } fmt.Println("\n\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==") fmt.Printf("Decrypted (after shuffle): ") for i := 0; i < k; i++ { M_decrypted, _ := ElDencrypt(suite, h, K2[i], C2[i]) fmt.Printf(" %s ",string(M_decrypted)) } prf, _ := proof.HashProve(suite, "PairShuffle", prover) fmt.Printf("\n\nProof: %s\n",hex.Dump(prf)[:80]) 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:
Private key b0cd72ad18c8afc610b08bd774034230ecc24d35b85e528127893edb19dda705 ==Encrypting cards== [0] K: 7a68a8371d067d514c62c2c7d7189e424911820013bb5e844ab11ab3f1064050, C: 221ee6085bc1404c6610b1af37129a6f995cdc5bcca8db368a93de21eb1788c7 [1] K: 89f0f66cd8057e777c2b1ff2d10041ec511f25b8712fa932f4d9e261cdb6b37d, C: b131f8371346a364aa8ecf627f53d3292d8c16b39d7532e26d0f4ba14a465944 [2] K: f4f1e9abb06bd229825d483967fadfbf18b4c5033c8440a9b96bee7c5609d256, C: 9acac40c05ba0fcc37b9f0794dfb4093b5b520c2896d80d08a69d65d486d033d [3] K: 48d48535bdf1da7340436613c4c77bf001c489ea4084cf7ca9896f42f1bf8ac1, C: 49fd182a306dc5d134ca22acf2d8e5af0ff150db68b1673922ec7a42110ba065 ==Check for decryption== Decrypted (before shuffle): 0 1 2 3 == Shuffling and re-randomising keys== K: 5e39949e8229daf798df83467ed694b5b153d4748d7c763fc803af689776d462, C: 123d0970a6973aa8d6fd2958848c0b4b7b72e00b73ff0033c9e55a442a4b5faa K: e1c7fb5bf653b8e20dac6d8a15351774d1744414c2a8763603365ff135a3c7a1, C: ea093af4160d3202d9c42f3cfb3454774b612170bf0bbfdea1bb493d11613d93 K: 6800abd21071ea6096b190416ae615822989aac3793dc709219359fbefb4d78c, C: 1f232a25914062460f532633cb2a2d924d42a80beaae3de1caa1840cf816bb56 K: 8e29b9914b81d75b8d528ee0b07105cc9ca2673457ec54be1cd8ee8c2c0d0e6a, C: 491fecb4af64e87d1eeb00f8771363f8f07a841b87a6921ee3bcded44a7bcc7a ==Check for decryption== Decrypted (after shuffle): 1 0 3 2 Proof: 00000000 8a 26 0d be c6 08 ec a6 22 ce 37 ed 07 92 d6 af |.&......".7.....| 00000010 b1 d7 86 31 72 a3 8e a1 bb bd 47 8f 4e 9a 2a 8d |...1r.....G.N.*.| !!! Shuffle has been proven !!!
And with 10 cards:
Private key b0cd72ad18c8afc610b08bd774034230ecc24d35b85e528127893edb19dda705 ==Encrypting cards== [0] K: d90b6458287e4865b33a453bf6dfcdd9e453fac6930676661275c966fe491020, C: 969bb9871dcf2388ca8a2e76ae93c569481f29ca549bbeef4f5545de5695518b [1] K: d6f9d30a8dcc5b08180603ee12b8e9c4af439ab39af2816153a7e958bee9441b, C: ba0a696c9948f72aaf8de84bf06b4a0d0ef8ecef09aff2f0635025c585592490 [2] K: c625a26427a869bcf95ad49e3d0faa29095fca1d785f788aa3c78e25d9b87ba4, C: acfcf5f93dc1512b76d4ddfae9d763039c99e0eac0f1fed19a9e8fbebaff625a [3] K: 4bf2b254de59956a079e26e6970e61f2613d2efe0e98f61a4e8fb3099ed83b2c, C: e2e25fa44dd834e8ba8014362787b67f8c5260e9f5d261ef546dd588dcf4962f [4] K: 525d26b1e2c7a19c6c60909be3fb3825aa4fde1b253c9dae6082f571cf7fa9af, C: 2534ca50c13df677d3837c15492533074274c1591e20d23d6c81bfc61372a078 [5] K: 372d44cde77428957708dfdaee2935481f683113a046b2f24c3f8d4fa1fc79a3, C: 7a0e00cde1a8bfac9ef4235a2a781494166b7422edd0076984c3e7b93b488b5c [6] K: 2efdf32a475be94e8f323b505bf0248a75e1ca09415863f95a846d084245c8ca, C: 87ac884fa7af74ba0d8ed156215053dbce054750f2fb59564cac1206c2dbf74e [7] K: bee201c6e677c9cdc78ca4bd4259f5e0987bd21d926f64ca21d0ab06e9e2d6ab, C: e2b54b3e654c85d75750c7347e2d7e296e607f0dab1f85c1cdc570a0bb545be6 [8] K: e070f378bf80e8ab28580970932e3e7673bb0f6e9dedc7f41cc41737b5b06a89, C: 4eeabc68c07c0eb5558b287b58b1bd2c3f8e5434c61b37a57ef2432afb9db974 [9] K: 2253ad5124d44c5b1e844b14935c808394c321a91fffe09fea4b649ed3ab6305, C: e09dd463e601d441642f3096ea66c57d59f7cc570a7727e822bccb77eb8631c7 ==Check for decryption== Decrypted (before shuffle): 0 1 2 3 4 5 6 7 8 9 == Shuffling and re-randomising keys== K: e7b15cb6a9579c340670aae123377732cb533629d7beab420272ce92c99720fa, C: 241ab8e3b87d963aa3bde2902d79a3a73c7fea37e7a2923801fd6ffee55a0afe K: c0f726012673550333cf05fdd8c74662dbe4a8196cfbca65828b781091292222, C: a9bca80da759608e0107a0fc6223d5c55b92a00c831a73ef0267fa65bb63c0a4 K: 951ac9b8ebf13c05e9665c8205b4fb0ff32e79637b34d13f51fb49b1e696c010, C: 350e686e0982ba54d7b7f36c23f13ffeeae683b9355ecf364abfbfe7e91af6f2 K: bf85b458fae1c2fe8c308e94a5ab91293252ec3b699f2d41b3817323fbbb979d, C: da7fcf4e19b21ffc00d2fa00dc837405fdc6ba2ae4607ea134f82ba59ff129fb K: f216f599a207d0bda792f8dc6f7b25ca82e3c0b47f91d7bba229453028c26351, C: 73a93221f95738240d11cc7a6799b33f55eb4d104a5e0710111ac8abfcbb8dce K: 4130079e10a37a33ed8d06ff97748a8765e817e63e2ebe6850e5bc5be1b455dc, C: 46b65f0802c7bc7353eaae59d803b2e8407831087f38247dda2f2287d2252613 K: 8f322af916ba1b6a31ea99c541ca45d76a50d14b9a589ec9e00779c667abbb06, C: b97e72aa42f1be1e97b1fd0843885987095c76c556381012d716c93711acaa7d K: 9de3b11b852e25ed31970b612d05ded1cff94b28a4aa68896b069c1615f47a89, C: 25913ff9c6f3c2ad63e0e7aa83a2a09052667f89e42539992539539ae03fa9c9 K: f328ffb402e63ba31ab9677dcee0a29db272d5c45a0f73840038f34040c05dea, C: 165b988d5d33e0c13f17f9f4ae1da622dc92929f909f46440d402ecb0a087433 K: 3d7781792486d7150041affe7a7b2794b9b17c52fc3c0260b2ad3518d32db2a4, C: 0dc1a84cfafc8029ec5ed0f20fbed458cac75adf7a2ccfb48867062d2acb6eb3 ==Check for decryption== Decrypted (after shuffle): 0 5 3 7 4 1 6 2 9 8 Proof: 00000000 c8 ff de 54 b0 d5 4c c6 f5 ed f9 bf 27 00 dd d3 |...T..L.....'...| 00000010 42 61 9c e8 20 07 2a a7 6e 86 ac 91 62 72 4a 28 |Ba.. .*.n...brJ(| !!! Shuffle has been proven !!!