0
$\begingroup$

Let $E$ be a semantically secure cipher.

Let $E'(k,m) = E(k,E(k,m))$.

How would one prove that $E'$ is not necessarily secure even if $E$ is?


It doesn't make sense to me. If you consider the advantage of an attacker $\mathcal{A}$ over a semantically secure cipher $E$, you have $SSadv[\mathcal{A},E] = \epsilon$, where $\epsilon$ is negligible.

If you call for $E(k,E(k,m))$, you should have $E(k,E(k,m)) = E(k,c)$, where $c$ is $\epsilon$-distant of being random, so you give an advantage of $\epsilon$ to the attacker.

When you compute $E(k,c)$, analogously you give another advantage of $\epsilon$ to the attacker, so you give an overall advantage of $(\epsilon + \epsilon)$, and such a sum would be negligible as well.

$\endgroup$
  • 3
    $\begingroup$ what happens if $E$ is a stream cipher? $\endgroup$ – Richie Frame Apr 30 '18 at 19:41
  • $\begingroup$ @RichieFrame if $E$ is, for example, one-time pad (which is a stream cipher), let $m$ be the plaintext and $c$ the ciphertext , so instead of $c_i = m_i + k_i$, it would be $c_i = m_i + 2k_i$, and it isn't clear for me how the latter is not secure given the former is secure $\endgroup$ – Daniel Apr 30 '18 at 20:06
  • 2
    $\begingroup$ @Daniel You're almost there: What if you use exclusive-or to combine the key stream instead of addition? $\endgroup$ – Ella Rose Apr 30 '18 at 20:35
  • 1
    $\begingroup$ so $c_i = m_i \oplus k_i \oplus k_i = m_i$, and it would be trivially broken. Thanks! I wouldn't come up with the idea of using a stream cipher nor modifying the one-time pad like this. $\endgroup$ – Daniel Apr 30 '18 at 20:50
1
$\begingroup$

Summarizing the answer from the comments:

what happens if E is a stream cipher? ~ Richie Frame

What if you use exclusive-or to combine the key stream instead of addition? ~ Ella Rose

So $c_i=m_i\oplus k_i\oplus k_i=m_i$, and it would be trivially broken. Thanks! I wouldn't come up with the idea of using a stream cipher nor modifying the one-time pad like this. ~ Daniel

$\endgroup$
0
$\begingroup$

The only component that defines security in this case is 'k'. i.e., the more random 'k' is, harder it is for the attacker to guess. Rest of the functions are deterministic. i.e., the definitions of E and E' and m are known to the outside world.

So, it doesn't matter if you do a two level or three level encryption, if you use a single key as a base, then that becomes the single point of attack or the weakest link in the chain. Breaking that would break your n-level encrypted ciphering text.

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