Roll a dice via e-mail

Question

I have been asked this question, but failed to find an article that describe a good method. Instead I came out with my own method (see my answer below). However it is also possible that I merely came up with a method I am not smart enough to break. So I pass this question on to you:

Alice and Bob wish to play a board game over e-mail. They need to find a way to roll the dice in a way that will not let them cheat.

What is a good algorithm to do so.

Helpless

@Justin Morgan: He just asked the question 2 minutes ago, give him a moment... – Fatherhood

Just looked like he forgot to paste it in, that's all :) – Conjunctive

I guess including a video of the roll with the TV setup on a common channel in the background doesn't count ? – Robichaud

@matthiew How that prevents rolling multiple times until the best result is achieved? – Posey

Answer 1

This is a classic problem in cryptography.

One such paper: Coin Flipping by Telephone.

There are apparent some impossibility results too.

For instance reference [C86] in this paper here: http://www.cs.columbia.edu/~dglasner/MyPapers/coin-cut.pdf

Hope that helps.

Medford

Answer 2

Alice and Bob need to be able to send each other a proof that they picked a number, before they reveal what number they picked. Then the number they chose need to be verified against the proof. Finally both the numbers need to be joined in some way that will not give each of them a total control over the outcome.

In the following crypto_function can be something like sha1sum or md5sum:

Step 1:

needed to make the range of possible values for the crypto_function below sufficiently large

• Alice picks random numbers Ra1 and Ra2 and send Ra1 to Bob.
• Bob picks random numbers Rb1 and Rb2 and send Rb1 to Alice.

Step 2:

creates the proof Hx that the value Vx is now fixed, but prevent deducing this value from that proof

• Alice picks a value Va (0<=Va<=5), compose a string Sa="Va Ra2 Rb1" , and send a Ha=crypto_hash(Sa) to Bob.
• Bob picks a value Vb (0<=Vb<=5), compose a string Sb="Vb Rb2 Ra1" , and send a Hb=crypto_hash(Sb) to Alice.

Step 3:

generates the desired outcome V

• Alice sends Sa to Bob. Bob Calculate Ha out of Sa and compare it to Ha from step 2. Then takes Va out of Sa, and calculate the value V=(Va+Vb)%6+1.
• Bob sends Sb to Alice. Alice Calculate Hb out of Sb and compare it to Hb from step 2. Then takes Vb out of Sb, and calculate the value V=(Vb+Va)%6+1.

---

Update:

Based on Coin Flipping by Telephone suggested by @Moron the algorithm can become:

1. Bob picks a random number R and the value 0 <= Vb <= 5, Calculates a hash H=crypto_hash("Vb R"), and sends it to Alice.

2. Alice picks the value 0 <= Va <= 5, and sends it to Bob.

3. Bob sends Vb and R to Alice; Bob calculates V=(Va+Vb)%6+1

4. Alice verifies H=crypto_hash("Vb R"); Alice calculates V=(Va+Vb)%6+1

... Although I would feel better about it if:

0. Alice picks a random number Q and sends it to Bob.

And the string to be hashed becomes then "Vb Q R".

Helpless

Sounds like what I'd have done. though I don't think you need the -2 in the final calculation. The modulus operation sorts that out. I assume your random numbers are not meant to be similar to dice rolls but that's what I thought on first reading so you might like to clarify that. – Leu

In the calculation of V, it looks like you’re using assumptions about the ranges of Va and Vb. Can you make those explicit? – Hawkshaw

@Chriss, @jieedev, Thank you. I integrated your comments in. – Helpless

Answer 3

Games played by mail - whether email or not - used to use a publicly available (pseudo) random number - typically the least significant digit on a stock price listing at a specific position on a stock listing (not a particular stock). This could not be predicted, and was verifiable after the event. Players would exchange details - before the dice roll - of which position of the stock listing (typically at close of business) should be used for the next dice roll(s).

Belton

The modern version is something like rpglibrary.org/software/securedice which can email dice rolls with serial numbers and a hash that is verifiable online. – Conjunctive

@justin Post that as an answer! - The serial numbers are the key issue here – Posey

You need also to solve the problem that a player by choosing when to throw the dice, can choose its' value. – Helpless

@Chen - yes you do, though this was partially solved by the player not making the roll selecting the position and future date and time of the listing, for use by the dice roller. It still does not solve the problem where multiple dice rolls are used for different purposes, and the dice roller can choose the ordering of the dice rolls. So not completely cheat proof, but it proved to be adequate for board games where the ultimate remedy was not to play with someone you suspected was cheating. – Belton

Answer 4

Use a trusted third party like http://rpglibrary.org/software/securedice which can email dice rolls with serial numbers and a hash that is verifiable online.

Conjunctive

Answer 5

Alice and Bob agree on a two session keys using something like Diffie-Hellman, Sa and Sb. Each session key is the seed of a random number generator, Ra and Rb.

The RNGs are used as one-time pads for each die roll. If Alice wants to roll, takes Ra[i] where i is the ith random number in the sequence. Alice sends both i and Ra[i] to Bob. Bob can verify i using his own copy of Ra.

This keeps Alice honest by requiring her to use sequential values of i that are verifiable by Bob.

Conjunctive

If Bob also has Ra and knows what i is next, then can't he predict the dice roll in advance of Alice sending it? Makes the game of 'who rolls a six first' a bit dull... – Cibis

Isn't that game already boring? ;) Yes, if uncertainty of the next die roll is important, then this is not the right solution. But it's probably the simplest solution in cases where that doesn't matter. – Conjunctive

Answer 6

I received a response to a similar question I asked which was How can I make dice for R? The response was a program for R in addition to a program for "intimate dice". I'm not sure which die Alice and Bob are interested in but I suggest using R in addition to a remote desktop so each player can see that the other is not cheating.

I don't know how to write the codes so I've copy/pasted the response I received:

If you want to make dice in the statistical program R. Start by downloading it here: http://cran.r-project.org/.

To make a normal dice use the following script: #Dice roll function RollDie = function(n) sample(1:6,n,replace=T) #use Die RollDie(n)

#If you'd like to spice things up a bit and make a dice for safe and consensual adult
#activities then use the following series of scripts:

#Creating the function, use this script:
#Intimate dice function

Actions= c("kiss","lick","suck","bite",
"spank","blow", "stroke",
"tickle","pinch",
"torment")

Body= c("lips","arms","chest","thighs",
"neck","ear", "wrist",
"navel","nipples",
"the good stuff")

Action= function(n) sample(Actions[1:10],n,replace=T)

Area= function(n) sample(Body[1:10],n,replace=T)

Action(1)

Area(1)

#If you'd like the dice saved to the R global environment so you can be ready for when
the mood is right use the following script:

#Save the following script as yourfile.R in something like this location "C:\\Documents           
and Settings\\yourfile.R"

#Intimate dice
Action(1)
Area(1)
#yes

#Now create the following function to save to R's global environment with the following:    

#Run all
source("C:\\Documents and Settings\\yourfile.R",echo=T)

hi<-function(){source("C:\\Documents and Settings\\yourfile.R",echo=T)}

#ok

#close and save your R workspace 
#upon opening run the following function:
hi()
#If this has been done properly then you should see something along the lines of this:
#Intimate dice
Action(1)
[1] "bite"

Area(1)
[1] "ear"

#yes

#Here's to one more reason for celebrating math & science

Systaltic

Answer 7

Setup an automated third party server where each sends there emails for dice rolling and forwarding to the other player?

Otherwise it's just plain way too damn much work to play this game and I quit!

Photoflood