Build a cipher that is secure against message recovery attack but not semantically secure

Question

I know the definitions of both of the securities (against message recovery and semantic), but I don't know how to actually build a cipher that meets these conditions, I mean, I don't know how to define "let $\mathcal{E} = (E,D)$ where $E(k,m) = \;...$ and you can see that it is secury against MR because of ..., but is not semantically secure because of ..." yet.

I would like to know, at least, how to start building such cipher.

---

Message recovery attack:

Let $\mathcal{E} = (E,D)$ be a cipher. The challenger chooses a random $m$ from message space $\mathcal{M}$, a random $k$ from key space $\mathcal{K}$, computes a random $c \xleftarrow[]{\text{R}} E(m,k)$ and sends $c$ to the attacker.

The attacker, then, sends $\hat{m}$ back to the challenger.

The attacker wins the game if $\hat{m} = m$. Let $p$ be the probability $Pr[\hat{m} = m]$.

The advantage of this attacker is $\Big\vert \; p - \frac{1}{\Vert \mathcal{M} \Vert} \; \Big\vert$

The cipher is secure against MR attack if this advantage is negligible for all efficient attackers.

Answer 1

The basic idea of constructing such a cipher is to exploit the fact (and the main difference between the definitions!) that $m$ is sampled uniformly at random from the message space for message-recovery security and can be chosen very specifically for semantic security.

This means that the easiest solution probably special-cases the encryption output for one specific input and acts securely for all others. The chance of hitting this one special-case is then negligible with message-recovery security, but can be made arbitrarily high with semantic security, allowing the special case encryption to be distinguished from any other encryption.

Answer 2

Let $\mathcal{M} = \{0,1\}^{n}$ and let $\mathcal{C} = \{0,1\}^{n}$, and let $\mathcal{K} = \{$binary sequences of odd parity of length n$\}$.

Key Generation: $k \leftarrow_{\\\$} \mathcal{K}$.

E(k,m) = $m \oplus k$, bitwise.

D(k,c) = $c \oplus k$, bitwise.

Let $\mathcal{E} = (E,D)$ over $\{ \mathcal{M}, \mathcal{K}, \mathcal{C} \}$.

Let $\mathcal{A}$ be any efficient MR adversary of $\mathcal{E}$.

Let F be the challenger for $\mathcal{A}$, so challenger F computes $k \leftarrow_{$} \mathcal{K}$, $m \leftarrow_{$} \mathcal{M}$ and $c \leftarrow E(k,m)$, and sends this c to $\mathcal{A}$.

And let $\mathcal{A}$ outputs $\hat{m}$ upon recieving c from F and analysing it.

$MRAdv[\mathcal{A}, \mathcal{E}]$ = |Pr($\mathcal{A}$ wins) - $\frac{1}{|\mathcal{M}|}$|.

Pr($\mathcal{A}$ wins) = Pr($\hat{m}$ = m) = Pr(K = $c \oplus \hat{m}$) = [ Pr(K = $c \oplus \hat{m}$| $\hat{m}$ is of even parity, c is of even parity) Pr($\hat{m}$ is of even parity| c is of even parity) Pr(c is of even parity) + Pr(K = $c \oplus \hat{m}$| $\hat{m}$ is of even parity, c is of odd parity) Pr($\hat{m}$ is of even parity| c is of odd parity) Pr(c is of odd parity) + Pr(K = $c \oplus \hat{m}$| $\hat{m}$ is of odd parity, c is even parity) Pr($\hat{m}$ is of odd parity| c is of even parity) Pr(c is of even parity) + Pr(K = $c \oplus \hat{m}$| $\hat{m}$ is of odd parity, c is of odd parity) Pr($\hat{m}$ is of odd parity| c is of odd parity) Pr(c is of odd parity)] $ \leq$ $\frac{1}{2}[0+\frac{1}{2^{n-1}} + \frac{1}{2^{n-1}} + 0 ]$ = $\frac{1}{2^{n-1}} = \frac{2}{|\mathcal{M}|}$.

So, $MRAdv[\mathcal{A}, \mathcal{E}] \leq \frac{1}{2^{n-1}}.$

So $\mathcal{E}$ is MR secure.

Now the claim is that $\mathcal{E}$ is Semantically not secure.

Let C be the SS challenger, and let's construct the SS adversary $\mathcal{B}$, the following way:

$\mathcal{B}$ chooses the following messages from the message space $m_{0} = 000\cdots00$ and $m_{1} = 000\cdots01$, and sends them to it's challenger C.

Then the challenger C computes $b \leftarrow_{$} \{0,1\}$ and $k \leftarrow_{$} \mathcal{K}$ and $c \leftarrow E(k,m_{b})$, and sends this c to $\mathcal{B}$.

Then $\mathcal{B}$ computes $\hat{b}$, the following way:

$\hat{b} = 0$, if c is of odd parity, else $\hat{b} = 1$.

Pr($\hat{b} = 1$ | b = 1 ) = 1, Pr($\hat{b} = 1$ | b = 0 ) = 0, because k is always of odd parity and we have chosen $m_{0}$ and $m_{1}$ of different parities.

So, $SSAdv[\mathcal{B}, \mathcal{E}] = 1$, which is not negligible. So $\mathcal{E}$ is not semantically secure.