Suppose user Alice wants to send a large plaintext message P to
multiple users Bob, Carol and Dave.  Assume Alice, Bob, Carol, and
Dave each has publick-private key pairs.  Show an efficient protcol
that allows A to send one digitally signed and encrypted copy of the
message such that its contents are protected against disclosure to
users other than Alice, Bob, Carol, and Dave, and against modification
by users itehr than Alice.

---

Request for Question Clarification by rbnn-ga on 21 Oct 2002 00:15 PDT

One simple possibility would be to encrypt the message P separately
with the public keys each of Bob, Carol, and Dave; before each copy of
P is encrypted, however, the name (or address) of the respective user
Bob, Carol or Dave is prepended. Then bundle these three encrypted
messages together, prepend a header that tells at which byte each of
the three copies of the messages begins, and sign the whole thing with
Alice's public key.

Unfortunately I have a feeling this may not be what you are looking
for because the problem emphasizes "a large plaintext message P" and
this winds up making the three copies of the message.

So I hope another researcher here can give a more elegant solution or,
if this is what you are seeking, perhaps an expanded version can serve
as an answer, although I'd want to do more research myself to check
that there is no more elegant solution here.

---

Clarification of Question by israel55555-ga on 21 Oct 2002 09:33 PDT

I confirmed that the questionis correct as listed.  So please do your best.

They key to interpreting this problem is that the message is a LARGE
plaintext message P. I interpret this to mean that it is expensive to
send it; for example, maybe the message is 100 gigabytes long and must
be sent over a 56K modem.

I should mention that I am not always certain how much detail in the
explanation you need. If something is unclear, please do not hesitate
to ask for clarification and I would be happy to explain further.

So, we do not want to use a protocol that involves encrypting the
message multiple times.

I spent a lot of time thinking about it, and, as I mentioned in the
clarification request, my first solution involved this: Alice encrypts
the message separately using the public keys for Bob, Carol, and Dave;
then she concatenates the result together and digitally signs the
message.

This works, but it wastes a lot of space.

So I thought of a different scheme that is space efficient.

We name with the four public-private key pairs

AliceKey=(Alice_private, Alice_public)

BobKey=(Bob_private, Bob_public)

CarolKey=(Carol_private, Carol_public)

DaveKey=(Dave_private, Dave_public)

If M is a message and if K=(x,y) is a key pair, then we let E(M,K) be
the result of encrypting M using the key pair K, and we let D(M,K) be
the result of decrypting the result using the key pair K.

Now, if M is a message and M' is another message, we let bundle(M,M')
be the "bundling" of the messages. By bundling, I mean that we
concatenate them together and we prepend a header that tells us at
which byte M and M' begin. (So that someone who gets the message can
know where M begins and where M' begins in the message). Similarly,
bundle(M,M',M'') bundles the three messages M, M', and M'' together.

The key idea here, so to speak, is that Alice first chooses ANOTHER
(private,public) key pair. It has to be one whose private key she
doesn't mind being disclosed.

Let's call this new pair 

NewKey=(New_private,New_public)

The first thing Alice does is to encrypt New_private using each of
Bob, Carol, and Dave's public key:

NewPrivateBob=E(New_private,BobKey)
NewPrivateCarol=E(New_private,CarolKey)
NewPrivateDave=E(New_private,DaveKey)

She also encrypts the original message P using NewKey

EncryptP=E(P,NewKey)

Now she bundles all the information into a big bundle.

bundle1=bundle(New_public, NewPrivateBob, NewPrivateCarol,
NewPrivateDave, EncryptP) .

We are almost done. If, say, Bob gets bundle1, he can decrypt it by
extracting NewPrivateBob, getting the new private key by applying
D(NewPrivateBob,BobKey), then decrypting EncryptP via
D(EncryptP,NewKey) .

No other user than Bob, Carol, or Dave can read EncryptP, since to
read EncryptP it is necessary to have New_private, and that has been
encrypted so that only Bob, Carol and Dave can know it.

But we are not quite done. First, how does Bob know which of the three
keys that are sent is his?

We solve this by creating a header bundle that just has the names of
the recipients in the order in which their encryptions of the NewKey
occur:

header="Bob Carol Dave" (we'd use the real names of the recipients
here, assuming no name contains a space character)

bundle2=bundle(header,bundle1)

Finally, to prevent any tampering, we can just have Alice digitally
sign bundle2.

result=AliceDigitallySign(bundle2) .

Now, the result cannot be modified by anyone other than  Alice because
she has digitally signed it. (If you need more detail on how Alice can
digitally sign something, let me know).

Each of the recipients can read the message by decrypting the
appropriate New_private private key, and using that private key to
decrypt the included message.

That is, say Carol wants to read the message. She extracts bundle2,
and gets the header. She sees that she is the second recipient. She
extracts bundle1 and gets New_public and NewPrivateCarol. She computes
NewKey by decrypting NewPrivateCarol using here private key. She
extracts EncryptP from the bundle and decrypts it using NewKey.

But noone else can read the message, because to do so requires the
New_private key.

Search Strategy:

I did an extensive search on cryptographic protocols using keywords
such as:

cryptographic protocols
cryptography multiple users
cryptography email

However, I did not find this exact problem addressed, so I solved it
from general facts about public and private keys.

I believe that PGP does this. If I remember correctly, when you are
encrypting an email, you just add multiple users to the list of
recipients for the encryption process. You can get PGP at
www.pgpi.com. I'm posting this as a comment rather than an answer
since I'm not 110% that this 1) works 2) is exactly what you are
looking for, but I hope this works for you.

Just to simplify:
1) The Message M is encrypted with a new (random) simmetric key K
   C=E(M,K)
2) A different copy of the key K is encrypted with each one of the recipients
   public keys: EK1 = E(K,PK1), EK2= E(K, PK2), ..., EKn=E(K, PKn)
3) All the encrypted keys (EK1, EK2, ..., EKn) are sent with the encrypted 
   message (C).
This is the basic idea behind some protocols like PGP and S/MIME.

kerberos-ga: excellent comment. Most of the machinery in my answer
just entails manipulating header data; these are things already
present in protocols like S/MIME (one of the key things MIME does).