Essays, Posts & Presentations

Alice and Bob Play a Game of Cards

Arnoud Buzing

Author

Arnoud Buzing

Title

Alice and Bob Play a Game of Cards

Description

Determining who has the higher playing card, cryptographically. An example of using the Wolfram Language to model and reason about zero knowledge.

Alice and Bob Play a Game of Cards

August 6, 2020

Arnoud Buzing, Director of Quality and Release Management

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):

In[]:=

[◼]	PlayingCardGraphic

[Range[13],"CardSpreadAngle"0]

Out[]=

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

(*hidethiscellfromtheblog,itisonlyneededtomaketheoutputsnon-random*)(*SeedRandom[2]*)

In[]:=

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

Out[]=

{12,9}

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

In[]:=

alicesCard=

[◼]	PlayingCardGraphic

[alicesChoice]

Out[]=

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

In[]:=

bobsCard=

[◼]	PlayingCardGraphic

[bobsChoice]

Out[]=

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:

In[]:=

allCards=Table

[◼]	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:

In[]:=

allPasswords=Table[GenerateSymmetricKey[Method<|"Cipher""Blowfish"|>],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:

In[]:=

bobsPassword=RandomChoice[allPasswords]

Out[]=

SymmetricKey

cipher: Blowfish

block mode: CBC

key size: 256 bits



This holds all passwords, except Bob’s:

In[]:=

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:

In[]:=

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:

In[]:=

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

Out[]=

{$Failed,12},

,9,1

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:

In[]:=

Off[Decrypt::failed]

In[]:=

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];

In[]:=

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:

In[]:=

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

Out[]=



,9,Higher

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 a “zero-knowledge proof.” These types of proofs can show that one person has access to certain information without revealing what that information actually is. For example, it allows you to prove to someone that you possess a password, without actually telling that person your password. Zero-knowledge proofs are also used in blockchains to prove the validity of a transaction, without revealing the identity of a sender or a recipient.

Using the Wolfram Language, you can easily model and reason about zero-knowledge proofs and even implement them for production-level code.

Cite this as: Arnoud Buzing, "Alice and Bob Play a Game of Cards" from the Notebook Archive (2020), https://notebookarchive.org/2020-08-2t8hajz