Wolfram Blog
Arnoud Buzing

Playing Cards with Alice and Bob: Using Secure Multi‑Party Computation and the Wolfram Language to Determine a Winner

August 6, 2020 — Arnoud Buzing, Director of Quality and Release Management

Alice and Bob Play a Game of Cards

While catching up with my old friends Alice and Bob on Zoom a few days ago, I became intrigued by their recent card game hobby—and how they used the Wolfram Language to settle an argument. To figure out who gets to go first at the start of the game, they take one suit (spades) from a full deck, and each draws a card. Then, the person with the highest card value wins. Because they are using only one suit, there can be no ties. Simple, right?

Now, there is one thing you need to know about Alice and Bob. They are both super-secretive people. They share very few private details about their lives. One reason for this is that they both have jobs in cryptography. Bob works as a security specialist for a major bank, and Alice is a programmer who develops cryptographic libraries.

With that in mind, it came as no surprise that after they each pulled a card from the deck, they did not want to divulge to each other what card they were holding. Alice was quite certain she had the highest card, but Bob was equally certain he did. They argued back and forth about this, but quickly realized neither one wanted to show the other their card, and as a result, they could not start their card game.

They began to wonder if perhaps there was a way for one of them to prove to the other that they indeed were holding the higher card. It was not immediately clear how to do this, or if this was even possible, but they both began to discuss this problem and put the actual card game aside for a moment.

Card Selection

They started out by examining their deck of cards and decided that they might as well use a virtual deck of cards, for example this deck from the Wolfram Function Repository. Because a full deck of cards has four copies of each face value, they limited themselves to drawing from a single suit (spades):

ResourceFunction
&#10005

ResourceFunction["PlayingCardGraphic"][Range[13],
 "CardSpreadAngle" -> 0]

Alice and Bob proceeded to both virtually draw one card from this set:

{alicesChoice, bobsChoice} = RandomSample
&#10005

{alicesChoice, bobsChoice} = RandomSample[Range[13], 2]

This was Alice’s card, which Bob did not see:

alicesCard = ResourceFunction
&#10005

alicesCard = ResourceFunction["PlayingCardGraphic"][alicesChoice]

And this was Bob’s card, which Alice did not see:

bobsCard = ResourceFunction
&#10005

bobsCard = ResourceFunction["PlayingCardGraphic"][bobsChoice]

Because they used the RandomSample function, they each got a unique random card. Alice and Bob did not know each other’s card.

Decrypting a Winner

Next they implemented a way to figure out who had the higher card. We, as the observers, know the answer, but at this point Alice and Bob only knew their own cards. For the first step they needed a list of all 13 individual cards with the value of each card attached to it:

allCards = Table
&#10005

allCards = Table[{ResourceFunction["PlayingCardGraphic"][i], i}, {i,
    13}];

Next they generated 13 passwords, one to encrypt each card with. Bob was given only one of these 13 passwords. Alice had all the passwords, but she did not know the password that belonged to Bob. They needed 13 passwords to make sure one password could encrypt and decrypt one card. If they had only two passwords, then either Bob would be able to decrypt more than one card or Alice would be able to figure out which card had a unique password to decrypt with:

allPasswords = Table
&#10005

allPasswords = Table[GenerateSymmetricKey[], 13];

From the generated passwords, Bob picked one that he could use to encrypt and decrypt his own card. He did not know the other passwords, and Alice did not know which password Bob picked. Bob’s choice is shown here, but the actual password is not too relevant. Even Bob did not need to see the actual password—he just needed to have it to decrypt his card:

bobsPassword = RandomChoice
&#10005

bobsPassword = RandomChoice[allPasswords]

This holds all passwords, except Bob’s:

otherPasswords = DeleteCases
&#10005

otherPasswords = DeleteCases[allPasswords, bobsPassword];

Then Bob and Alice agreed to run the following code, which encrypted each card in turn. Bob’s card was encrypted with Bob’s password, but all the other cards were encrypted with the passwords that Bob did not know in random order:

encryptedObjects = Module
&#10005

encryptedObjects = Module[
   {mixedPasswords, i = 0},
   mixedPasswords = RandomSample[otherPasswords];
   Map[
    If[
      First[#] === bobsCard,
      Encrypt[bobsPassword, {bobsCard, bobsChoice}],
      i++; Encrypt[mixedPasswords[[i]], #]
      ] &,
    allCards
    ]];

There were now 13 encrypted objects, one of which could be decrypted by Bob. In other words, Bob could use his key to decrypt the encrypted object that held his own card, but he could not decrypt any of the other encrypted objects. A way to check this is to attempt to decrypt all objects with Bob’s password, as 12 will fail and one will succeed:

Quiet@Tally
&#10005

Quiet@Tally[
  Map[
   Decrypt[bobsPassword, #] &,
   encryptedObjects
   ]]

Then Alice added information to each encrypted object. She unlocked each encrypted object by trying each password until she had a successful decryption. Next, she added "Higher", "Lower" or "Equal" before encrypting every object again:

Off
&#10005

Off[Decrypt::failed]

newObjects = Map
&#10005

newObjects = Map[
   Function[{object},
    Module[{card, value, password},
     {{card, value}, password} =
      First[Select[Map[{Decrypt[#, object], #} &, allPasswords],
        First[#] =!= $Failed &]];
     Which[
      alicesChoice > value, Encrypt[password, {card, value, "Higher"}],
      alicesChoice === value,
      Encrypt[password, {card, value, "Equal"}],
      alicesChoice < value, Encrypt[password, {card, value, "Lower"}]
      ]]],
   encryptedObjects
   ];

On
&#10005

On[Decrypt::failed]

Bob could still only decrypt his own object, but he was able to observe what Alice added. After Bob decrypted his object, he noticed that Alice indicated that her card was higher:

Clear
&#10005

Clear[result];
Quiet@Map[
   Function[
    decrypt = Decrypt[bobsPassword, #];
    If[decrypt =!= $Failed, result = decrypt]],
   newObjects];
result

So finally Bob knew that Alice’s card was higher, even though he was never told what Alice’s card was. They ran the entire scenario with reversed roles, at which point Alice knew that Bob’s card was lower. In this case, Alice and Bob were looking at the same notebook and code, which made cheating by either one very difficult. If they had each executed their code on their own machines, it would be possible to cheat. For example, Alice could have modified the code and pretended to have a higher card than Bob. But this works only up to a point. If Bob had the king of spades (the highest card), and Alice pretended to have that card too, then Bob would know that Alice had cheated. But the chance of detecting that would be low. One way they could have addressed that is by automating the procedure and running it many times. If Alice had cheated, this would have eventually come out. Another way to address this is to use a shared, trusted computation source. For example, API functions in the Wolfram Cloud could be used as a shared mechanism to run the individual computation steps.

The concept behind all this somewhat mysterious trickery is called “secure multi-party computation.” These types of computations let people compute a function over their data, without revealing the data itself to each other. Another related type of computation is a “zero-knowledge proof,” where one party proves to another party that they know a certain value without revealing it.

Using the Wolfram Language, you can easily model and reason about these types of protocols and computations and even implement them for production-level code.

Get full access to the latest Wolfram Language functionality with a Mathematica 12.1 or Wolfram|One trial.

Leave a Comment

7 Comments


Aaron Toponce

Why Blowfish, when AES has been around since 2001?

Posted by Aaron Toponce    August 6, 2020 at 3:03 pm
    Arnoud Buzing

    There was no specific reason for using “Blowfish”. While writing this blog I used different ciphers while experimenting and this one ended up in the blog. The default cipher used by GenerateSymmetricKey (when you don’t specify anything else) is “AES256″. I could get this changed, if you think it is wrong or distracting? Documentation for GenerateSymmetricKey can be found here: https://reference.wolfram.com/language/ref/GenerateSymmetricKey.html

    Posted by Arnoud Buzing    August 7, 2020 at 9:57 am
    Arnoud Buzing

    Aaron, I updated the code to use the default (“AES256″)

    Posted by Arnoud Buzing    August 7, 2020 at 10:40 am
      Aaron Toponce

      Thanks. Blowfish is a 64-bit block cipher, which suffers from the Sweet32 attack [1]. Even though this post is for informational purposes illuminating multi-party computation, and is not necessarily vulnerable to Sweet32 unless an oracle is involved, guides using Blowfish on the Internet imply that it’s still a secure block cipher for today’s problem solving, when in reality, it should not be used. That was my only concern.

      Thanks for updating the post.

      [1]: https://sweet32.info/

      Posted by Aaron Toponce    August 7, 2020 at 12:11 pm
Jay

I understand it is a showcase, so, kudos to Wolfram – however, would this have worked for A & B as well (from their point of secrecy): they each pick a card (as per above) and those two cards are compared by W, simply returning the ‘winner’ (without disclosing any actual values): so, A = 12, B = 9 – W returns: ‘A’ (wins).
The point being, W being capable of processing those 2 values in a second step, without actually showing them (meaning, they are allocated to variables).

Posted by Jay    August 18, 2020 at 7:35 am
    Arnoud Buzing

    If I understand you correctly, you are suggesting adding a third person to the equation? This would also work but then this is no longer the same algorithm. It introduces the problem of who “W” is. Can “W” be trusted? Is “W” a spy for either Alice or Bob? Does “W” always tell the truth? And so on. This would be interesting to explore in another blog post perhaps!

    Posted by Arnoud Buzing    August 18, 2020 at 10:09 am
      Jay

      W = Wolfram
      (it better being trusted and trustworthy, otherwise A & B would make a grave mistake using it in the first place)

      Posted by Jay    August 18, 2020 at 11:22 am


Leave a comment in reply to Jay