Chosen-ciphertext attack on receiver anonymity

[Brent Waters <[e-mail]>]

I wanted to bring up an issue that had to do with chosen-ciphertext 
attacks on receiver anonymity.

The specific case I am worried about is when the "throw-keyid" option is
used to encrypt a message to multiple recipients. My understanding is that
the throw-keyid option should hide the identity of the a receiver of the
message (by throwing away the key-id) even from other receivers of a
message. Suppose I made such an encryption of M to Alice and Bob, then the
hybrid encryption (at a high level) would look something like this:
1)Choose random symmetric key key K
2)Ciphertext: (C1,C2,C')=E_{KeyAlice}(K)E_{KeyBob}(K),E_K(Message)
where C1,C2 are asymmetric encryption and C' is a symmetric key 
encryption.

At this point Alice and Bob can both decrypt the message, but neither can
tell if the other was the other receiver. Suppose Bob suspects Alice was 
the other receiver. Then he can create a ciphertext:
(C1,C'')=E_{KeyAlice}(K)E_K(NewMessage)
and send this to Alice, if Alice responds to this in a meaningful way she
was the other receiver. NewMessage could be something simple like "Do you
want to go to lunch?" which would likely elicit a response. Note, this can
be a problem even if the ciphers are CCA-secure.

I have been discussing this type of a problem in the context of BCC 
privacy for email programs with Adam Barth and Dan Boneh. However, there 
could be wider implications as PGP is used in other contextes.
Anyway, I would be interested to hear comments.

Regards,
Brent

http://crypto.stanford.edu/~bwaters/