1
$\begingroup$

$(E,D)$ is a (one-time) semantically secure cipher where the message and ciphertext space is $\{0,1\}^n$. $E'(k,m)$ is defined as

$E′(k,m)=E(0^n,m)$

The question is whether $E'(k,m)$ is (one-time) semantically secure?

I thought that the random chosen key $k$ might be $0^n$, therefore the adversary cannot distinguish the messages $m0$ and $m1$ when encrypted with the key $0^n$. Therefore, the scheme is semantically secure. However, the answer states that

To break semantic security, an attacker would ask for the encryption of $0^n$ and $1^n$ and can easily distinguish $EXP(0)$ from $EXP(1)$ because it knows the secret key, namely $0^n$.

Can you elaborate on the answer more? I don't understand how the key is known ("because it knows the secret key") and how we can find that the messages $0^n$ and $1^n$ should be used to break the semantic security (Can we try the whole message space?)?

$\endgroup$
  • 3
    $\begingroup$ If you hard-code the key it's part of the algorithm and by Kerckhoff's principle the attacker knows this then, so he can just try it. $\endgroup$ – SEJPM May 14 '16 at 13:33
  • $\begingroup$ That makes the key issue clear, thanks! Does this mean that we don't have to use $0^n$ and $1^n$ to break the semantic security, we can actually use any two different messages to break the semantic security? $\endgroup$ – sha1 May 14 '16 at 13:40
  • $\begingroup$ Possible duplicate of Is the identity function a one-way function? $\endgroup$ – fkraiem May 14 '16 at 16:02
  • $\begingroup$ Maybe we need a "master question" about this. Preferably one which does not involve the quite vague statement known as Kerckhoff's principle, which causes more confusion than it solves. $\endgroup$ – fkraiem May 14 '16 at 16:06
1
$\begingroup$

The algorithm $E'(m)=E'(k,m)=E(0^n,m)$ is defined with a hard-coded key, thus the key is part of the algorithm definition of $E'$.

Because of Kerckhoff's principle we generally assume the attacker to know our algorithm definition.

Because of this, the attacker can just try decrypting the challenge ciphertexts of the eavesdropper security game himself (or try encrypting the challenge messages himself if encryption is deterministic).

The choice of the messages $0^n$ and $1^n$ is entirely arbitrary and any message would suit the purpose here with these two having the advantage of the shortest possible description (instead of something like $0^{n-1}||1$).

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