Dreaming BiBa

I am a great believer in the power of sleep, and how we can use it to solve technical problems. So, I had a dream a while ago, and I was at a fairground. As you may remember from our youth, a popular amusement is throwing balls into cans. In my dream,you win a prize if you could get two balls in the same can. My dream came from me thinking about BiBa — Bins and Balls — and which is a post-quantum crypto method for signing messages. When I woke up, and I had the answer on how BiBa relates to signing messages.

At the fairground

Let’s say you are at the fairground, and where there are five bins, and you randomly throw balls into the bins and win get two balls in the bin after three throws. Of course, the probability of the first throw will be:

P_0 = 0

on the second we now have a one-in-5 chance of getting it 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…