I have to solve this exercise and I really could use some help:

Show that any 2-round key-exchange protocol (that is, where each party sends a single message) satisfying $Definition$ $9.1$ can be converted into a public-key encryption scheme that is CPA-secure.

$Definition$ $9.1$:
A key-exchange protocol II is secure in the presence of an eavesdropper if for every probabilistic polynomial-time adversary $A$ there exists a negligible function negl such that

$Pr [KE^{eav}_{A,\pi} (n) = 1] \le \frac{1}{2}+ negl(n)$

  • 1
    $\begingroup$ Hint: Look at DH and ElGamal / ECIES / DHIES. $\endgroup$ – SEJPM May 30 '19 at 8:43

The methods suggested in the comments are useful in practice, but they base on some specific key exchange protocols. It's useful to proove that a public key encryption scheme can be created from any such $KE^{eav}$-secure protocol.


Let $\langle s_A, m_A \rangle, \langle s_B, m_B \rangle$ denote the state and transmitted message from Alice and Bob within the protocol respectively. Let $Prot_A(1^n) \rightarrow \langle s_A, m_A \rangle$ denote the process of Alice creating her secret state and the message to be transmitted to bob, $Prot_B(m_A) \rightarrow \langle s_B, m_B \rangle$ be the process of Bob sampling his random state and creating the message based on the random state and Alice's message. We then define the key to be $f(s_A, m_B) = k_A = k = k_B = f(s_B, m_A)$ for $f$ some predefined function.


Now, we create a public-key encryption scheme as follows:

\begin{align*} Gen&(1^n) \\ & \langle s_A, m_A \rangle \leftarrow Prot_A(1^n) \\ & \langle s_k, p_k \rangle = \langle s_A, m_A \rangle \\ & Output \space \langle s_k, p_k \rangle \\ % % Enc_{p_k}&(m): \\ & \langle s_b, m_b \rangle \leftarrow Prot_B(p_k) \\ & Output \space \langle m_B, f(s_B, p_k) \oplus m \rangle \\ % % Dec_{s_k}&(c): \\ & \langle m_B, c' \rangle = c \\ & k = f(s_k, m_B) \\ & Output \space k \oplus c' \end{align*}


Since $f(s_k, m_B) = f(s_A, m_B) = f(s_B, m_A) = f(s_B, p_k)$ the correctness follows from the correctness of a one-time-pad.


We can proceed to prove CPA-security by reduction. Assume there is an adversary $\mathcal{A'}$ which succeeds at breaking the CPA experiment for our public-key encryption scheme $\Pi'$. We construct an adversary $\mathcal{A}$ breaking the KE experiment as follows:

  1. $\mathcal{A}$ receives $m_A, m_B, \hat{k}$ as input
  2. $\mathcal{A}$ runs $\mathcal{A'}(1^n, m_A)$ and receives $m_0, m_1$
  3. $\mathcal{A}$ samples $b \leftarrow \{0,1\}$ uniformly and computes $c = \langle m_B, m_b \oplus \hat{k} \rangle$
  4. $\mathcal{A}$ runs $\mathcal{A}'(c)$ and receives $b'$
  5. $\mathcal{A}$ outputs 0 iff $b = b'$

Now we have 2 cases to consider -- when $\mathcal{A}$ received the true key ($[K=\hat{k}]$) and when it received a uniformly random string ($K \neq \hat{k}]$). But in the first case, the result of the KE experiment will be 1 exactly when $\mathcal{A}'$ succeeds in the CPA experiment. In the other scenario, since $\mathcal{A}$ samples b uniformly, the result of the experiment will be 1 when $b = b'$ with probability $\frac{1}{2}$. Hence:

$Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1] = \frac{1}{2}Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1 | K = \hat{k}] + \frac{1}{2}Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1 | K \neq \hat{k}] = \frac{1}{2}(Pr[Pubk^{CPA}_{\mathcal{A}', \Pi'}(1^n) = 1] + \frac{1}{2}) = \frac{1}{2}(\frac{1}{2} + \frac{1}{p(n)} + \frac{1}{2}) = \frac{1}{2} + \frac{1}{2p(n)}$

This contradicts $\Pi$ being $KE^{eav}$-secure, hence $\mathcal{A}'$ cannot exist and $\Pi'$ is CPA-secure.

  • $\begingroup$ The notation of tuples is somewhat inconsistent in your construction. Also, the symbols your looking for are probably "\langle"=$\langle$ and "\rangle"=$\rangle$ instead of $<$ and $>$. $\endgroup$ – Maeher Feb 7 '20 at 9:22
  • $\begingroup$ Thanks for the feedback, I fixed the notation. $\endgroup$ – Boyan Hristov Feb 10 '20 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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