# 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? – Squeamish Ossifrage 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. – Daniel Apr 29 '18 at 20:57
• If you have a cipher, e.g. a block cipher and a mode of operation such as CTR then what makes it semantically secure? – Maarten Bodewes Apr 29 '18 at 22:12
• @MaartenBodewes I don't know what you mean with mode of operation. – Daniel Apr 29 '18 at 22:47
• This is the first hit I get when I put it into my favorite search engine: en.wikipedia.org/wiki/Block_cipher_mode_of_operation – Maarten Bodewes Apr 29 '18 at 23:13

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.