# Multi-key decryption

Let's assume I want to send a secret message to $N$ recipients in an asymmetric way.

My message could be encrypted with $N$ different public keys $p_i$ one after another and send to each user individually. In practice only a symmetric key $k$ is sent in an asymmetric way I guess, but that's not the point.

Even direct symmetric encryption comes into mind where the key $k$ is encrypted with each $p_i$ once and attached to message body afterwards. Of course the message length grows with rising $N$.

So I wonder if there is an encryption function having $N$ public keys as input. This fixed length encrypted message should be decrypted by corresponding private keys only. Is this possible?

By the way: Is this concept similar to TV channel encryption?

-
What you are describing is essentially broadcast encryption, where one wants to encrypt a message to a desired subset of receivers while keeping the ciphertext length short. –  Chris Peikert Aug 13 at 13:25
yes, it is essentialy broadcast encryption, as pointed in an other comment by @ChrisPeikert. It exists two kind of broadcast encryption: one where you name the intended recipients and the other one where you ban a subset of all potential recipients. The first one is similar to the pay-tv: you pay so you can decrypt the broadcast, the latter to the DVD encryption: all producer can play a DVD until the producer is banned. –  ddddavidee Aug 13 at 13:40
You'll find all the definition in one of the first papers about Broadcast Encryption: Broadcast Encryption by Fiat and Naor [courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/…. It presents a symmetric key solution to the problem based on users as leafs on a binary tree. –  ddddavidee Aug 13 at 13:43
@ddddavidee Those comments would make a fine answer when put together and if the contents of the links are briefly explained. –  owlstead Aug 16 at 14:01
@owlstead thanks. Write down as an answer and added few details. Hope it is good. –  ddddavidee Aug 16 at 14:26

The problem you described is addressed and solved in different way by the Broadcast Encryption: roughly the problem is how to encrypt a message intended to more than one recipient. You described a naive approach to the problem, your solution is, indeed, probably the simplest one.

The Broadcast Encryption concept was formalized and defined by Fiat and Naor in their seminal paper Broadcast Encryption. Their solution is based on a binary tree where recipient are leafs of this tree and owns a key for every node from them to the root ($2^n$ leafs, $n-1$ keys per user): a ciphertext is encrypted using the minimal set of nodes covering the set of intended recipient.

Others solutions have been published, using both public and symmetric key cryptography. These attacks different deficiencies of solutions to the problem: size of the ciphertext, size of the user keyring, revocation without re-keying, privacy preserving schemes, ...

Two kinds of broadcast encryption exist: one where you name the intended recipients and the other one where you ban a subset of all potential recipients. This first is similar to the pay-tv: you pay so you can decrypt the broadcast, the latter to the DVD encryption: all producer can play a DVD until the producer is banned. The Fiat and Naor solution is of the first kind.

Note that usually public-key encryption is used with the KEM/DEM paradigm, so the plaintext to be encrypted to multiple recipient is a random key for a symmetric algorithm.

-
OK, tried to rewrite it a bit, could you take a look at the last paragraph? It doesn't parse for me. –  owlstead Aug 16 at 14:36
Yep, that parses, thanks. –  owlstead Aug 16 at 17:15
Thank you for the useful edit. –  ddddavidee Aug 16 at 17:25