Jump to content

Broadcast encryption

Edit links
From Wikipedia, the free encyclopedia

Broadcast encryption is the cryptographic problem of delivering encrypted content (e.g. TV programs or data on DVDs) over a broadcast channel in such a way that only qualified users (e.g. subscribers who have paid their fees or DVD players conforming to a specification) can decrypt the content.[1][2][3] The challenge arises from the requirement that the set of qualified users can change in each broadcast emission, and therefore revocation of individual users or user groups should be possible using broadcast transmissions, only, and without affecting any remaining users. As efficient revocation is the primary objective of broadcast encryption, solutions are also referred to as revocation schemes.[4][5][6]

Rather than directly encrypting the content for qualified users, broadcast encryption schemes distribute keying information that allows qualified users to reconstruct the content encryption key whereas revoked users find insufficient information to recover the key.[1] The typical setting considered is that of a unidirectional broadcaster and stateless users (i.e., users do not keep bookmarking of previous messages by the broadcaster), which is especially challenging.[4] In contrast, the scenario where users are supported with a bi-directional communication link with the broadcaster and thus can more easily maintain their state, and where users are not only dynamically revoked but also added (joined), is often referred to as multicast encryption.[7]

The problem of practical broadcast encryption has first been formally studied by Amos Fiat and Moni Naor in 1994.[1] Since then, several solutions have been described in the literature, including combinatorial constructions, one-time revocation schemes based on secret sharing techniques, and tree-based constructions.[2] In general, they offer various trade-offs between the increase in the size of the broadcast, the number of keys that each user needs to store, and the feasibility of an unqualified user or a collusion of unqualified users being able to decrypt the content. Luby and Staddon have used a combinatorial approach to study the trade-offs for some general classes of broadcast encryption algorithms.[3]

A particularly efficient tree-based construction is the "subset difference" scheme by Dalit Naor, Moni Naor and Jeff Lotspiech (NNL) which is derived from a class of so-called subset cover schemes.[4] The subset difference (SD) scheme in the NNL paper provides a particular trade-off point between the two key efficiency parameters -- the communication overhead required to "cover" the target subsets of privileged users, and the amount of key storage required. Sanjay Bhattacherjee and Palash Sarkar presented a generalisation of the NNL SD scheme[4] for an arbitrary number of users in place of a power of , along with its combinatorial analysis and a theoretical upper bound of for the average communication overhead when the number of revoked users is .[8] The NNL SD scheme has been further generalised using -ary trees in place of binary trees.[9] For a total of users in the system, Dani Halevy and Adi Shamir (HS) introduced a method to lower user storage of NNL SD[4] from O(log2 n) to O(log3/2 n) at the cost of doubling the communication overhead.[10] The HS framework was later formalised as an optimisation problem to minimise user storage using dynamic programming.[11] The other trade-off direction which lowers the communication overhead below that of the NNL SD scheme at the cost of increasing user storage has also been explored.[12] The subset difference scheme is notably implemented in the AACS for HD DVD and Blu-ray Disc encryption. A rather simple broadcast encryption scheme is used for the CSS for DVD encryption.

The problem of rogue users sharing their decryption keys or the decrypted content with unqualified users is mathematically insoluble. Traitor tracing algorithms aim to minimize the damage by retroactively identifying the user or users who leaked their keys, so that punitive measures, legal or otherwise, may be undertaken.[13][4] In practice, pay TV systems often employ set-top boxes with tamper-resistant smart cards that impose physical restraints on a user learning their own decryption keys. Some broadcast encryption schemes, such as AACS, also provide tracing capabilities.[14]

See also

[edit]

References

[edit]
  1. ^ a b c Amos Fiat; Moni Naor (1994). Stinson, Douglas R. (ed.). "Broadcast Encryption". Advances in Cryptology — CRYPTO' 93 (Extended abstract). Lecture Notes in Computer Science. 773: 480–491. doi:10.1007/3-540-48329-2_40. ISBN 978-3-540-57766-9.
  2. ^ a b Noam Kogan; Yuval Shavitt; Avishai Wool (May 2003). A Practical Revocation Scheme for Broadcast Encryption Using Smart Cards. 24th IEEE Symposium on Security & Privacy (Extended abstract).
  3. ^ a b Michael Luby; Jessica Staddon (1998). Nyberg, K. (ed.). "Combinatorial bounds for broadcast encryption". Advances in Cryptology — EUROCRYPT'98. Lecture Notes in Computer Science. 1403: 512–526. doi:10.1007/BFb0054150. ISBN 978-3-540-64518-4.
  4. ^ a b c d e f Dalit Naor; Moni Naor; Jeff Lotspiech (2001). "Revocation and Tracing Schemes for Stateless Receivers". Proc. Advances in Cryptology – CRYPTO '01. Lecture Notes in Computer Science. Vol. 2139. pp. 41–62. doi:10.1007/3-540-44647-8_3. ISBN 3-540-42456-3.
  5. ^ Scott C.-H. Huang; Ding-Zhu Du (March 2005). "New constructions on broadcast encryption and key pre-distribution schemes". Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proc. IEEE Computer and Communications Societies – INFOCOM 2005. Vol. 1. pp. 515–523. CiteSeerX 10.1.1.401.9780. doi:10.1109/INFCOM.2005.1497919. ISBN 978-0-7803-8968-7. S2CID 17709190.
  6. ^ Noam Kogan; Tamir Tassa (2006). Improved Efficiency for Revocation Schemes via Newton Interpolation (PDF). ACM Transactions on Information and System Security. Vol. 9. pp. 461–486.
  7. ^ Ran Canetti; Tal Malkin; Kobbi Nissim (1999). "Efficient communication-storage tradeoffs for multicast encryption". Proc. Theory and application of cryptographic techniques – EUROCRYPT '99. Lecture Notes in Computer Science. Vol. 1592. pp. 459–474. ISBN 3-540-65889-0.
  8. ^ Bhattacherjee, Sanjay; Sarkar, Palash (14 May 2012). "Complete tree subset difference broadcast encryption scheme and its analysis". Designs, Codes and Cryptography. 66. Springer: 335–362. doi:10.1007/s10623-012-9702-6.
  9. ^ Bhattacherjee, Sanjay; Sarkar, Palash (27 May 2015). "Tree based symmetric key broadcast encryption". Journal of Discrete Algorithms. 34. Elsevier: 78–107. doi:10.1016/j.jda.2015.05.010.
  10. ^ Halevy, Dani; Shamir, Adi. "The LSD Broadcast Encryption Scheme". Advances in Cryptology -- CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. doi:10.1007/3-540-45708-9_4.
  11. ^ Bhattacherjee, Sanjay; Sarkar, Palash (21 March 2013). "Concrete Analysis and Trade-Offs for the (Complete Tree) Layered Subset Difference Broadcast Encryption Scheme". IEEE Transactions on Computers. 63 (7). IEEE: 1709–1722. doi:10.1109/TC.2013.68.
  12. ^ Bhattacherjee, Sanjay; Sarkar, Palash. "Reducing Communication Overhead of the Subset Difference Scheme". IEEE Transactions on Computers. 65 (8). IEEE: 2575–2587. doi:10.1109/TC.2015.2485231.
  13. ^ Benny Chor; Amos Fiat; Moni Naor (1994). "Tracing traitors". Proc. Advances in Cryptology – CRYPTO '94. Lecture Notes in Computer Science. Vol. 839. pp. 257–270. ISBN 978-3-540-58333-2.
  14. ^ ""AACS Specifications: Introduction and Common Cryptographic Elements Book"" (PDF). Archived from the original (PDF) on 2010-08-27. Retrieved 2010-10-14.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Broadcast_encryption&oldid=1285404818"