MPC Techniques Series, Part 5: What is Oblivious Transfer, and why should you care?
By Ivan Damgård, Professor and Chief Cryptographer at Partisia
Oblivious transfer (OT) is a fundamental tool in cryptography. In this blog post, I will explain what OT is, what it can be used for, and how it can be implemented.
In a nutshell, OT can be thought of as a very strange communication channel. It works as follows: a sender, Alice, can send two bits, b0 and b1, to a receiver, Bob, via OT. However, only one of the two bits will make it to Bob and he can choose which of the bits he wants to receive. Moreover, Alice does not find out which of these bits Bob chose to receive.
To explain this more concretely, we can say that Bob has a choice, bit c, and what happens is that he gets bc, but not the other bits. Moreover, Alice does not learn the value of c.
To get a feeling for what is going on, let’s assume Bob has two padlocks that look absolutely similar, but he only has the key to one of them. Bob labels the padlocks with 0 and 1, making sure that the one with label c is the one he has the key for. Bob sends the padlocks to Alice, who writes down her bits on two pieces of paper which she puts in two boxes. Now, the box containing b0 is locked with the padlock labelled 0, and similarly for the other box. Finally, the boxes are returned to Bob. He can open just one of the boxes, so he will only learn which of the bits that he has chosen. Because the padlocks look alike, Alice does not know which bit Bob wanted to see. Below, I will explain how you can make OT happen in a similar way, by using cryptographic tools.
BUT WHY, I hear you ask? Why would anyone want such a weird communication channel? In fact, there are many good reasons, and here is one simple, but still interesting example: imagine Alice and Bob are in their teens. Bob wonders if Alice wants to go out with him, and maybe Alice wonders as well. But, of course, Bob cannot just ask. If Alice says no, that would be terribly embarrassing — his confidence would be ruined! What is needed is a secure way in which Alice and Bob can both learn if there is mutual interest. By secure, we mean that if the answer is no, no one learns more than that. So, if Alice is not interested, she already knows the answer will be no, so she does not find out if Bob really was interested or not. And so Bob is safe from embarrassment.
As it happens, OT can be used to solve this: Say Alice has a bit A that is 1 if she wants the date and 0 otherwise, similarly Bob has a bit B reflecting his interest. We can now rephrase the goal: what the parties want is to learn the product AB, since this bit is 1 exactly if there is mutual interest. Now Alice and Bob can do an OT as we just described. It turns out we can arrange it such that the bit Bob receives will exactly be AB. As choice bit c, Bob uses his interest bit B. Now, Alice knows that if Bob has B=0, the output is AB=0. But if B=1, then the product is AB=A.
Therefore, Alice sets b0=0 and b1=A. This means that, when the OT is done, indeed Bob has received AB and can tell Alice what the answer was.
Why is this secure? Well, Alice learns only the result AB (when Bob tells her) because the OT does not reveal what Bob’s choice was. Also, Bob only learns the result, because the OT will only tell him the bit he chose to receive: if Bob has B=0, he will receive b0 = 0 and will not learn b1=A. If he has B=1, he will learn b1=A=AB, but this is fair: if you are interested in the date, the answer will tell you if the other party was interested.
In an upcoming blog post on garbled circuits, you’ll see a very different application of OT. But I should also mention that even the simple idea of computing mutual interest has more serious applications than just embarrassment-free dating: match-making among many parties can be used by companies to find out who wants to do business with whom, while keeping business strategies private.
Let us now see how to actually build OT from cryptography using RSA encryption, which I will assume you have seen before. A reminder: RSA involves a public key with two numbers (n,e), and you can encrypt a number X between 0 and n, by raising X to the power e, divide by n and take the residue. If (n,e) is Alice’s public key, there is a corresponding secret key (n,d) known only to Alice. If X was encrypted to get ciphertext number Y, Alice is the only party who can decrypt, by raising Y to power d.
To get OT from this, we do as follows:
- We assume Bob has Alice’s public key (n,e). Using his choice bit c, Bob chooses two ciphertext numbers Y0, Y1, such that he knows the plaintext number for one of them, but not the other one. Concretely, Bob chooses a random Xc and RSA encrypts it to get Yc, whereas the other number Y1-c is chosen at random. Compared to the padlocks and boxes example above, Y0, Y1 correspond to the padlocks, where Yc is the one Bob has the key for, and Xc will play the role as the key to the padlock.
- Bob sends Y0, Y1 to Alice. She can decrypt both using her secret RSA key and gets X0, X1 as the result. Her final step is to encrypt b0 using X0 as a key and encrypt b1 using X1 as a key. So, she computes encryptions E(X0, b0), E(X1, b1) and sends them to Bob. The details of how this encryption works are not so important, the only thing that matters is that if you know X0 say, then you can easily compute b0 from E(X0, b0), but if you don’t, you have no idea what b0 is (see footnote below).
- Using Xc, Bob decrypts E(Xc, bc) and learns bc.
Alice does not learn Bob’s choice because Y0, Y1 are both random numbers between 0 and n, it is impossible to tell which one Bob knows the plaintext for. On the other hand, if RSA is secure, Bob only learns bc: if he chooses the other RSA ciphertext number Y1-c at random, he would have to break RSA to find X1-c. If he cannot compute X1-c, he cannot decrypt
E(X1-c, b1-c) and cannot learn b1-c. This protocol is secure against passive attacks, that is, when parties always follow instructions (see this post on various types of attacks). Still, you may be thinking that it seems very tempting for Bob to break the rules and choose both of Y0,Y1 with a known plaintext number — Alice cannot tell what happened and Bob would learn both bits. You would be right, and this is indeed a problem in practice. Fortunately, we have a tool in cryptography called zero-knowledge proofs. Such proofs offer a way for Bob to convince Alice that he followed the rules, without giving away the value of c. We will not describe zero-knowledge proofs in detail here, as this would be much too long a story for this blog post. Stay tuned, however, for a blog post on zero-knowledge proofs later in this series.
Footnote: But if you really want to know, Alice can set d0 to be the least significant bit of X0 and then let the encryption E(X0,b0) be the XOR (the sum modulo 2) of d0 and b0.. For technical reasons, the least significant bit is a good choice: given only the RSA encryption Y0 of X0, you cannot guess d0, not even slightly better than flipping a coin — assuming RSA is secure.
About the author
Ivan is professor and head of the research group in cryptography at Aarhus University. Ivan is co-founder of Cryptomathic, Partisia and Sepior. He is one of the top cited and publishing researchers in cryptography, is a fellow of the IACR (International Association for Cryptologic Research), and received the 2015 RSA Award for Excellence in the Field of Mathematics.