Please help me understand this k-out-of-n oblivious transfer protocol

Question

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.

Answer 1

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.