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.

  • $\begingroup$ Can you start by writing down your definitions of security against message recovery and semantic security, and perhaps say where you've gotten stuck? $\endgroup$ – Squeamish Ossifrage Apr 29 '18 at 20:33
  • $\begingroup$ @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. $\endgroup$ – Daniel Apr 29 '18 at 20:57
  • $\begingroup$ If you have a cipher, e.g. a block cipher and a mode of operation such as CTR then what makes it semantically secure? $\endgroup$ – Maarten Bodewes Apr 29 '18 at 22:12
  • $\begingroup$ @MaartenBodewes I don't know what you mean with mode of operation. $\endgroup$ – Daniel Apr 29 '18 at 22:47
  • $\begingroup$ 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 $\endgroup$ – 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.

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.


Your Answer

