How?

Got a sheet of paper? Perfect, let’s go.

The protocol needs room numbers. Let’s use our Faculty’s:

$$R = \{ I01, I02, I03, I21, I22, I23, I30, I31, I32, I33, I34, I35 \}$$

In practice, we’ll represent each room as 128-bits integers to be able to modulo-add, modulo-subtract, and modulo-multiply them:

const ROOMS: [u128; 12] = [1, 2, 3, 21, 22, 23, 30, 31, 32, 33, 34, 35];

Diagrams

The first question is:

How does the protocol work?

If it’s already crystal-clear, don’t hesitate to skip to the next section.

To grasp it, I encourage you to redraw the protocol’s diagram we saw in class. In particular, expand the equations. Next to each actor, note the variables they know. Observe what they can compute and what they cannot.

Tip

Click here to see my version.

Only click if you're done.

Promise?

Additions and subtractions cancelling out are the secret to make it work.

Maybe you’ve got a different way of representing this. No worries, the whole goal of the exercise is to make it yours.

Okay, good. This is the one-shot version, though. In our scenario, Alice and Bob would have multiple room numbers to compare. So, as the course suggests, we’ll have to repeat the protocol several times. How do you do that? Draw another diagram with:

$$a_0 = I21 \quad b_0 = I02 \quad b_1 = I21$$

Or, if you prefer, write pseudo-code to show how the loop works:

let alice_rooms: &[u128] = &[21];
let bob_rooms: &[u128] = &[2, 21];

Tip

Again, click here to see my version.

Or, if you prefer (not-so-)pseudo-code:

let secret = "YELLOW SUBMARINE"; // Use better passwords, please.
let counter = 0;
let alice_rooms = [21];
let bob_rooms = [2, 21];
for alice_room in alice_rooms {
    for bob_room in bob_rooms {
        let hash = sha256(counter || secret);
        let k1 = hash[0..16];
        let k2 = hash[16..32];
        protocol(k1, k2, alice_room, bob_room);
        counter += 1;
        let hash = sha256(counter || secret);
        let k1 = hash[0..16];
        let k2 = hash[16..32];
        protocol(k1, k2, bob_room, alice_room);
        counter += 1;
    }
}

Security

The definition of security always depends on a context and a threat model. So, the second question is:

What is the security of this protocol?

What are we trying to achieve? Cryptography is about information. Alice and Bob want to share information, but with special constraints and certain assurances. What are those? Try to enumerate them.

Tip

Don't know where to start?

Your first diagram should help. Look at the information Alice, Bob, and the Server can and cannot compute.

Tip

Click to see the solution.

At each “round”:

• Alice must know if \(a_x = b_x\).
• Alice must not know the exact value of \(b_x\) (when \(a_x \neq b_x\)).
• Bob must not deduce any information whatsoever.
• The Server must not deduce any information neither.

Then, at the next round, exchange Alice and Bob’s roles.

A threat model is what the adversary is capable of. An adversary is someone trying to break security. What is the threat model here?

Tip

Click to see the solution.

• The Server is honest, meaning it executes the protocol as expected, it doesn’t collaborate with Alice nor Bob, doesn’t mutate values before forwarding them. It doesn’t cheat.
• The Server is curious though, meaning it will try to learn any information it shouldn’t be able to.
• Alice is honest but curious too.
• Bob is honest but curious too.

We’re now able to prove whether the protocol is secure or not (according to this definition).