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.

$\endgroup$
2
  • $\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$ Apr 29, 2018 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, 2018 at 20:57

2 Answers 2

2
$\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.

$\endgroup$
0
$\begingroup$

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.

$\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.