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?

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

Other solutions have been published, using both public and symmetric key cryptography. These attack 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 pay TV (you pay so you can decrypt the broadcast), the second to DVD encryption (all players can play a DVD unless they are 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 recipients is a random key for a symmetric algorithm.

  • $\begingroup$ OK, tried to rewrite it a bit, could you take a look at the last paragraph? It doesn't parse for me. $\endgroup$
    – Maarten Bodewes
    Aug 16 '14 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.