# From 2-round key-exchange protocol to a public-key encryption scheme CPA-secure

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)$$

• Hint: Look at DH and ElGamal / ECIES / DHIES. – 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.

### Notation

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.

### Construction

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*}

### Correctness

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.

### Security

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.

• 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 $>$. – Maeher Feb 7 '20 at 9:22
• Thanks for the feedback, I fixed the notation. – Boyan Hristov Feb 10 '20 at 23:54