All too often I describe some process saying that "he" did something to "his" message,
and it makes sense in my own head, but no one else can figure out which of the several people involved that those pronouns refer to.
Or worse -- sometimes I say that "the message is encrypted", but I don't say who does it and with which key.
That's why all the good cryptographers describe processes using Alice and Bob, avoiding pronouns -- even if they have to use "Bob" six times in one sentence.
Have you considered maybe possibly editing your question by replacing all the pronouns with names? That would make it much easier for us to figure out what you're trying to ask.
Let me also add Eve:
- Eve stole Mark's private key.
- Bob wants to send a message to Alice and Mark, but Bob doesn't want anyone else to read it -- in particular, Bob doesn't want Jim or Eve to read it. However, Bob wants Jim to be able to block Eve from reading the message, even it means that Mark can't read the message after all. Also: Bob is in a remote location where every message Bob sends must go over a public network that people like Eve can read.
- Mark wants to receive the message, but after Bob sent the message, Mark found out that Eve stole Mark's private key, and Mark immediately informed Jim of the breach.
- Jim is pretty reliable, but he's in yet another remote location where every message Jim sends or receives must go over a public network that people like Eve can read.
The SSS system that John Deters describes sounds good. Another approach (similar to the TOR onion routing system) could be:
Assume Bob, Jim, Mark, and Alice have previously shaken hands and traded public keys with everyone else in the group.
Bob sends a message M1 to Jim, and M6 to Mark and Alice.
Sometime after Bob sends his messages, Eve steals Mark's private key.
Jim somehow learns of this key compromise before he gets the message from Bob.
Jim authenticates that the message M1 really came from Bob, then decrypts it with Jim's private key, resulting in a partially decrypted message M2 that says something like "Please forward this message to Mark: " followed by an encrypted message M3 and "Please forward this message to Alice: " followed by encrypted message M4.
- Since Jim can't send anything to Mark any more (since if he does, Eve would also be able to read the message), he shreds M3.
- (optional) Jim authenticates that M4 really came from Bob.
Jim sends M4 to Alice without change.
(If Jim learns that Alice's key was compromised after he sends message M4 out, it's too late -- there's nothing anyone can do to prevent whoever stole Alice's key from recovering the plaintext message).
Alice authenticates that M4 really came from Bob, then decrypts it with Alice's private key, resulting in a plaintext message M5.
(optional) perhaps M5 is actually a symmetric key. Bob encrypts the original long plaintext message with key M5 and then signs the resulting ciphertext, sending the resulting signed message M6 directly to Alice and Mark. Once Alice authenticates that M6 really came from Bob, Alice uses M5 to decrypt M6 and recover the original long plaintext message.
Even after Eve collects all the public messages -- M1, M4, and M6 -- Eve still cannot recover the original long plaintext message, unless Jim colludes with Eve by leaking M3, or Alice colludes with Eve by leaking M5 or the original long plaintext message or Alice's private key.
- double-encrypting things, which sounds like trouble
- encrypting basically the same piece of data against two different keys
Neither one is really a problem in practice, assuming you are using a modern encryption system.
Generating many encrypted messages, each one a singly-encrypted ciphertext of the same data but encrypted using a different public key,
is a key part of the standard way of generating standard OpenPGP encrypted files intended for more than one recipient.
(It actually generates many short encrypted "packets", each one encrypted with a different public key, but all of them representing the same symmetric key).
Encrypting some plaintext with one key, and then encrypting the resulting ciphertext with some other key, and then encrypting that resulting ciphertext with yet another key, is a common operation in the TOR anonymity network.
There is a lot of confusion about both approaches -- see http://crypto.stackexchange.com/search?q=double+encryption .
Historically, some classic encryption algorithms had problems with one or the other or some similar-sounding setup.
In particular, the infamous "two time pad".
However, modern algorithms generally use a mode of operation that makes such attacks just as difficult as the full brute-force attack -- i.e., infeasible.
What about padding?
I'm assuming you're using an off-the-shelf high-level implementation of symmetric-key encryption -- such as, for example, practically any program that supports AES-encrypted ".zip" files.
I'm assuming you're using an off-the-shelf high-level implementation of public key encryption -- such as, for example, practically any program that supports the standard OpenPGP format.
That software should automatically use, by default, a good mode of operation --
the software should generate initialization vectors, handle padding, etc. with no extra effort on your part. If it doesn't, I recommend switching to some other code library that is easier to use.