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 the following 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.

## Alice and Bob Case

28
Nov