Thread: Cryptography problem dealing with information hiding

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.

Hey hwill205.

Any method that allows you to make a comparison either indirectly (or directly) with the boxes will work. Ordering the boxes is the easiest but as long as you can extrapolate the information from any kind of organization of the boxes (if we assume that they don't have labels, have been arranged in random order, and don't have any link between the two sets) will do.

The theoretical way of understanding this is through that of a relation in mathematics.

You just need some way to be able to relate the two boxes with rocks to each other and for your purposes, you need to do it with regard to what the box corresponds to numerically.

Think of it like a chain: you have two ends of the chain but as long as the whole thing is linked so that there is a "path" for a way to relate the two boxes in terms of which is bigger then it doesn't matter how much depth there is in the organization of the boxes and their relationships (i.e. how deep the chain is): the only thing is that a relationship exists to discern the answer.

You could create many many ways of organizing the boxes and force constraints to know how to get particular attributes, and ordering the boxes in consecutive order is definitely one way to do it: but there are many ways.