1-2 Oblivious Transfer

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 m0 and m1. 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 m1 but doesn’t learn anything about m0. 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:

ProtocolAlice(Secret)AliceAndBobBob(Secret)
Alice has two pieces of data.m0 and m1
Alice generates key pair. Public key is shared with Bob. Private key is kept secret with Alice.Private Key – dPublic Key – e
Alice generates two random messages and sends them to Bob.x0 and x1
Bob chooses which data they want. Let’s denote the choice as k = 0 or k = 1.xk
Bob generates a random message.r
Bob blinds the chosen xk and shares the result with Alice. v = xk + re
Alice computes two new values t0 and t1. 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 t0 or t1 is r.t0 = (v – x0)d

t1 = (v – x1)d
Alice combines the original data and sends them to Bob.m0‘ = t0 + m0

m1‘ = m1 + t1
Once again Bob chooses mk‘ and computes mk‘ – r, thereby revealing the value of mk. The other message is completely garbage for Bob.mk‘ – r
Oblivious Transfer Protocol

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 mk.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: