I learnt about oblivious transfer when reading up about garbled circuits. As an engineer this feels like a fascinating, almost magical protocol. And it’s not just me. Everyone I talked to about this protocol had the same reaction – disbelief. Here’s an engineer’s perspective.

#### Objective

Let’s create two fictional characters – Alice and Bob. Alice has two pieces of data. Bob wants to select one of them without Alice learning about Bob’s selection. Additionally, Alice doesn’t want Bob to learn anything about the data Bob did not select.

As a concrete example, imagine Alice has data m_{0} and m_{1}. Bob can get one of them by presenting the choice as k = 0 or k = 1. If Bob chooses k = 1, then Bob learns the value m_{1} but doesn’t learn anything about m_{0}. Also, Alice doesn’t learn that Bob chose k = 1.

This is a very useful protocol to build more complex multi-party computation applications.

#### Protocol

Let’s consider an implementation of oblivious protocol using RSA. Alice generates an RSA key pair and shares the public key with Bob. The private key is stored secretly by Alice. Below are the series of steps that are executed to transfer data:

Protocol | Alice(Secret) | AliceAndBob | Bob(Secret) |
---|---|---|---|

Alice has two pieces of data. | m_{0} and m_{1} | ||

Alice generates key pair. Public key is shared with Bob. Private key is kept secret with Alice. | Private Key – d | Public Key – e | |

Alice generates two random messages and sends them to Bob. | x_{0} and x_{1} | ||

Bob chooses which data they want. Let’s denote the choice as k = 0 or k = 1. | x_{k} | ||

Bob generates a random message. | r | ||

Bob blinds the chosen x_{k} and shares the result with Alice. | v = x_{k} + r^{e} | ||

Alice computes two new values t_{0} and t_{1}. You can see that one of them will be completely random while the other is r. But since r itself is a random message, Alice doesn’t learn which of t_{0} or t_{1} is r. | t_{0} = (v – x_{0})^{d}t _{1} = (v – x_{1})^{d} | ||

Alice combines the original data and sends them to Bob. | m_{0}‘ = t_{0} + m_{0}m _{1}‘ = m_{1} + t_{1} | ||

Once again Bob chooses m_{k}‘ and computes m_{k}‘ – r, thereby revealing the value of m_{k}. The other message is completely garbage for Bob. | m_{k}‘ – r |

You may want to execute the above protocol with k = 0 or k = 1 to satisfy yourself that Alice doesn’t learn Bob’s choice of k and Bob doesn’t learn the data other than m_{k}.

## Leave a Reply