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.

  • $\begingroup$ 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. $\endgroup$
    – fkraiem
    Commented Oct 3, 2015 at 18:48
  • $\begingroup$ 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. $\endgroup$
    – Kat108
    Commented Oct 4, 2015 at 15:21
  • $\begingroup$ Do you know an example of an IND-CPA encryption scheme? If yes, is it identity-revealing? $\endgroup$
    – fkraiem
    Commented Oct 4, 2015 at 16:59

1 Answer 1


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 \mathbin\| 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. The IND-CPA security notion does not care if some information about the key is revealed.


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.