# Why Bellare-Micali Oblivious Transfer Construction requires ElGamal with hashed key?

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

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.

• 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". – Mark Dec 25 '20 at 18:16
• 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. – Lorenzo Dec 25 '20 at 18:21
• Under such a choice, $m_b = H(v_0^k)\oplus v_1$ does not typecheck, as $H : \mathbb{G}\to\{0,1\}^\ell$. – Mark Dec 25 '20 at 18:24
• 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. – Lorenzo Dec 25 '20 at 18:38
• 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. – Lorenzo Dec 25 '20 at 18:49

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.
• 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. – Lorenzo Dec 28 '20 at 16:12
• 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. – Yehuda Lindell Dec 29 '20 at 15:10