Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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? en.wikipedia.org/wiki/Oblivious_transfer#1-2_oblivious_transfer –  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
add comment

1 Answer 1

up vote 4 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
add comment

Your Answer

 
discard

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.