12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about the one on Wikipedia? en.wikipedia.org/wiki/Oblivious_transfer#1-2_oblivious_transfer $\endgroup$ – mikeazo Jun 25 '13 at 16:09
  • $\begingroup$ @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?) $\endgroup$ – D.W. Jun 25 '13 at 17:29
  • $\begingroup$ You'll have to let me know how you end up presenting this and how it is received. $\endgroup$ – mikeazo Jun 26 '13 at 13:59
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – poncho Jun 26 '15 at 18:27
  • $\begingroup$ @mikeazo Should it be k^e instead of 'k' in #5 of the second solution? $\endgroup$ – Oleg Gryb Apr 9 '17 at 19:29
  • $\begingroup$ @poncho - as I understand, in MPC based encryption m0 and m1 are calculated for each encryption/decryption, so fresh RSA key is not required. Right? $\endgroup$ – Oleg Gryb Apr 9 '17 at 19:45
  • $\begingroup$ @OlegGryb: no, that is not correct. In an OT transfer, Bob is supposed to learn only either the current secret $m_0$, or the current secret $m_1$. If Alice reuses the RSA key, Bob could also elect to learn instead the value $m_1 - m'_1$, where $m'_1$ is one of the secrets from a previous exchange. I'm not sure how that could be exploited in a MPC computation, but it certainly violates any proof assumption. $\endgroup$ – poncho Apr 9 '17 at 20:14
  • $\begingroup$ @poncho given that m1.n are just randomly generated numbers (keys) in my scenario uncovering m1.n - m1.(n-1) doesn't really uncover anything. $\endgroup$ – Oleg Gryb Apr 9 '17 at 22:16
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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