Adam Back writes:
On the simple hash/encrypt approach, I think this should work:
Alice sending non-transferably signed message to Bob and Charlie:
Encrypt_Bob(K_B), Encrypt( K_B, Sign_Alice(K_B||Bob), H(msg) ),
Encrypt_Charlie(K_C), Encrypt( K_C, Sign_Alice(K_C||Charlie), H(msg) ),
I see, that makes sense. It's similar in flavor to the suggestion
I made last night, to do separate MACs on the msg using K_B and K_C.
Then I was having Alice sign the Bob- and Charlie-encrypted key blocks,
rather than the MAC and public key values directly, which probably amounts
to much the same thing. Here's where proofs of security would be really
nice, to see if any of these constructions have subtle problems, or if
one is superior to the others.
The one other point I see is that as the number of recipients increases,
then a priori it becomes less likely that so many people would all
collude to forge a message from Alice. So although you have security
in principle, the deniability becomes a little more questionable in
practice when the number of recipients is large.