I'm having the following protocol specification of a k-out-of-n oblivious transfer (as part of some E-Voting protocol) and it's bugging me that I fail to understand it with my basic knowledge of cryptography. This particular implementation looks totally different from the usual 1-out-of-n "the receiver generates multiple public keys but only one is valid" examples I can find in the Internet.

1. Is this OT somehow based on the ElGamal encryption scheme? Especially the exponentiation within a prime order group remind me of it, but I don't see what the PK and SK are?

2. In order for it to be working, and according to the the final equation $m_{sj} = c_{sj} \oplus k_j$ I'm expecting to get $m_j$ from simplyfing $c_{sj} \oplus k_j$.

$m_j = k\oplus c\\ m_j = H(b\cdot g^{-sr}) \oplus c\\ m_j = H((\Gamma(s_j)\cdot g^{r})^s \cdot g^{-sr}) \oplus c\\ m_j = H(\Gamma(s_j)^s \cdot g^{sr} \cdot g^{-sr}) \oplus c\\ m_j = H(\Gamma(s_j)^s) \oplus c\\ m_j = H(\Gamma(s_j)^s) \oplus (m\oplus k)\\ m_j = H(\Gamma(s_j)^s) \oplus (m\oplus H(\Gamma(i)^s))$

So, $H(\Gamma(s_j)^s)$ must be equal to $H(\Gamma(i)^s)$

How can that be? How can some counter $i$ be equal to the senders query $s_j$? Is the selection $s$ basically the index of $m$ that he wants to receive.

• Check your working going from line 2-3 of your equations. I think you're missing an $s$ exponent. – pscholl Feb 16 '17 at 17:44
• Indeed! Thank you. It became a bit less confusing, but yet not 100% clear to me :) – user66875 Feb 16 '17 at 19:34
• Is there still something missing from the answer you've received? If so please indicate what you're missing. Otherwise please accept the answer and - if applicable - assign the bounty. – Maarten Bodewes Feb 26 '17 at 0:19

1. Recall the ElGamal encryption scheme: The secret key is some random $$r \in \mathbb{Z}_q$$, the public key is $$h := g^r$$ , together with the group order $$q$$ and the generator $$g$$ of the group $$\mathcal{G}$$. To encrypt a message $$m \in \mathcal{G}$$, one chooses a random $$s \in \mathbb{Z}_q$$ and computes the ciphertext $$(c_1, c_2) := (g^s, m \cdot g^{rs})$$. To decrypt the ciphertext, one computes $$c_2 \cdot (c_1)^{-r} = c_2 \cdot (g^s)^{-r} = m$$.
In case of your OT scheme, $$g$$ and $$q$$ are assumed to be known and are therefore not part of the public key. Now, instead of sending $$g^{r_j}$$, the receiver sends $$\Gamma(s_j) \cdot g^{r_j}$$. When the sender raises this to the power of $$s$$, this results in $$\Gamma(s_j)^s \cdot g^{r_j s}$$. Hence, the $$d = g^s$$ and $$b_j = \Gamma(s_j)^s \cdot g^{r_j s}$$ sent by the sender correspond to an encryption of $$\Gamma(s_j)^{s}$$. This is then used by the receiver to obtain $$H_{\ell}(\Gamma(s_j)^s)$$, which was in turn used to (one-time pad) encrypt the actual message. The trick here is to allow the sender to encrypt $$\Gamma(s_j)^s$$ without knowing $$\Gamma(s_j)$$.
2. Yes, the selection $$s_j$$ corresponds to the $$j$$th index the receiver wants to receive.