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.

image showing protocol description

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.

  • 2
    $\begingroup$ Check your working going from line 2-3 of your equations. I think you're missing an $s$ exponent. $\endgroup$
    – pscholl
    Commented Feb 16, 2017 at 17:44
  • $\begingroup$ Indeed! Thank you. It became a bit less confusing, but yet not 100% clear to me :) $\endgroup$
    – user66875
    Commented Feb 16, 2017 at 19:34
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Commented Feb 26, 2017 at 0:19

1 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.


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.