How can IND-CPA encryption be identity revealing? This is problem 10 of Chapter 4 "Symmetric Encryption" (pdf) from Lecture notes by Bellare and Rogaway:


  An IND-CPA secure encryption scheme might not conceal identities, in
  the following sense: given a pair of ciphertexts C, C′ for
  equal-length messages, it might be “obvious” if the ciphertexts were
  encrypted using the same random key or were encrypted using two
  different random keys. Give an example of a (plausibly) IND-CPA secure
  encryption scheme that has this is identity revealing. Then give a
  definition for “identity-concealing” encryption. Your definition
  should imply IND-CPA security but a scheme meeting your definition
  can’t be identity-revealing.


How can a scheme that is identity revealing be IND-CPA? I understand that the view of changing the key is not the same as changing the message but the point of ensuring security is to make sure that no additional information is revealed.
Consider an IND-CPA secure scheme that has the setup, encrypt and decrypt functions as $S_{secure}$, $E_{secure}$ and $D_{secure}$ respectively. Consider another scheme with setup, encrypt and decrypt functions as $S_{IR}$, $E_{IR}$ and $D_{IR}$ respectively.

Let $S_{IR}$ be the same as $S_{secure}$ to produce the key $K$. Let $E_{IR}$ run $E_{secure}(K, x)$ to get the ciphertext $C$, and return $C||H(K)$ where $H(x)$ is a collision resistant one way hash function. Let $D_{IR}$ simply discard the hash part of the ciphertext and use $D_{secure}$ to decrypt.

If, $S_{secure}$, $E_{secure}$ and $D_{secure}$ form an IND-CPA secure encryption scheme, $S_{IR}$, $E_{IR}$ and $D_{IR}$ also form an IND-CPA secure scheme, but the latter is identity revealing.

Note that no additional information about any of the messages is revealed in this case, and this is the only thing that IND-CPA security wants to control for. The IND-CPA security notion does not care if some information about the key is revealed.