{
 "id": "ep4ttw4xby",
 "slug": "broadcast-encryption",
 "title": "Broadcast encryption",
 "updated": "2026-10-21",
 "topic_path": [
  {
   "id": "technology",
   "label": "Technology and the built world",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology"
  },
  {
   "id": "technology.computing",
   "label": "Computing and digital systems",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing"
  },
  {
   "id": "technology.computing.networks",
   "label": "Networks and security",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.networks"
  },
  {
   "id": "technology.computing.networks.network-defense",
   "label": "Network defense and threats",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.networks.network-defense"
  }
 ],
 "geo": [
  {
   "id": "geo.nongeo.t1946.technology.computing.networks",
   "label": "Non-geographic · 1946 to 2000: Networks and security",
   "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.networks",
   "path": [
    {
     "id": "geo.nongeo",
     "label": "Non-geographic",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo"
    },
    {
     "id": "geo.nongeo.t1946",
     "label": "Non-geographic · 1946 to 2000",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946"
    },
    {
     "id": "geo.nongeo.t1946.technology",
     "label": "Technology and the built world",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology"
    },
    {
     "id": "geo.nongeo.t1946.technology.computing",
     "label": "Computing and digital systems",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing"
    },
    {
     "id": "geo.nongeo.t1946.technology.computing.networks",
     "label": "Networks and security",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.networks"
    }
   ]
  }
 ],
 "excerpt": "Broadcast encryption is a cryptographic method that lets a sender encrypt a message so a chosen set of recipients can decrypt it while excluded users, even colluding, learn nothing.",
 "snippet": "Broadcast encryption is a cryptographic method that lets a sender encrypt a message so a chosen set of recipients can decrypt it while excluded users, even colluding, learn nothing.",
 "node": "technology.computing.networks.network-defense",
 "markdown": "# Broadcast encryption\n\nBroadcast encryption is a cryptographic method that lets a sender encrypt a message so that every member of a chosen set of recipients can decrypt it, while other users, even acting together, learn nothing about the content. It addresses a problem ordinary point-to-point encryption does not: on a broadcast channel such as satellite TV or a disc format, the same ciphertext reaches everyone, so the sender must build revocation into the key material rather than the transport. The naive alternative, encrypting a copy of the session key separately for each of the m recipients, costs bandwidth proportional to m; the opposite extreme, assigning a key to every possible subset of users, is bandwidth-optimal but needs storage exponential in the number of users, impractical even for 100 users.<sup>[1](https://eprint.iacr.org/2024/154.pdf)</sup><sup> • </sup><sup>[2](https://per.austrin.se/papers/scbounds.pdf)</sup> Broadcast encryption schemes trade bandwidth, per-user storage, and decryption work to avoid both extremes.\n\n| Fact | Value |\n|---|---|\n| Subset-cover framework (NNL 2001) | Introduced by Dalit Naor and colleagues, CRYPTO 2001<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup> |\n| Subset Difference (NNL 2001) | Header at most \\( 2r - 1 \\) keys for \\( r \\) revoked users; storage \\( (1/2)\\log^{2}N + (1/2)\\log N + 1 \\) keys<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup> |\n| BGW 2005 | Constant-size ciphertexts and private keys (two group elements), fully collusion resistant<sup>[4](https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf)</sup> |\n| Fiat–Naor guarantee | Any coalition of \\( k \\) non-recipients learns nothing; security is information-theoretic<sup>[5](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad.pdf)</sup> |\n| Fiat–Naor parameters | \\( O(k \\log k \\log n) \\) keys per user; \\( O(k^{2} \\log^{2} k \\log n) \\) broadcast messages<sup>[5](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad.pdf)</sup> |\n| Main deployment | Subset Difference method suggested for use by the AACS standard for Blu-ray and HD-DVD content protection<sup>[6](https://link.springer.com/article/10.1007/s10623-012-9702-6)</sup> |\n| Performance axes | Bandwidth (transmission overhead), space (per-user storage), time (decryption computation)<sup>[2](https://per.austrin.se/papers/scbounds.pdf)</sup> |\n\n## How it works\n\nA broadcast encryption scheme is a triple of algorithms (Setup, Broadcast, Decrypt). Setup builds per-user private key material; Broadcast takes the set of revoked users R and a fresh session key K and outputs a broadcast message B; Decrypt computes K for any user in the privileged set.<sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup> In the common symmetric formulation, Encrypt(m, A, k_master) outputs a header h and a ciphertext c: the header is a list of subset indices together with encryptions of the session key under the corresponding subset keys, of the form c = E(k₁, k_e) ∥ E(k₂, k_e) ∥ … ∥ E(k_l, k_e), and the body is the message encrypted under the session key.<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup><sup> • </sup><sup>[1](https://eprint.iacr.org/2024/154.pdf)</sup>\n\nThe covering principle explains how recipients and non-recipients are separated. In the subset-cover framework, Setup defines a collection of subsets of the user universe, each assigned a long-lived key that every member of the subset can deduce. Broadcast calls a Cover procedure to partition the privileged users into these subsets and emits one encrypted session-key copy per subset.<sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup><sup> • </sup><sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup> A recipient finds a subset containing itself, extracts the corresponding key, and decrypts the session key; a revoked user belongs to no subset in the cover, so the decryption step returns null.<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup> Colluding revoked users hold only keys of subsets that exclude them, so they cannot recover the session key.<sup>[8](https://kar.kent.ac.uk/93931/1/An_Analysis_of_the_NNL_SD_Algo.pdf)</sup>\n\nSecurity can be defined in two ways. If the subset keys are chosen randomly and independently, security is information-theoretic: given the keys of a coalition and the transmitted message, the conditional distribution of the secret is unchanged. If the keys are derived from secret information, security is computational.<sup>[5](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad.pdf)</sup><sup> • </sup><sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup> A hybrid argument bounds the adversary's success against the two-step structure by \\( 1/(N - r) \\) times the probability of breaking the underlying body-encryption function F.<sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup>\n\n## How it is done\n\nScheme performance is measured in three parameters: bandwidth (transmission overhead), space (per-user storage), and time (decryption computation).<sup>[2](https://per.austrin.se/papers/scbounds.pdf)</sup>\n\nAn early scheme of Fiat and Naor lets a center broadcast a secret to any privileged subset of a universe of n users so that coalitions of k excluded users cannot learn it. Their most interesting scheme requires every user to store \\( O(k \\log k \\log n) \\) keys and the center to broadcast \\( O(k^{2} \\log^{2} k \\log n) \\) messages regardless of the privileged set's size; a second scheme, resilient with probability p against a random coalition of k users, needs \\( O(\\log k \\log(1/p)) \\) keys per user and \\( O(k \\log^{2} k \\log(1/p)) \\) broadcast messages.<sup>[5](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad.pdf)</sup><sup> • </sup><sup>[9](https://dl.acm.org/doi/10.5555/646758.705697)</sup>\n\nThe subset-cover framework of Dalit Naor, Moni Naor, and Lotspiech reframed the goal around revoking stateless receivers, with users arranged as leaves of a complete binary tree. Its Complete Subtree (CS) instantiation uses complete subtrees as the special sets and needs less storage at the price of heavier bandwidth; the Subset Difference (SD) instantiation uses differences of subtrees.<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup><sup> • </sup><sup>[1](https://eprint.iacr.org/2024/154.pdf)</sup> CS revocation of r users costs a header of length \\( r \\log(N/r) \\) with \\( \\log N \\) stored keys; SD costs at most \\( 2r - 1 \\) header keys with storage on the order of \\( \\log^{2} N \\) and \\( O(\\log N) \\) processing plus a single decryption.<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup> The layered variant reduces storage to \\( O(\\log^{3/2} N) \\) with header length \\( 4r - 2 \\).<sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup> SD's bandwidth is \\( \\min(2r - 1,\\ n - r) \\), and later schemes improve the constant below 2.<sup>[2](https://per.austrin.se/papers/scbounds.pdf)</sup>\n\n## Origin\n\nThe subset-cover framework, together with its Complete Subtree and Subset Difference schemes, was presented in the paper \"Revocation and Tracing Schemes for Stateless Receivers\", published at CRYPTO 2001.<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup><sup> • </sup><sup>[8](https://kar.kent.ac.uk/93931/1/An_Analysis_of_the_NNL_SD_Algo.pdf)</sup> Boneh, Gentry, and Waters published the fully collusion resistant construction with constant-size ciphertexts and private keys in 2005.<sup>[4](https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf)</sup>\n\n## Variants\n\nThe Boneh, Gentry, and Waters 2005 construction changed the trade-off: using groups with an efficiently computable bilinear map, it achieves constant-size ciphertexts and private keys of two group elements for any subset of receivers, with public key size linear in the number of receivers; a second system achieves \\( O(\\sqrt{n}) \\) ciphertext and public key sizes for n users.<sup>[4](https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf)</sup> It was the first fully collusion-resistant scheme with short ciphertexts for all broadcast sets.<sup>[10](https://eprint.iacr.org/2025/323.pdf)</sup>\n\nIn distributed broadcast encryption, each user generates their own public and secret key pair, and encryption takes a collection of recipient public keys together with the message.<sup>[11](https://par.nsf.gov/servlets/purl/10618346)</sup> On the symmetric side, a 2024 scheme based on sum-product decomposition of Boolean functions achieves lower bandwidth than NNL-style schemes at the cost of increased key storage, and remains post-quantum because it uses only block ciphers and pseudorandom functions.<sup>[1](https://eprint.iacr.org/2024/154.pdf)</sup>\n\n## Applications\n\nThe Subset Difference method is the most popular broadcast encryption scheme and is suitable for real-time applications such as Pay-TV; it has been suggested for use by the AACS standard for digital rights management in Blu-ray and HD-DVD discs.<sup>[6](https://link.springer.com/article/10.1007/s10623-012-9702-6)</sup> AACS is the content protection system specified for protecting audiovisual content on pre-recorded BD-ROM (Blu-ray) discs.<sup>[12](https://aacsla.com/wp-content/uploads/2019/02/AACS_Spec_BD_Prerecorded_Final_0_953.pdf)</sup> Boneh, Gentry, and Waters name access control in encrypted file systems, satellite TV subscription services, and DVD content protection as applications.<sup>[4](https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf)</sup>\n\n## Limitations and alternatives\n\nCollusion resistance comes in grades. The NNL subset-cover schemes are resilient to any size coalition of revoked users, even all r of them, a property called r-flexible.<sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup> More generally, schemes are classed as robust (full collusion resilience) or k-collusion resistant (resisting only coalitions of up to k revoked users), and as static or dynamic depending on whether new users' credentials can be generated on the fly.<sup>[1](https://eprint.iacr.org/2024/154.pdf)</sup> For information-theoretically secure schemes, tight lower bounds exist on the number of private keys per user and the number of keys the center must generate.<sup>[13](https://link.springer.com/chapter/10.1007/BFb0053444)</sup>\n\nBroadcast encryption is often paired with traitor tracing, a complementary problem for digital media where a legitimate user cannot be prevented from disseminating content but cannot mask their identity.<sup>[1](https://eprint.iacr.org/2024/154.pdf)</sup> The NNL framework integrates a general tracing mechanism with any subset-cover revocation scheme satisfying a bifurcation property, without an a priori bound on the number of traitors, and reduces message length to \\( O(r) \\) regardless of coalition size while keeping a single decryption at the user's end.<sup>[3](https://iacr.org/archive/crypto2001/21390040.pdf)</sup> Compared with naive per-recipient encryption, which stores one key per user but has header length \\( O(N - r) \\), subset-cover schemes accept larger per-user storage for short headers.<sup>[7](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)</sup><sup> • </sup><sup>[2](https://per.austrin.se/papers/scbounds.pdf)</sup>\n\nA stated open problem is building a system with BGW's performance that is secure against adaptive adversaries; BGW's security is proven only against non-adaptive ones.<sup>[4](https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf)</sup>\n\n## References\n\n1. [Broadcast Encryption using Sum-Product decomposition of Boolean functions (ΣΠBE, IACR ePrint 2024/154)](https://eprint.iacr.org/2024/154.pdf)\n2. [Lower Bounds for Subset Cover Based Broadcast Encryption](https://per.austrin.se/papers/scbounds.pdf)\n3. [Revocation and Tracing Schemes for Stateless Receivers (Naor, Naor, Lotspiech, CRYPTO 2001; IACR archive copy, merging the author, ePrint 2001/059 and ECCC 2002/043 copies)](https://iacr.org/archive/crypto2001/21390040.pdf)\n4. [Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys (Boneh, Gentry, Waters; author-hosted copy, merging the ePrint 2005/018 copy)](https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf)\n5. [Broadcast Encryption (Fiat and Naor, full paper PDF)](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad.pdf)\n6. [Complete tree subset difference broadcast encryption scheme and its analysis (Designs, Codes and Cryptography)](https://link.springer.com/article/10.1007/s10623-012-9702-6)\n7. [A Survey of Broadcast Encryption (Horwitz)](http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf)\n8. [An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm](https://kar.kent.ac.uk/93931/1/An_Analysis_of_the_NNL_SD_Algo.pdf)\n9. [Broadcast Encryption, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO '93)](https://dl.acm.org/doi/10.5555/646758.705697)\n10. [A Generic Approach to Adaptively-Secure Broadcast Encryption in the Plain Model (IACR ePrint 2025/323)](https://eprint.iacr.org/2025/323.pdf)\n11. [Broadcast Encryption from Succinct LWE (NSF public access repository copy, Chen–Wee line of work, CW24)](https://par.nsf.gov/servlets/purl/10618346)\n12. [Advanced Access Content System (AACS) Specification for BD-ROM Pre-recorded, version 0.953](https://aacsla.com/wp-content/uploads/2019/02/AACS_Spec_BD_Prerecorded_Final_0_953.pdf)\n13. [Space requirements for broadcast encryption (Springer)](https://link.springer.com/chapter/10.1007/BFb0053444)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Networks and security › Network defense and threats*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026; Oct 21, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n",
 "same_as": [
  "https://crypto.stanford.edu/~dabo/pubs/papers/broadcast.pdf",
  "http://xenon.stanford.edu/~horwitz/pubs/broadcast.pdf"
 ],
 "url": "https://www.edgepedia.org/broadcast-encryption",
 "markdown_url": "https://www.edgepedia.org/broadcast-encryption.md",
 "license": {
  "name": "Edgepedia Community License 1.0",
  "url": "https://www.edgepedia.org/edgepedia/license",
  "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.",
  "spdx": "LicenseRef-Edgepedia-Community-1.0"
 },
 "credit": "\"Broadcast encryption\", Edgepedia (EdgeChat), https://www.edgepedia.org/broadcast-encryption. Edgepedia Community License 1.0.",
 "credit_md": "\"[Broadcast encryption](https://www.edgepedia.org/broadcast-encryption)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/broadcast-encryption](https://www.edgepedia.org/broadcast-encryption). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).",
 "credit_html": "\"<a href=\"https://www.edgepedia.org/broadcast-encryption\">Broadcast encryption</a>\", Edgepedia (EdgeChat), <a href=\"https://www.edgepedia.org/broadcast-encryption\">https://www.edgepedia.org/broadcast-encryption</a>. <a href=\"https://www.edgepedia.org/edgepedia/license\">Edgepedia Community License 1.0</a>.",
 "speakable": "Broadcast encryption is a cryptographic method that lets a sender encrypt a message so a chosen set of recipients can decrypt it while excluded users, even colluding, learn nothing."
}