Introduction

This is the most in-efficient version of Yao, it does not use point and permute. The oblivious transfer protocol explained is also in-efficient by Nigel Smart.

Problem - Tinder

Alice and Bob are deciding whether they should go on a date. However, they do not want to be publicly rejected.

• If Alice says no, she should not find out if Bob said no and vice versa.
• If Alice says yes, however she will find out if Bob says no.

Ideal world

In the ideal world, there is a trusted third party, Trent.

Alice sends a 1 to Trent indicating that she would like to go on a date with Bob.

Bob sends a 0 indicatin he would not like to go on a date with Alice.

Trent sends back the result which is 0 AND 1 = 0 to both parties. Indicating that they are not a match.

Information revealed

Alices receives a 0 from Trent, which indicates that Bob said no. Since she said yes.

Bob receives a 0 from Trent, which indicates nothing; Alice could have said no also.

Real world

In the real world, Trent is on vacation. However, we can get the same result by using Yao’s Garbled Circuit on an AND gate.

Roles

Alice plays the role of a Garbler, as she is garbling the circuit(single gate).

Bob plays the role of an Evaluator, as he will be evaluating the circuit(single gate)

Choice

• Alice chooses 1
• Bob chooses 0

Shared view

Alice first looks at all of the possible input values and outputs of the AND gate, as a table.

Both Alice and Bob have a copy of this table, ie the circuit which is being evaluated, is public.

Labelling the inputs

Alice then assigns random labels to the possible choices, her and Bob can make. We label these as $A_0$,$A_1$,$B_0$,$B_1$.

Example : $A_0$ is a random label that represent Alices choice of 0.

The table now looks like this:

Encrypting the table

Alice now wants to encrypt each row, such that Bob can only decrypt a single row. In particular, Bob should only be able to decrypt the second row which corresponds to $(A_1, B_0)$.

Encrypting each row

TO encrypt each row, Alice Hashes together the inputs, which serve as a shared key. This shared key is used to encrypt the output.

Using the first row as an example:

1. $K_0$ = $H(A_0, B_0)$
2. $R_0$ = $ENC_{K_0}(0)$

The second line says that 0 is encrypted under the key $K_0$.

Repeating this for all four rows, transforming the encrypted table into four ciphertext values $R_0$, $R_1$, $R_2$, $R_3$.

Alice to Bob

Alice sends Bob the ciphertext values, and the label corresponding to her choice. In this case it will be $A_1$.

Bob Evaluates the circuit

Bob receives Alices encrypted choice, however he is not able to decrypt any of the rows because the shared key requires his encrypted choice. Here are a few choices Bob could make:

Bob sends his choice to Alice

If Bob sends his choice to Alice, this would defeat the purpose of the protocol, since now Alice knows what Bob’s choice is.

Alice sends both $B_0$ and $B_1$

Alice has already sent $A_1$. If she sends both $B_0$ and $B_1$, Bob will be able to decrypt both the second and last rows.

How does this reveal Alice’s choice?

The key is in the fact that $B_1$ reveals the other persons choice.

Imagine :

• Bob decrypts the last row to be equal to 1.
• Bob now knows that $B_1$ corresponds to his choice of 1.
• Since it is an AND gate, he now knows that $A_1$ corresponds to a 1.

This has now revealed Alice’s choice.

What if the first and third row are decrypted?

The first and third row, both output 0. Since one of $B_0$ or $B_1$ has to be 1. This tells Bob that Alices choice was 0.

Oblivious Transfer

The problem we face now, is that Bob needs to know which label out of $B_0$ and $B_1$ correspond to his choice. However, he does not want Alice to figure out his choice.

To do this, Bob can use Oblivious transfer.

Without going into detail right here, this allows Bob to choose either $B_0$ or $B_1$ accordingly without giving away his choice. See appendix

Evaluation Step

Bob now has $B_0$, $A_1$, $R_0$, $R_1$, $R_2$, $R_3$ .

He creates the shared key by doing:

$K_0$ = $H(A_1, B_0)$

He then decrypts each row, until he gets a 0 or a 1. All other ciphertext decryptions will give unrecognisable plaintext.

Rows are not shuffled

Bob can still learn Alice’s input, if the rows are not shuffled. Note that Bob decrypts the second row and since they both have a shared view of the original table. This row corresponds to Alice’s choice of 1.

To fix, Alice randomly permutes the rows $R_0$, $R_1$, $R_2$, $R_3$ before sending to Bob.

Alice does not know

Bob has successfully decrypted the second row, however Alice does not know the answer. In the Oblivious transfer protocol, Alice does not know which choice Bob made.

To solve this, Bob sends the output back to Alice.

Appendix

Oblivious Transfer 1/2

In the oblivious transfer protocol, Alice the sender has two messages $m_1$ and $m_2$. Bob the receiver wants to choose between $m_1$ and $m_2$, without telling Alice what choice he made. Furthermore, Alice only wants Bob to know either $m_1$ or $m_2$, but not both.

Below is a protocol by Bellare and Micali which describes how this could be achieved:

Notation

We denote group elements with capital letters, and scalars with lowercase.

We define a canonical generator of a chosen prime order group as $G$.

Bob’s public keypair would be denoted as $(b, B)$ where $B = bG$

Encrypting the messages

Alice first generates a nonce keypair $(k, K)$ .

Alice then creates a shared key using Bob’s public key : $kB$, this is then hashed and used to xor the message.

$E_m$ = $msg \oplus H(kB)$

Alice sends $(K, E_m)$ to Bob

Decrypting the messages

Bob first creates the same shared key using his secret key and the nonce point : $bK$

msg = $E_m \oplus H(bK)$

The intuition is that $kB = k(bG) = b(kG) = bK$. Added to the fact that xoring the message is a method of doing symmetric encryption.

Bob sends 2 Public keys

Naively, we could have Bob send two public keys and Alice would encrypt both messages using the two public keys.

This is broken however, because Bob can decrypt both messages. We want him to only be able to decrypt one message. So we need a way to ensure that he only knows the secret key to one of the public keys he sends.

Alice sends a Random Key

To solve this, Alice first sends a random Point $P$. Bob again sends 2 public keys, however the difference between the two public keys sent, must be equal to the random point $P$.

This ensures that Bob does not know both Public keys, unless he knows the DLOG to $P$.

Example

Concretely, lets imagine that Bob sends $K$ and $K-P$. Bob knows the private key corresponding to $K$, however he has no idea what the private key for $K-P$ is as this would require $p$ where $P = pG$.

How does this work with Yao?

In the Yao protocol, Alice has $B_0$ and $B_1$. If Bob sends Alice ($K$ , $K-P$), then Alice will encrypt $B_0$ under the key $K$ and $B_1$ under the key $K-P$. Bob will only be able to decrypt $B_0$, which corresponds to the choice of 0.

Alternatively, if Bob wants to pick the yes choice, then he would send Alice ($K-P$, $K$).

Can Alice figure out Bob’s choice?

Similarly since Alice does not know $k$ she is unable to figure out which key belongs to Bob.

Can Alice use her own KeyPair?

Although there is nothing in the protocol, disallowing Alice to use her own keypair, it is much safer to have each encrypted message use a nonce. In the case that Alice’s secret key is revealed, all previous messages which have been encrypted using it, will now be un-obfuscated. Whereas in the case of a nonce, only one oblivious transfer will be affected.

How does this satisfy our needs?

In this protocol, Alice is unable to deduce Bob’s choice and Bob is unable to pick both.

Are there any assumptions made?

We assume that Alice encrypts the messages correctly, although if she does not then Bob will know eventually. Not in the oblivious transfer because the $B_0$ and $B_1$ are random, so it is not possible to deduce whether the output was correctly decrypted here. However, in Yao’s protocol, Bob will not get the correct sharedkey to decrypt exactly one row.