# 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.

• You are misunderstanding the definition of IND-CPA. To better see where the misunderstanding comes from, it would be helpful if you could give the definition of IND-CPA you are working under, and why you think an identity-revealing cryptosytem necessarily violates it. – fkraiem Oct 3 '15 at 18:48
• I did read up about [IND-CPA] (en.wikipedia.org/wiki/…) and understand that the notion of security that it talks about is different from Identity revealing. Thank you for pointing that out ! However, I still have problems coming up with a concrete example of an identity revealing scheme that is IND-CPA. – Kat108 Oct 4 '15 at 15:21
• Do you know an example of an IND-CPA encryption scheme? If yes, is it identity-revealing? – fkraiem Oct 4 '15 at 16:59

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.