Assignment

Let's suppose that Alice and Bob have each a number n_A and respectively n_B between 1 and 10 and they want to know if they have the same number or not. The problem is that in case they don't have the same number, they don't want to reveal to the other party any other information. They can solve this problem with thefollowing protocol that uses 10 boxes that have a small opening and two pebbles. Each box also can be locked and opened with a key. We assume that Alice has the keys of all boxes.

1. Alice enters alone in the room where the boxes are and she inserts a pebble in the n_A-th box.

2. Bob enters alone in the room where the boxes are and he inserts a pebble in the n_B-th box. He cannot open any of the boxes because the keys are in the other room.

3. Alice enters and opens the n_A-th box. If it has two pebbles, it means that n_A = n_B, and if it has a single pebble, then n_A is not equal to n_B. Alice tells Bob whether n_A and n_B are equal or not.

Note that we assume that Alice is honest and she follows the protocol's rules (otherwise she could open all boxes and see what n_B is).

(A) Your first task is to design a protocol (name it Protocol A) that has the same functionality as the one above, but instead of locked boxes, uses some encryption scheme, and email for communication.

(B) Your second task is to design protocol B using encryption schemes and email communication, in which Alice and Bob need to determine whether n_A + n_B>= t, where t is some threshold number. As before, Alice and Bob will not learn anything else besides that the sum of their numbers is at least T, or not.

In both protocols, you can assume that Alice and Bob are honest, and follow the rules of the protocols designed by you.

Describe concisely and clearly your protocol A and B. Make the protocolsrealistic (think that you play it with your friends). Present small concrete examples for both protocol A and protocol B, and show how your protocols run in these cases.