0
$\begingroup$

The idea of the Bellare-Micali Oblivious Transfer Constructions is the following:

enter image description here

Informally, the receiver is required to generate two public keys $y_b$, $y_{b-1}$ such that it knows only the secret key paired with $y_b$ (where $b$ is its choice bit), indicated with $k$. In order to prevent the receiver from cheating, the sender requires that the two generated public keys have to satisfy a certain constraint, i.e., $y_b \cdot y_{b-1} = c$ . In such a way, the receiver cannot know both private keys or it can compute DLOG. At this point, the receiver sends the two public keys to the sender. Then, the sender encrypts $m_0$ with $y_0$ and $m_1$ with $y_1$ and sends both encryptions $c_0$, $c_1$ to the receiver. Finally, the receiver obtains $m_b$ by decrypting the chipertext $c_b$ (corresponding to its choice bit) using the private key $k$ (note that $c_b$ is the only chipertext it can decrypt).

While the general idea is clear to me, I do not get why ElGamal is not computed as $y_{0}^{r_{0}} \cdot m_{0}$ (and $y_{1}^{r_{1}} \cdot m_{1}$) but $H(y_{0}^{r_{0}}) \oplus m_{0}$ is used instead.

Improve this question
$\endgroup$
5
  • $\begingroup$ Where do the $m_i$ live? Depending on the answer (there are two natural ones here), one of $y_i^{r_i}\cdot m_i$ or $H(y_i^{r_i})\oplus m_i$ "typechecks". $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Dec 25, 2020 at 18:16
  • $\begingroup$ I am particularly interested in the case in which $m_i \in \{0,1\}$ (the same domain of $b$), but I am curious about what other option you have in mind and how it would work instead as well. $\endgroup$
    – Lorenzo
    Commented Dec 25, 2020 at 18:21
  • $\begingroup$ Under such a choice, $m_b = H(v_0^k)\oplus v_1$ does not typecheck, as $H : \mathbb{G}\to\{0,1\}^\ell$. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Dec 25, 2020 at 18:24
  • $\begingroup$ Right, what the receiver would obtain, if the hash is used and (for example) $m_b = 1$, is $m_b = 0^{l-1}1$. Would it make sense if the first $l-1$ bits are ignored? If $y_i^{r_i} \cdot m_i$ is used instead I still see a problem. If $m_i = 0$, then $c_i = 0$ and $m_i$ would leak. $\endgroup$
    – Lorenzo
    Commented Dec 25, 2020 at 18:38
  • $\begingroup$ If you look at "Definitions and Obilivious Transfer by Yehuda Lindell" video at 1:16:00, apparently the hash version has to be used (I suppose, by eventually adjusting the domain) but I do not get why. $\endgroup$
    – Lorenzo
    Commented Dec 25, 2020 at 18:49

1 Answer 1

Reset to default
2
$\begingroup$

The hash needs to be used in order to be able to simulate. In particular, consider the case that the receiver is corrupted. The simulator can't know the choice of $b$ so doesn't know if the receiver can decrypt the first or the second message. Therefore, in order to simulate, the simulator has no choice but to just choose random values to represent $H(y_0^{r_0})$ and $H(y_1^{r_1})$; denote these random values by $\rho_0$ and $\rho_1$. Then, the simulator can see which of the two queries $y_0^{r_0}$ or $y_1^{r_1}$ the receiver makes to the random oracle. (One can show via the CDH assumption that the receiver cannot make both queries.) Now, once the simulator receives the query $y_b^{r_b}$ to the random oracle, it can send $b$ to the trusted party and get back $m_b$. Then, it sets the response of the random oracle to be $\rho_b \oplus m_b$ (i.e., $H(y_b^{r_b})=\rho_b \oplus m_b$). You should be able to verify that this indeed gives the right distribution.

Next, in order to simulate the corrupted sender, the simulator has to be able to extract the values $m_0,m_1$. Since it doesn't know $r_0,r_1$ (since no ZKPOK are used), this is problematic without the hash. However, .... I'm actually stuck at this point; I'm not sure how you would do this without adding a proof of knowledge of the discrete log of $c$ in the beginning (maybe my brain is fried right now). Then once you have this ZKPOK, you wouldn't need the hash for this part of the proof anyway. Note that you only need to do the ZKPOK once for many OTs using the same $c$.

Note that the lectures refer to the semi-honest setting. In this case, I don't believe that the hash is actually necessary, and it suffices for $m_0,m_1$ to be in the group.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If I've understood what you meant in the lecture, first the semi-honets case is presented, then the malicious one. Regarding the latter, I've seen another version using ZKP instead of hash, but I have not found the paper where it comes from yet. The first part of your explanation is super clear now, thanks! I need time to understand the rest. $\endgroup$
    – Lorenzo
    Commented Dec 27, 2020 at 17:27
  • $\begingroup$ Actually, they only cover the semi-honest setting in the proof (and they state that in the lecture they only cover semi honest). $\endgroup$
    – Yehuda Lindell
    Commented Dec 28, 2020 at 7:58
  • $\begingroup$ I believed you were referring to the video lecture I cited in the comments above (Definitions and Obilivious Transfer), from which I've understood that adding the constraint over the public keys ($y_b \cdot y_{b-1}=c$) makes the protocol secure against malicious adversaries. $\endgroup$
    – Lorenzo
    Commented Dec 28, 2020 at 16:12
  • $\begingroup$ I don't remember what's in the video. However, as you can see from my answer, the constraint with a ZK proof of knowledge of the discrete log of $c$, together with the hash function will be secure. $\endgroup$
    – Yehuda Lindell
    Commented Dec 29, 2020 at 15:10

Your Answer

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

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