14
$\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).

Improve this question
$\endgroup$
3
  • $\begingroup$ What about the one on Wikipedia? en.wikipedia.org/wiki/Oblivious_transfer#1-2_oblivious_transfer $\endgroup$
    – mikeazo
    Jun 25, 2013 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, 2013 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, 2013 at 13:59

2 Answers 2

Reset to default
9
$\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.

Improve this answer
$\endgroup$
5
  • 2
    $\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, 2015 at 18:27
  • $\begingroup$ @mikeazo Should it be k^e instead of 'k' in #5 of the second solution? $\endgroup$
    – Oleg Gryb
    Apr 9, 2017 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, 2017 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, 2017 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, 2017 at 22:16
3
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Moderator note: this has been flagged as "not an answer". That's because it consists mostly of links, and that's discouraged, see Provide context for links there. A summary of the Oblivious Transfer protocol linked to, why it's a 1-out-of-2 OT protocol, and (since the information is dated) an update on the status, would greatly improve the question! $\endgroup$
    – fgrieu ♦
    Jun 21, 2022 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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