Now I am doing a variation of the oblivious transfer, I have to use 2 people, pebbles, and boxes. I need to find out if who has a larger number between Alice and Bob (variation of Yao's Millionaires' Problem). This is what I have come up with:
- Bob enters a room where alone where 100 boxes are and he inserts a pebble in the n_Bth box.
- Alice enters the room alone where the boxes are and she inserts a pebble in the n_Ath box and a pebble into each $(n_A+1)$th box till she reaches the last box ($100$th box). She cannot shake any of the boxes because the noise will be heard by Bob who is waiting outside.
- Bob enters the room and he changes the order of the boxes. He cannot shake the boxes for the same reason.
- Alice enters the room and she changes the order of the boxes. She cannot shake the boxes for the same reason.
- Now Alice and Bob both enter the room and they shake each box. If they hear $2$ pebbles in one box, it means that $n_A < n_B$. Alice now only knows that $n_B$ has to be larger than her number. If a box does not contain two pebbles then $n_A > n_B$. Alice now only knows that $n_B$ is less than her number.
Now the only problem is, that it only works if Bob has a larger number than Alice. If Alice has a larger number than Bob, then none of the boxes will have $2$ pebbles and they will both know that Bob's number is larger than Alice. However, Bob has an advantage as to figuring out what number Alice has, because Alice put pebbles in her box and all boxes greater.
Example using 10 boxes:
Alice's number = 7, Bob's number = 3 x x x x x 10 9 8 7 6 5 4 3 2 1 After the randomization process, Alice and Bob both know that Alice's number is larger than Bob's. But the Prob(of b = 4 or 5 or 6) = 0% because all Bob has to do is subtract the number of boxes with a pebble in it from the number of boxes (10 - 4 (it's because he put a pebble in his box)) and he knows that Alice's number has to be 10, 9, 8, or 7.
If you don't follow, I can try to make it more clear.