Prove that any two rounds of (1,2)-oblivious transfer, that is semi honestly secure, imply public key encryption.

My ideas so far:

Let's say Alice samples two $n$ random strings $(x_1, x_2)$, and Bob will ask for $x_i$ using the given OT.

Now, wlog, we'll deal with 1 bit encryptions.

The main idea I had, is that Bob will send a random string $s$ when he asks for the string $i$ with the given OT. Then, Alice will always answer with $pk=(x_i, r)$ (the inner product). According to the Goldreich-Levin theorem, guessing $x_i$ based on the inner product is only with negligible advantage over 1/2. In such case, everyone can encrypt using $E_{pk}(m, r)=r, pk \oplus m$, and only Alice can decrypt cause she knows both $x_i$. However, how could she tell which $x_i$ has been used?

I'm not sure if this is indeed PKE, cause there may be many PKs, which looks weird at first. Moreover I didn't actually use the OT-ness, and the fact OT is two rounds, which may be related.

Secondly, I think that making some secret key agreement between Alice an Bob will suffice to build PKE, but I'm not sure either how to build it from OT.

So the real problem is how the public key should be generated, and that's my problem. Please help me to prove this theorem.

  • $\begingroup$ It's late here, so no answer and no guarantees, but: You may be overcomplicating things. What's wrong with using the first (the receiver's) OT message (for a random bit b) as the encryption key and the corresponding randomness as the decryption key. Encryption of m would then work by simply computing the sender's message for (m,m). $\endgroup$ – Maeher Jan 11 '18 at 7:26
  • $\begingroup$ I'm not sure I fully understand you, because I think that now everyone could decrypt. $\endgroup$ – Napoleon Jan 11 '18 at 7:39
  • $\begingroup$ No, clearly the randomness used to create the receiver's OT message is needed to extract m from the sender's message. (Otherwise the sender could simply extract and see which message he gets, thus breaking receiver privacy.) And this randmoness is kept secret as the decryption key. $\endgroup$ – Maeher Jan 11 '18 at 7:42
  • 2
    $\begingroup$ Suppose the two-round OT protocol is defined as follows. S has input $(x0, x1)$, R has input $b$. There are 3 functions f1, f2, f3: $M1=f1(b, r1)$. $M2=f2(x0,x1,M1, r2)$. $x_b=f3(M1, M2, b, r1)$. The OT protocol is executed by R sending $M1$ to the S, S sending $M2$ to R; and R locally computes $f3$. Constructing a PK encryption. A party randomly picks a bit $b$ and $r1$. Compute $pk=f1(b,r1)$ ($sk=(b,r1)$). Encryption of $m$ is done by $c = f2(m, m, pk, r2)$ for some $r2$. Decryption is done by $m = f3(pk, c, b, r1)$. $\endgroup$ – redplum Jan 12 '18 at 2:03
  • 1
    $\begingroup$ @redplum Yes, this is what I was talking about. Should be CPA secure. The proof should work in using a hybrid argument with three hops, first using sender privacy to switch out the $m$ that does not correspond to $b$, then using receiver privacy to flip $b$ and finally using sender privacy again to replace the second $m$. $\endgroup$ – Maeher Jan 12 '18 at 3:16

Your Answer

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

Browse other questions tagged or ask your own question.