Broadcast encryption

• US 5,592,552 A
• Filed: 09/24/1994
• Issued: 01/07/1997
• Est. Priority Date: 08/25/1993
• Status: Expired due to Fees

• Current Assignee: Algorithmic Research Limited
• Original Assignee: Algorithmic Research Limited
• Inventors: Fiat, Amos
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/295,207
• Time in Patent Office: 836 Days
• Field of Search: 380/21, 380/20, 380/23, 380/10
• US Class Current: 713/163
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/065 for group communications cryptographic mechanisms or cryptographic arrangements for key management involving conference or group key H04L9/0833
• CPC Class Codes: H04L 63/104 Grouping of entities
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure

Abstract

A selective broadcasting method operative to transmit a plurality of message data signals to a corresponding plurality of subscriber subsets within a set of subscribers, the method comprising receiving an indication of a privileged set comprising an individual subset and transmitting a message data signal from which a key can be extracted by members of the privileged set and cannot be extracted by any set of members outside the privileged set whose number of members is less than a predetermined resiliency, wherein the length of the message data signal is less than the sum of lengths of the message data signals required if an individual message data signal is transmitted to each subscriber in the privileged set.

Claims

1. A selective broadcasting method operative to transmit a plurality of message data signals to a corresponding plurality of subscriber subsets within a set of subscribers, the method comprising:

receiving an indication of a privileged set comprising an individual subset; and

transmitting a message data signal from which a key can be extracted by members of the privileged set and cannot be extracted by any set of members outside the privileged set whose number of members is less than a predetermined resiliency,

wherein the length of the message data signal is less than the sum of lengths of the message data signals required if an individual message data signal is transmitted to each subscriber in the privileged set.

12. A method according to claim 1 and also comprising splitting the subscriber population into a plurality of subscriber subpopulations and performing the above methods separately for each subpopulation.

13. A method according to claim 12 wherein each subpopulation comprises approximately 1000 subscribers.

14. A method according to claim 12 wherein each subpopulation comprises 63 subscribers.

15. A method according to claim 12 wherein there are approximately 100,000 subpopulations.

2. A selective broadcasting method operative to transmit a plurality of message data signals to a corresponding plurality of subsets within a set of subscribers, the method comprising:

receiving an indication of a privileged set comprising an individual subset;

providing each subscriber with confidential information to be stored which requires a certain memory size;

transmitting a message data signal from which a key can be extracted by members of the privileged set and cannot be extracted by any set of members outside the privileged set whose number of members is less than a predetermined resiliency,

wherein at least one of the total subscriber memory size, for a privileged set of m subscribers, and the message data signal length are less than the subscriber memory size and message data signal length, respectively, required when 2^l keys are provided to each subscriber, where l is an integer, and m/l message data signals are used to transmit a common key to a privileged set having m members.

3. A selective broadcasting method for broadcasting to a privileged set of subscribers from among a population of n subscribers, the method comprising:

providing a set of keys respectively corresponding to the set of all possible subscriber subsets within the subscriber population with less than a predetermined number k of members, wherein for each subset, the key corresponding thereto is provided only to those subscribers not belonging to the subset;

providing a message data signal and selecting from among the subscriber population a privileged set of subscribers which is to exclusively receive the message data signal, and transmitting information identifying the privileged set;

encrypting the message data signal using a key comprising the bitwise XOR of all keys corresponding to subsets which are disjoint to the privileged set; and

broadcasting a data signal comprising the encrypted message.

4. A method according to claim 3 wherein said key providing process comprises:

computing an n-leaf balanced binary tree characterized in that its root is labelled with a common seed and, for each vertex of the tree, the label of the root. of its right subtree is the left half of the result of applying a pseudo random function to the vertex label and the label of the root of its left subtree is the right half of the result of applying a pseudo random function to the vertex label; and

providing each subscriber with the label of the root of each tree in a forest of trees resulting from removal from the balanced binary tree of a path extending from a leaf associated with the subscriber to the root.

7. A selective broadcasting method for broadcasting to a privileged set of subscribers from among a population U of n subscribers, the method comprising:

defining a plurality of l partitions of the population of subscribers, each partition comprising m subscriber sets;

for each partition and for each subscriber set within the partition, providing a unique scheme based on the method of claim 3 which is one-resilient within said set and distributing keys to the subscribers in said subscriber set as indicated by the unique scheme;

providing a value M_i for each partition i (i=1, . . . , l), at least some of which values are random;

for each partition i and for each set j (j=1, . . . , m) within partition i, transmitting M_i to all privileged subscribers in set j using the scheme of set j under partition i; and

transmitting a message data signal in encrypted form using a key which is the bitwise XOR of the M_i '"'"'s.

8. A selective broadcasting method for broadcasting to a privileged set of subscribers from among a population U of n subscribers, the method comprising:

defining a plurality of l partitions of the population of subscribers, each partition comprising m subscriber sets;

for each partition and for each subscriber set within the partition, providing a unique scheme based on the method of claim 4 which is one-resilient within said set and distributing keys to the subscribers in said subscriber set as indicated by the unique scheme;

providing a value M_i for each partition i (i=1, . . . , l), at least some of which values are random;

for each partition i and for each set j (j=1, . . . , m) within partition i, transmitting M_i to all privileged subscribers in set j using the scheme of set j under partition i; and

transmitting a message data signal in encrypted form using a key which is the bitwise XOR of the M_i '"'"'s.

5. A selective broadcasting method for broadcasting to a privileged set of subscribers from among a population of subscribers, the method comprising:

providing each subscriber i with a key g to the power of p_i where g is a high index value unknown to the subscribers and wherein the p_i values are selected such that, for any two subscribers i and j, p_i and p_j are relatively prime;

providing a message data signal and selecting from among the subscriber population a privileged set of subscribers which is to exclusively receive the message data signal, and transmitting information identifying the privileged set;

encrypting the message data signal using a key which is the modulo N value of g to the power of the product of the p_i values of all subscribers i belonging to the privileged set, where N is a random hard to factor prime composite which is known to the subscribers; and

broadcasting a data signal comprising the encrypted message.

9. A selective broadcasting method for broadcasting to a privileged set of subscribers from among a population U of n subscribers, the method comprising:

defining a plurality of l partitions of the population of subscribers, each partition comprising m subscriber sets;

for each partition and for each subscriber set within the partition, providing a unique scheme based on the method of claim 5 which is one-resilient within said set and distributing keys to the subscribers in said subscriber set as indicated by the unique scheme;

providing a value M_i for each partition i (i=1, . . . , l), at least some of which values are random;

for each partition i and for each set j (j=1, . . . , m) within partition i, transmitting M_i to all privileged subscribers in set j using the scheme of set j under partition i; and

transmitting a message data signal in encrypted form using a key which is the bitwise XOR of the M_i '"'"'s.

6. A selective broadcasting method for broadcasting to a privileged set of subscribers from among a population U of n subscribers, the method comprising:

defining a plurality of 1 partitions of the population of subscribers, each partition comprising m subscriber sets;

for each partition and for each subscriber set within the partition, providing a unique scheme which is one-resilient within said set and distributing keys to the subscribers in said subscriber set as indicated by the unique scheme;

providing a value M_i for each partition i (i=1, . . . , l), at least some of which values are random;

for each partition i and for each set j (j=1, . . . , m) within partition i, transmitting M_i to all privileged subscribers in set j using the scheme of set j under partition i; and

transmitting a message data signal in encrypted form using a key which is the bitwise XOR of the M_i '"'"'s.

10. A method according to claim 6 wherein l, the number of partitions, and m, the number of sets per partition, are selected as follows:

m is at least k² where k is a predetermined resiliency value with probability p for a random set of k members;

l is at least log (1/p).

11. A method according to claim 6 wherein l, the number of partitions, and m, the number of sets per partition, are selected as follows:

m is at least 2 k² where k is a predetermined resiliency value

l is at least k log n.

16. A selective broadcasting system operative to transmit a plurality of message data signals to a corresponding plurality of subscriber subsets within a set of subscribers, the system comprising:

encrypting and broadcasting equipment operative to transmit a message data signal from which a key can be extracted by members of a privileged set and cannot be extracted by any set of members outside the privileged set whose number of members is less than a predetermined resiliency,

wherein the length of the message data signal is less than the sum of lengths of the message data signals required if an individual message data signal is transmitted to each subscriber in the privileged set.

17. A selective broadcasting system operative to transmit a plurality of message data signals to a corresponding plurality of subsets within a set of subscribers, the system comprising:

a subscriber memory loaded with confidential information occupying a certain memory size;

broadcasting equipment operative to transmit a message data signal from which a key can be extracted by members of a privileged set and cannot be extracted by any set of members outside the privileged set whose number of members is less than a predetermined resiliency,

wherein at least one of the total occupied subscriber memory size, for a privileged set of m subscribers, and the message data signal length are less than the subscriber memory size and message data signal length, respectively, required when 2^l keys are provided to each subscriber, where l is an integer, and m/l message data signals are used to transmit a common key to a privileged set having m members.

18. A selective broadcasting system for broadcasting to a privileged set of subscribers from among a population of n subscribers, the system comprising:

n subscriber memories storing a set of keys respectively corresponding to the set of all possible subscriber subsets within the subscriber population with less than a predetermined number k of members, wherein for each subset, the key corresponding thereto is stored only by those subscribers not belonging to the subset;

an encryptor operative to encrypt a message data signal intended for a privileged set using a key comprising the bitwise XOR of all keys corresponding to subsets which are disjoint to the privileged set; and

broadcasting equipment operative to broadcast information identifying the privileged set and a data signal comprising the encrypted message.

19. A selective broadcasting system for broadcasting to a privileged set of subscribers from among a population of subscribers, the system comprising:

a plurality of subscriber memories associated respectively with the subscribers, wherein the i'"'"'th subscriber memory associated with subscriber i stores a key g to the power of p_i where g is a high index value unknown to the subscribers and wherein the p_i values are selected such that, for any two subscribers i and j, p_i and p_j are relatively prime;

encrypting a message data signal intended for a privileged set of subscribers using a key which is the modulo N value of g to the power of the product of the p_i values of all subscribers i belonging to the privileged set, where N is a random hard to factor prime composite which is known to the subscribers; and

broadcasting equipment operative to broadcast information identifying the privileged set and a data signal comprising the encrypted message.

20. A selective broadcasting system for broadcasting to a privileged set of subscribers from among a population U of n subscribers, the system comprising:

n subscriber memories associated with the n subscribers respectively, wherein for each of a plurality of l partitions of the population of subscribers, each partition comprising m subscriber sets and for each subscriber set within the partition, keys distributed according to a unique scheme which is one-resilient within said set are stored in the memories of all subscribers in said subscriber set,

broadcasting apparatus operative, for each partition i and for each set j (j=1, . . . , m) within partition i, to transmit an M_i signal to all privileged subscribers in set j using the scheme of set j under partition i, wherein at least some of the M_i signals are random, the broadcasting apparatus also being operative to transmit a message data signal in encrypted form using a key which is the bitwise XOR of the M_i '"'"'s.