# 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. Aug 13 '14 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. Aug 13 '14 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. Aug 13 '14 at 13:43
• @ddddavidee Those comments would make a fine answer when put together and if the contents of the links are briefly explained. Aug 16 '14 at 14:01
• @owlstead thanks. Write down as an answer and added few details. Hope it is good. Aug 16 '14 at 14:26

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.