BiBa — One Time Signature

BiBa — One Time Signature

You are at a fairground, and there’s a fun challenge. In front of you are five bins, and the challenge is for you to fire a ball at the bins, and where they will fall randomly into one of the bins. If you get two balls in the bin, you will win, but every attempt will cost you $1. The prize money is $4. Is it a good bet?

Okay. You have five bins, and you want to get to the point where one bin has two balls. For this you will have a 1-in-5 probability that any throw of the ball will go into a specific bin. What is the likely number of throws that it will take to win? Well, as a maximum will be six throws (you will lose $6, but gain $4, and will be thus $2 down). As a minimum it will take you two throws (for a $2 stake you will win $4). Will you win or will the fairground win, overall?

Of course, the probability on the first throw will be:

P_0 = 0

on the second we now have a one-in-5 chance of getting in the bin we hit the first time, so the chances of us not winning will be:

P_1 (Not win on second throw) = 4/5

Now, on the third throw, if we have not won, we will have two bins with balls out of 5 bins. So the bins could be:

1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 1 0 0
0 1 0 1 0
0 1 0 0 1
0 1 0 1 0
0 1 0 0 1
You have three spaces that we could hit in each of the bins. You thus have two chances to hit a bin with a ball, and three chances to miss. The chance of you not winning is 3/5. The probability you will not win at this point is thus:

P(Not win on third throw) = 4/5 x 3/5 = 12/25 = 0.48

The probably of you winning is 0.52, but it has cost you $3 to get to this point. A win is $4, so your returns — on average — will be $2.08 (you are likely to lose around half of your money at this stage, if you keep playing the game continually). If you are still in the game, you now have a 2-in-5 chance of losing. For example the losing bins will include:

1 1 1 0 0
1 1 0 1 0
1 0 1 1 0
0 1 1 1 0
1 1 0 1 0

Thus:

P(No win on forth throw) = 4/5 x 3/5 x 2/5 = 12/25 = 0.192

You now have a 80.8% chance to have won at this point. So for a $4 stake, your returns are still only likely to be $3.20 (on average you will be down by $0.8). Finally you throw again, and now only have a 1 in 5 chance of not hitting on a bin with a ball:

P(No win in five throws) = 4/5 x 3/5 x 2/5 x 1/5 = 12/25 = 0.0384

You now have a 96.1% chance to have won at this point. So for a $5 stake, your returns — on average — are still only likely to be $3.84 (you will be over $1 down for each attempt). And finally you throw the last one, and you are guaranteed to win — so you might as well pay your money — as you have been unlucky enough to throw the balls in all the bins:

P(No in five throws) = 4/5 x 3/5 x 2/5 x 1/5 x 0/5=0

You will then win, but it has cost you $6 and the return is $4. So it is a bad bet!

The coding to determine the average number of throws to get two balls in at least one bin, and with n bins is [here]:

n = 5.0
val=(n-1)/(n)
for i in range(2,int(n+2)):
    print i,1-val
    val = val* (n-i)/n

print

E=0
p_prev=1.0/n

E=p_prev*2

for i in range(2,int(n)):
    pnew = p_prev*(n+1-i)*i/(n*(i-1))
    E = E+pnew*(i+1)    
    p_prev=pnew

print "Average number of throws",E

A sample run for five bins is [here]:

Number of bins: 5

Throw   Prob of winning
2       0.20
3       0.52
4       0.81
5       0.96
6       1.00

Average number of throws 3.28

This type of problem can be used to analyse hashing algorithms, and is the basis of the birthday paradox. With this, we determine the probability of two people having the same birthday. We then have 365 days, and so will have 365 bins:

Throw Prob of winning
2 0.003
3 0.008
4 0.016
5 0.027
6 0.040
7 0.056
8 0.074
9 0.095
10 0.117
11 0.141
12 0.167
13 0.194
14 0.223
15 0.253
16 0.284
17 0.315
18 0.347
19 0.379
20 0.411
21 0.444
22 0.476
23 0.507
24 0.538
25 0.569

We see that for 365 days, then for 23 people in a room, we have a 50.7% chance of a ‘collision’. Thus, if we have hashing, and take a message, and then take two random nonces, within a reasonable amount of guesses we can come up with a collision. We can now use this for our One Time Signature (OTS).

BiBa — One Time Signature

One area where we can use this collision is within a one-time signature (OTS) and with the method defined as “BiBa” (“Bins and Balls”). Basically with BiBa, Bob creates a number of random values for his private key:

Priv = x_1, x_2, … x_n

Next he creates his public key from the hashed versions of his private key:

Pub = SHA1(x_1), SHA1(x_2) … SHA1(x_n)

To create the signature for a message (M), he finds two values which will create a collision (as we have seen it should be fairly easy to find a collision within a reasonable amount of guesses):

H(M || x_i) == H(M || x_j)

He then publish (x_i, x_j) as the signature of the message.

It would then be too difficult for Eve to find the values of x_i and x_j to create a collision, as Bob does not reveal them (they are only defined with their hash signature).

The coding to determine a collision and generate the signature is [here]:

A sample run for a message of “abcde” is [here]:

Message is abcde. Private key is 3227. Finding for [abcde3227] 
Looking for a collision for abcde3227. Hash: 35690

Searching ....

Found it at 44304. String is abcde44304. Hash: 35690
BiBa Signature [3227, 44304]

Conclusion

In a time of quantum computers, our existing public key methods are crackable, so we need to find new ways of creating a signature. BiBa is one such method.