Why is encrypting a key under itself dangerous?

Question

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?

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.