2
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\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
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.