Oblivious transfer variation question

Question

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:

1. Bob enters a room where alone where 100 boxes are and he inserts a pebble in the n_Bth box.
2. 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.
3. Bob enters the room and he changes the order of the boxes. He cannot shake the boxes for the same reason.
4. Alice enters the room and she changes the order of the boxes. She cannot shake the boxes for the same reason.
5. 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.

Answer 1

Actually, it does not matter if Bobs number is greater or less than Alices number. In either case Bob can compute $n_A$ (here I denote by $n_A$ and $n_B$ the private numbers of Alice and Bob respectively). Bob could simply note the number of boxes with one pebbles in them and the number of boxes with two pebbles in them, lets call these numbers $p_1$ and $p_2$ respectively. Also lets by $N$ denote the total number of boxes. If $p_2 = 0$ then $p_1 = N - (n_A - 1) + 1$, and if $p_2 = 1$ then $p_1 = N - (n_A - 1) - 1$ . In general we can write this as $p_1 = N - (n_A - 1) + (1 -2p_2)$. If we rewrite this we get $n_A = N + 2(1 - p_2) - p_1$. So you see, regardless of the relation between $n_A$ and $n_B$ Bob can compute $n_A$.

You could solve this by simply not letting Bob shake any boxes, so that he never learns $p_1$ or $p_2$. I.e., in the last step instead of Alice and Bob shaking every box, you should just send Alice into the room to shake all the boxes. She will then learn the result, and can tell the result to Bob. In fact, in this case Alice does not have to shuffle the boxes, only Bob needs to do that.

You could argue that in this case Alice may cheat and tell Bob an incorrect result. However, you are already trusting Alice to follow the protocol in the previous steps, so this shouldn't be a problem.

Note, that if a box contains two pebbles it means that $n_A \leq n_B$, not $n_A < n_B$ as you state.