I'm currently self-studying to try and understand more about cryptography for work. I'm on question 2.16 on A Graduate Course in Applied Cryptography .

For part a), we're given a cipher $E$ that's semantically secure and asked to create $\hat{E}$ where $\hat{E}$ becomes insecure when the adversary is given $\hat{E}(k, k)$. Since I can't control the details of $E$, I figure $\hat{E}(k, k)$ must somehow reveal the key or some key generation algorithm to the adversary, since anything else should be public already (and yet still semantically secure).

At the same time, any $k$ seems like it should be a valid message, so we have to explicitly know the answer to $\hat{E}(k, k)$ (and can't just stumble upon it when trying $\hat{E}(k, m)$).

To me, this seems to contradict and thus I'm stuck. What am I missing?

Update: I've thought this a little more through and may have some further ideas.

  1. The definition I'm using to verify "semantic security" is that where an adversary submits $m_1, m_2$ and receives $c_x$. At this point, they should have no advantage in guessing which message was encrypted. However, when given $E'(k,k)$, they gain an advantage.

  2. To me, this says that $E'(k,k)$ must somehow reveal information about k, since the scheme should be public by default (Kirchoff's Principle).

  3. Suppose $E'(k, m) = E(k \oplus m, m)$

  4. Therefore, $E'(k,k) = E(0, k)$. Since the decryption alg D should be public, I can decrypt $D(0, E(0, k)) = k$, and thus by giving the adversary $E'(k, k)$ I have given the key.

  5. The adversary submits $m_1, m_2$. Upon receiving $c_1$, they know $k$, and trivially calculates which message was encrypted.

  6. To adjust for the keyspace being smaller than the message space, allow for any excess bits in $k \oplus m$ to be truncated to $|k|$.

Thoughts? Does this work?

  • $\begingroup$ Any key $k$ is not automatically a valid message. This won't answer your semantic security question, but you could make the same argument for the One-Time Pad, but it will be (trivially) dead wrong. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 16, 2020 at 5:24
  • $\begingroup$ Related Encrypting decryption key, Encrypting a key with the same key, for instance using AES $\endgroup$
    – kelalaka
    Commented Apr 16, 2020 at 7:34
  • $\begingroup$ This can be the 0 class for someone thinking in a Perfert Foward Secrecy scheme. We need more than just a $E_k(payldoad,k)$. $\endgroup$ Commented Apr 16, 2020 at 17:34

1 Answer 1


Let $E$ be your cipher. Consider the following cipher: $$E_{k}'(m) = \begin{cases} k & m =k\\ E_k(m) & \text{else} \end{cases}$$ I believe you should be able to reduce the security of $E'$ to the security of $E$ in a rather straightforward manner.

This is a fairly important notion in general though. The notion of "being secure, even if one gets encryptions of functions of the secret key" is known as Key Dependent Messaging security in general. It's a property that (among other things) so far we seem to require to build FHE, but cannot prove that particular FHE schemes have it (instead we generally make the "Circular Security assumption").

Matthew Green has a blog post on it if you want a slightly higher level viewpoint on the topic.

  • $\begingroup$ With this definition, the adversary only gains non-negligible ability to guess if one of their messages is equal to the key, and therefore isn't poly-time bounded right? (Forgive me if I'm missing something & thanks for the response :)) $\endgroup$
    – AeonNeo
    Commented Apr 16, 2020 at 6:07
  • $\begingroup$ There's an issue with that construction $E'$: for key $k$, there are two inputs with output $k$, thus that's no longer a block cipher with the same key and message space. After some back and forth, I see no local fix working in polynomial time. It seems that we need to construct $E'$ from $E$ in quite a different manner. One is $E'_k(m)=E_k(m)\oplus(E_k(k)\oplus k)$ $\endgroup$
    – fgrieu
    Commented Apr 16, 2020 at 6:08
  • 2
    $\begingroup$ @fgrieu $E$ was never supposed to be a block cipher. It's a generic encryption scheme. The clue is that it's supposed to be semantically secure, which a block-cipher (not being an encryption scheme and being deterministic) is not. $\endgroup$
    – Maeher
    Commented Apr 16, 2020 at 7:13
  • $\begingroup$ @Mahear: I see. Then the probability that that two inputs encipher to $k$ becomes negligible with the construction $E_{k}'(m) = \begin{cases} k &\text{if }m =k\\ E_k(m) & \text{otherwise} \end{cases}$ and what I pointed is moot. $\endgroup$
    – fgrieu
    Commented Apr 16, 2020 at 7:24
  • 2
    $\begingroup$ @fgrieu You can avoid even that by just separating the co-domains by, e.g., prefixing $0$ in the former case and $1$ in the latter. (For most common encryption schemes the ciphertext space and the key space are already disjoint, so there would be no need.) $\endgroup$
    – Maeher
    Commented Apr 16, 2020 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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