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

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.

• Can you start by writing down your definitions of security against message recovery and semantic security, and perhaps say where you've gotten stuck? Apr 29 '18 at 20:33
• @SqueamishOssifrage done. I'm stuck in the fact that I've seen ciphers that get something as input and send something as output, but this definition makes me struggle at creating a cipher that would be safe for this attack scenario and (at the same time) be semantically secure. Apr 29 '18 at 20:57

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.

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.