I wasn't sure of where to put this problem, but since the class is dealing with RSA encryption and number theory, I decided to place it here.
Basically I just want to know if I am on the right track with this problem.
Here is the problem:
Jill and Jack each have two numbers between 1 and 100 and want to see if their numbers are the same without revealing the actual numbers. They have a room with 100 boxes lined in order. The boxes each have holes that are big enough for a small rock to fit in. In order to solve their problem, Jill, who has number x, puts her rock in the xth box. Jack, who has number p, puts his rock in the pth box. He cannot shake any of the boxes, because Jill will hear.
Jill then enters the room and rearranges the boxes in random order. Bob then comes in and does the same. They then shake each box. If they eventually hear two rocks in one box, then they know that their numbers are the same.
Now Jill and Jack wants to know who has the bigger number without revealing any other information. They have the same scenario (two numbers between 1 and 100, rocks and a room with 100 boxes lined in order). Come up with a protocol to solve the problem.
My attempt at a solution:
My general solution to the problem was to simply have Jill put her rock in the xth box. Jack then puts his rock in the pth box. Jill then rearranges all of the boxes between x+1 and 100 so that none of them are in their original position. She tells Jack to go in and shake the box in the pth box (she doesn't know what p is, of course) and that if he hears his rock, then he has the bigger number. If he does not hear his rock moving when he shakes the box, then Jill has the bigger number.
I created a separate similar protocol for what they will do if one gets a 1 or 100 for a number, but its not worth elaborating on.
Two notes: Moving the box does not cause the rocks to move or make any noise. They can only be heard by shaking the box. Secondly, we assume that Jill and Jack are honest.
Thanks for any and all help offered.