Looking for cipher that uses one ciphertext

Question

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.

Answer 1

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.

" Hash decrypts key, key decrypts cipher... why? "

" https://security.stackexchange.com/questions/8245/gpg-file-size-with-multiple-recipients "

Information leakage from the ecryptfs filesystem

" How can two different passphrases unlock the same content? "

Answer 2

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.

2. Encrypt the temporary key/password with the password of each recipient.

3. Stick the list in front of the encrypted messages.

The recipient needs to find his entry in the list. A simple approach is to label them, but those labels are public.

Another approach is to encrypt a concatenation of the temporary key and a static value. The recipient will try to decrypt every list entry until he finds one decryption that contains that static value.

Note: This approach of creating a temporary key is often used with public/private key cryptography, for example in emails. When combining asymmetric and symmetric algorithms in this way, it is called Hybrid cryptosystem.

Answer 3

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.