# Looking for cipher that uses one ciphertext

I'm new to Cryptography so please free to edit my question for clarity and add the appropriate tag.

I'm trying to research if the following is possible. Suppose

1. John has a message that he encrypts to share with more than one recipients.
2. The message is different, i.e. it's unique to the recipients (though the recipients don't know that).
3. The recipients must each be given a unique password so as not be able to decrypt each others message.

Questions (sorry for more than one question, but they're related):

• What approach should I take? Links to references or further reading will be appreciated
• Is the one encryption with different decryption the wrong approach to achieve goal 3? What approaches would you suggest?

The objective are two fold:

1. allow a teacher to easily (hence 1 ciphertext) encrypt "answers to exam questions" (text and binary data e.g. images) to distribute to selected students. Reason for not allowing anyone outside of the selected students is to prevent students who haven't taken the exam to know the answer thus allowing reuse of the exam questions.
2. allow students to see teacher's comments and feedback specific to that students' attempted answers. Since students answered differently, the students need not share the same password and are discouraged from using the same password. This also helps teacher track which students leaked answers to future students.

Thanks

Update: I've bought Bruce Schneier's book to learn up on terminology and concepts so I won't be at a loss with terms like ciphertext.

-
(I am also new to cryptography). Have you looked at RSA? Here the recipients have their one key that John can use to encrypt the message with. Thereby each will receive a message that "looks" different. Only the recipient will be able to decrypt the message. – Thomas Jun 11 '12 at 21:03
@Thomas, If the message is large, RSA is not a good option (crypto.stackexchange.com/questions/14/…) – mikeazo Jun 12 '12 at 11:38
Hi Thomas, thanks for the suggestion. I'll go investigate RSA. – Global nomad Jun 12 '12 at 13:43
Hi Mikeazo, yes, the message is (I guess) considered large. About 30 MB worth of binary content. – Global nomad Jun 12 '12 at 13:44
Maybe you should give a step by step description of the protocol you have in mind. That might help understanding what your goals are. – Maeher Jun 12 '12 at 14:02

There are several systems that sound vaguely similar to your description. Would either one (or both) of the following systems work for you? If not, what exactly about systems is unsuitable for your application?

deniable encryption

You give a unique key to each of a bunch of people.

You think up a unique plaintext message intended for one and only one person.

Later, you publicly publish some huge encrypted file (one ciphertext).

Each person uses their own unique key to extract their own unique plaintext message from that file.

It's not possible for any one person (as long as everyone keeps their own key secret), or even several of the intended recipients working together, to find out if there are any other messages in the huge encrypted file, much less exactly how many messages there are or what exactly the other plaintext messages say.

deniable encryption

File intended for several recipients

Each person has a unique key. (Typically each person has their own private key, generates a public key from it, and each person publishes the public key or gives you their public key some other way).

You think up a plaintext message you want to send to some, but not all, of those people.

You make up a completely new one-time symmetric key that no one else could possibly know. You encrypt the plaintext message with this new key, making one large file. You encrypt and re-encrypt the one-time key multiple times, each time with the key (typically the public key) of one of the intended recipients. You end up with lots of short files, one for each intended recipient, and one large file that is the same for everyone. The standard OpenPGP system archives that large file and all the corresponding short files together into one slightly larger file.

Then you publish that slightly larger file (one ciphertext).

Each person uses their own unique key to extract the one-time symmetric key, and then uses that key to decode the large file.

Then every one of the intended recipients knows there is one and only one message in the large encrypted file, and they all know they are all reading exactly the same message as all the other intended recipients.

It's pretty obvious how many intended recipients there are for a file in OpenPGP format, even to people who are not a intended recipient. But there are work-arounds to camouflage exactly how many (other) recipients there are, even to someone that is a intended recipient and can decode the file into readable plaintext.

Information leakage from the ecryptfs filesystem

-
 Thanks David. Deniable encryption sounds like a good place for me to start. – Global nomad Jun 12 '12 at 18:48

I'm a bit confused, because the title of your question seemed to imply a different scenario than your actual question.

Is your goal, given one message $m$ to produce ciphertexts $c_1, \ldots, c_n$ such that each recipient can decrypt one of the ciphertexts but not check whether the other ciphertexts encrypt the same message? This can be achieved using any IND-CPA secure encryption scheme (such as a secure block-cipher in an appropriate mode of operation). Simply use a secure key derivation function for passwords such as PBKDF2 for each password $p_i$ resulting in key $k_i$ and encrypt $c_i \gets \mathsf{Enc(k_i,m)}$. Because each recipient knows his own password, he can derive his key and decrypt, but the security of the encryption scheme ensures that he cannot check whether the other $c_i$s contain the same message. (Short of brute-forcing the passwords of course.)

You title however implies that you only want a single ciphertext. If that is the case I think you need to clarify, what exactly you goal is.

-
Hi Maeher, thanks for asking. Yes, I do want a single cipher text when I encrypt, but I want the recipients to have different cipher text when they decrypt. Hope I'm making sense. Please let me know if I'm assuming something that isn't the way cryptography works. Thanks. – Global nomad Jun 12 '12 at 13:42
Maybe you want to have a ciphertext $c$ and Users $U_1,\ldots,U_n$ should be able to decrypt, but they should not be able to find out, who the other recipients are? That sounds like anonymous broadcast encryption. That is actually an active research topic (e.g. eprint.iacr.org/2011/476.pdf) and I currently do not know of a really efficient instantiation. – Maeher Jun 12 '12 at 13:59
Yes Maeher, that sounds like what I'm after. Thank you. – Global nomad Jun 12 '12 at 14:07

If it is okay for the recipients to know that the message was send to at least n people, you can do this:

1. Create a temporary key/password that is only valid for this message alone. Then use it to encrypt the message.