Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to explain the concept of 1-out-of-2 oblivious transfer to folks who haven't seen this idea before. I can explain what properties it provides, but it's also helpful if I can show a simple protocol for 1-out-of-2 OT, to give people a feeling that this is achievable.

What's a simple protocol for 1-out-of-2 OT that doesn't need much explanation or advanced cryptography to understand?

I don't need something you'd actually want to use in practice. It doesn't need to be the most efficient, the most practical, or have a clean security proof: just something that gives the basic idea. I'm asking only for pedagogical purposes, not to build a real system. Assume the audience is familiar with basic concepts of cryptography (including things like RSA, Diffie-Hellman, etc.) but may not be familiar with advanced concepts (e.g., zero-knowledge proofs, secure multiparty computation).

share|improve this question
What about the one on Wikipedia? – mikeazo Jun 25 '13 at 16:09
@mikeazo, thanks, that one's not bad! Looks pretty clean. Is there an even simpler protocol, or is that about as good as it gets? (Do you want to post the one on Wikipedia as an answer?) – D.W. Jun 25 '13 at 17:29
You'll have to let me know how you end up presenting this and how it is received. – mikeazo Jun 26 '13 at 13:59
up vote 6 down vote accepted

There are two that I know of that are pretty simple.

I'll first start with one that requires a "Trusted Initializer" where we assume that there is a party Ted which is trusted by both Alice and Bob and only needs to be present for the initialization stage. This is an extension of a quantum protocol and was proposed by Rivest in Section 7.

  1. Alice holds $m_0,m_1\in\{0,1\}^k$, Bob holds $c\in\{0,1\}$ and wants $m_c$
  2. Ted privately gives Alice $r_0,r_1\in\{0,1\}^k$, chosen at random
  3. Ted generates a private bit $d\in\{0,1\}$ and privately sends $d,r_d$ to Bob
  4. Bob sends $e=c\oplus d$ to Alice
  5. Alice sends $f_0=m_0\oplus r_e$ and $f_1=m_1\oplus r_{1-e}$ to Bob
  6. Bob computes $m_c=f_c\oplus r_d$. About $m_{1-c}$ Bob learns nothing.

The second comes from Wikipedia where it is instantiated with RSA (so exponentiations are done in the RSA group parameterized by the public key).

  1. Alice holds $m_0,m_1$, and an RSA key pair $(e,d,N)$. Bob holds the public key $(e,N)$ of Alice, $c\in\{0,1\}$ and wants $m_c$
  2. Alice generates random $x_0,x_1$ and sends them to Bob
  3. Bob chooses a random $k$, computes $v=x_c + k^e$ and sends $v$ to Alice.
  4. Alice computes $k_0=(v-x_0)^d$ and $k_1=(v-x_1)^d$ and sends $m_0'=m_0+k_0$ and $m_1'=m_1+k_1$ to Bob
  5. Bob computes $m_c=m'_c-k$ and learns nothing about $m_{1-c}$

You'll notice that the two protocols are somewhat similar which is kind of cool if you wanted to present both. The 2nd removes the assumption of a trusted initializer and replaces it with a public key pair for Alice.

share|improve this answer
Important note on the RSA protocol; Alice needs to generate a fresh RSA key for every transfer; if not, that is, if Alice uses the same RSA key for two exchanges, then Bob can cheat and for his second transfer, learn the different between a secret from the first transfer (that he didn't pick) and a secret from the second. That is, from the first exchange with secrets $(m_0, m_1)$, he learns $m_0$, from the second exchange with secrets $(m'_0, m'_1)$, he can learn $m'_1 - m_1$ – poncho Jun 26 '15 at 18:27

There's a new really simple OT protocol based on DH. It's even practical. Watch this video. For the paper and source code, go here.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.