Method and apparatus for conveying a private message to selected members

• US 6,782,475 B1
• Filed: 07/13/2000
• Issued: 08/24/2004
• Est. Priority Date: 01/15/1999
• Status: Expired due to Fees

• Current Assignee: Terence E. Sumner
• Original Assignee: Terence E. Sumner
• Inventors: Sumner, Terence E.
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): Zand, Kambiz
• Application Number:
  US09/600,421
• Time in Patent Office: 1,503 Days
• Field of Search: 713/163, 713/201, 380/255-257, 380/270, 380/33, 709/201, 709/107, 709/220, 709/223, 709/225, 709/227, 709/237
• US Class Current: 713/163
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• 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 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

An encrypted broadcast messaging system determines the management crypto-keys held by each selected subscriber device and not held by each excluded subscriber device of a group. The private message is decomposed into message-parts, one message-part per an excluded subscriber device, each message-part intended to be encrypted using each management crypto-key held by the selected subscriber devices and not held by the excluded subscriber device. Each message-part is encrypted using the intended management crypto-keys, and delivered to at least the selected subscriber devices, identifying the message-parts delivered and the message-parts necessary to re-compose the private message. Each received encrypted message-part is decrypted using the intended management crypto-key, and the necessary message-parts are chosen from which the private message is re-composed by combining in the selected subscriber devices.

Claims

1. A method of securely broadcasting a message from a message source over an insecure communication channel to included communicants but not to excluded communicants, comprising:

(a) providing a set of private security devices;

(b) providing a subset of said private security devices to each communicant;

(c) wherein each communicant has a unique subset of said private security devices taken from said set of private security devices, as compared to all other communicants;

(d) identifying said included communicants and said excluded communicants and associated private security devices;

(e) selecting particular ones of said private security devices from said set of private security devices through a combination of;

(1) analysis of private security device allocation among said included communicants and excluded communicants; and

(2) potential decomposition of said message into message portions;

(f) decomposing said message into message portion, with the amount of decomposition being related to the number of excluded communicants;

(g) utilizing said particular ones of said private security devices which are unavailable to said excluded communicants to secure said particular message portions of said message;

(h) communicating a secure form of said message over said insecure communication channel; and

(i) wherein said included communicants may utilize said particular ones of said private security devices to produce said message from said secure form of said message, but wherein said excluded communicants lack the necessary ones of said private security devices to produce said message from said secure form of said message and thereby are excluded from the broadcast.

2. A method of securely broadcasting according to claim 1, wherein said security devices comprise at least one of:

(1) a cryptographic communication key;

(2) a protocol;

(3) an algorithm;

(4) a mathematical function;

(5) a method of processing;

(6) a software security device;

(7) a hardware security device;

(8) a hash function;

(9) a serial number;

(10) a clock value;

(11) an initial value;

(12) a random variable;

(13) an initialization vector; and

(14) a value determined by a cyclic process.

3. A method of securely broadcasting according to claim 1, wherein said private security devices comprise cryptographic security devices including at least one of:

(1) cryptographic algorithms; and

(2) cryptographic keys.

4. A method of securely broadcasting according to claim 3, wherein said cryptographic security devices comprise asymmetric cryptographic security devices.

5. A method of securely broadcasting according to claim 3, wherein said cryptographic security devices comprise symmetric cryptographic security devices.

6. A method of securely broadcasting according to claim 1, wherein:

(1) said set of private security devices comprise at least four private security devices; and

(2) each subset of said private security devices comprise at least two private security devices.

7. A method of securely broadcasting according to claim 1, wherein each of said private security devices has an initial state which is altered after receipt of said message.

8. A method of securely broadcasting according to claim 1, wherein said security devices comprise private cryptographic communication keys.

9. A method of securely broadcasting according to claim 8, wherein said private cryptographic communication keys comprise symmetric private cryptographic communication keys.

10. A method of securely broadcasting according to claim 1:

(i) wherein said set of private security devices comprise a set of private cryptographic communication keys; and

(j) wherein said message is segmented into message part; and

(k) wherein each message part is encrypted utilizing particular ones of said set of private cryptographic communication keys.

11. A method of securely broadcasting according to claim 10, wherein said set of private cryptographic communication keys comprise at least four private cryptographic communication keys.

12. A method of securely broadcasting according to claim 10, wherein particular ones of said private cryptographic communication keys are selected through a combination of:

(1) analysis of key allocation among said included communicants and excluded communicants; and

(2) potential segmentation of said message.

13. A method of securely broadcasting according to claim 1, wherein said subset of said private security devices are provided to each communicant substantially according to n-select-n/2.

14. A method of securely broadcasting according to claim 1:

wherein said private security devices comprise data representing security keys; and

wherein said subset of said security keys are provided to each communicant substantially according to n-select-n/2.

15. A method of securely broadcasting according to claim 1, wherein said step of decomposing said message into message portions is accomplished by applying an invertible mathematical function to said message which produces a substantially unpredictable output.

16. A method of securely broadcasting according to claim 1, wherein said step of decomposing said message into message portions is accomplished by performing a bit-by-bit exclusive-OR operation on said message and substantially random bits of equal or greater length.

17. A method of securely broadcasting a message from a message source over an insecure communication channel to included communicants but not to excluded communicants, comprising:

(a) providing a set of private cryptographic communication keys;

(b) providing a subset of said private cryptographic communication keys to each communicant;

(c) wherein each communicant has a unique subset of said private cryptographic communication keys taken from said set of private cryptographic communication keys, as compared to all other communicants;

(d) identifying said included communicants and said excluded communicants and associated private cryptographic communication keys;

(e) selecting particular ones of said private cryptographic communication keys from said set of private cryptographic communication keys through a combination of;

(1) analysis of private cryptographic communication key allocation among said included communicants and excluded communicants; and

(2) analysis of potential decomposition of said message;

(f) decomposing said message into message parts, with the amount of decomposition being related to the number of excluded communicants;

(g) utilizing said particular ones of said private cryptographic communication keys which are unavailable to said excluded communicants to encrypt particular portions of said message;

(h) communicating an encrypted form of said message over said insecure communication channel;

(i) wherein included communicants may utilize said particular ones of said private cryptographic communication keys to decrypt said message, but wherein said excluded communicants lack the necessary ones of said private cryptographic communication keys to decrypt said message and are thus excluded from the broadcast.

18. A method of securely broadcasting according to claim 17, wherein said private cryptographic command keys comprise asymmetric cryptographic communication keys.

19. A method of securely broadcasting according to claim 17, wherein said private cryptographic command keys comprise symmetric cryptographic communication keys.

20. A method of securely broadcasting according to claim 17, wherein:

(1) said set of private cryptographic communication keys comprise at least four private cryptographic communication keys; and

(2) each subset of said private cryptographic communication keys comprise at least two private cryptographic communication keys.

21. A method of securely broadcasting according to claim 17, wherein said step of decomposing said message into message portions is accomplished by applying an invertible mathematical function to said message which produces a substantially unpredictable output.

22. A method of securely broadcasting according to claim 17, wherein said step of decomposing said message into message portions is accomplished by performing a bit-by-bit exclusive-OR operation on said message and substantially random bits of equal or greater length.

23. A method in a encrypted broadcast messaging system for conveying a private message to selected subscriber devices of a group while excluding other subscriber devices in the group, the method comprising the steps of:

(a) pre-programming from a first set of management security devices a second set of management security devices into each subscriber device of the group, with each second set being unique from all other second sets;

(b) determining the management security devices held by the selected subscriber devices and the management security devices held by subscriber devices excluded from the group;

(c) decomposing the private message into message parts, at least one message part for, and associated to, each excluded subscriber device of the group, each message part intended to be secured using management security devices not held by the excluded subscriber devices;

(d) securing a copy of each of the message parts, one copy for each of a management security devices held by the selected subscriber devices and not any held by the associated excluded device, using the management security devices intended for each message part;

(e) delivering the secured message parts to at least the selected subscriber devices in the group, identifying the message parts delivered and the message parts needed to re-compose the private message;

(f) receiving at least one secured message part, identifying the at least one message part received and the at least one message part needed to re-compose the private message;

(g) reconstructing the at least one received encrypted message part using a management security device;

(h) choosing from the secured received message parts at least one message part sufficient to re-compose the private message; and

(i) re-composing the private message by combining the chosen message parts.

24. A method according to claim 23, wherein said management security devices comprise at least one of:

(1) a cryptographic communication key;

(2) a protocol;

(3) an algorithm;

(4) a mathematical function;

(5) a method of processing;

(6) a software security device;

(7) a hardware security device;

(8) a hash function;

(9) a serial number;

(10) a clock value;

(11) an initial value;

(12) a random variable;

(13) an initialization vector; and

(14) a value determined by a cyclic process.

25. A method according to claim 23, wherein said management security devices comprise cryptographic security devices including at least one of:

(1) cryptographic algorithms; and

(2) cryptographic keys.

26. A method of securely broadcasting according to claim 25, wherein said cryptographic security devices comprise asymmetric cryptographic security devices.

27. A method of securely broadcasting according to claim 25, wherein said cryptographic security devices comprise symmetric cryptographic security devices.

28. A method of securely broadcasting according to claim 23, wherein:

(1) said set of management security devices comprise at least four management security devices; and

(2) each subset of said management security devices comprise at least two management security devices.

29. A method of securely broadcasting according to claim 23, wherein said management security devices comprise private cryptographic communication keys.

30. A method of securely broadcasting according to claim 29, wherein said private cryptographic communication keys comprise symmetric private cryptographic communication keys.

31. A method of securely broadcasting according to claim 23:

(i) wherein said set of management security devices comprise a set of management cryptographic communication keys; and

(j) wherein said message is segmented into message part; and

(k) wherein each message part is encrypted utilizing particular ones of said set of management cryptographic communication keys.

32. A method of securely broadcasting according to claim 31, wherein said set of management cryptographic communication keys comprise at least four private cryptographic communication keys.

33. A method of securely broadcasting according to claim 31, wherein particular ones of said private cryptographic communication keys are selected through a combination of:

(1) analysis of key allocation among said included subscribers and excluded subscribers; and

(2) potential segmentation of said message.

34. A method of securely broadcasting according to claim 23, wherein said subset of said management security devices are provided to each subscriber substantially according to n-select-n/2.

35. A method of securely broadcasting according to claim 23:

wherein said management security devices comprise data representing security keys; and

wherein said subset of said security keys are provided to each subscriber substantially according to n-select-n/2.

36. A method of securely broadcasting according to claim 23, wherein said step of decomposing said message into message portions is accomplished by applying an invertible mathematical function to said message which produces a substantially unpredictable output.

37. A method of securely broadcasting according to claim 23, wherein said step of decomposing said message into message portions is accomplished by performing a bit-by-bit exclusive-OR operation on said message and substantially random bits of equal or greater length.

38. A method in a encrypted broadcast messaging system for delivering a private message to selected subscriber devices of a group while excluding other subscriber devices in the group, the method comprising the steps of:

(a) determining the management crypto-keys held by the selected subscriber devices and the management crypto-keys held by subscriber devices excluded from the group;

(b) decomposing the private message into a message-part, at least one message-part for and associated to each excluded subscriber device of the group;

(c) copying the message-parts, one copy for each of a management crypto-key held by the selected subscriber devices and not any held by the associated excluded device, each message-part intended to be encrypted using the held management crypto-keys;

(d) encrypting each of the message-parts using the management crypto-keys intended for each message-part; and

(e) delivering the encrypted message-parts to at least the selected subscriber devices in the group, identifying the message-parts delivered and the message-parts needed to re-compose the private message.

39. The method in claim 38, wherein the copying step further includes a pre-combining step and a supplying step, to pre-combine all message-part copies to be encrypted using a particular management crypto-key into a first resultant message-part, the combining equivalent to that in a subscriber device and identifying the message-parts constituting the resultant, and to supply second resultant message-parts sufficient for all selected subscriber devices to re-compose the private message from delivered resultant message-parts.

40. A method in a encrypted broadcast messaging system for obtaining a private message by selected subscriber devices of a group excluding other subscriber devices in the group, the method comprising the steps of:

(a) pre-programming from a first set of at least two management crypto-keys a second set of management crypto-keys into each subscriber device of the group, each second set being unique from all other second sets;

(b) receiving at least one encrypted message-part, identifying the at least one message-part received and the at least one message-part needed to re-compose the private message;

(c) decrypting the at least one received encrypted message-part using a management crypto-key;

(d) choosing from the decrypted received message-parts at least one message-part sufficient to re-compose the private message; and

(e) re-composing the private message by combining the chosen message-parts and passing it to a destination.

41. A subscriber device comprising:

(a) a receiving interface for receiving secure message parts;

(b) a processing system coupled to the receiving interface for processing the received secure message parts;

(c) wherein the processing system is programmed to produce the message parts from the received secure message parts using preprogrammed security devices from a set of available security devices;

(d) wherein said preprogrammed security devices associated with said receiving interface are unique from all others;

(e) wherein the processing system is programmed to choose from the message parts at least one message part sufficient to re-compose a private message;

(f) and wherein the processing system is programmed to re-compose the private message by combining the chosen decrypted message parts; and

(g) an output interface coupled to the processing system for presenting the private message to its destination.

42. A subscriber device according to claim 41, wherein said security devices comprise at least one of:

(1) a cryptographic communication key;

(2) a protocol;

(3) an algorithm;

(4) a mathematical function;

(5) a method of processing;

(6) a software security device;

(7) a hardware security device;

(8) a hash function;

(9) a serial number;

(10) a clock value;

(11) an initial value;

(12) a random variable;

(13) an initialization vector; and

(14) a value determined by a cyclic process.

43. A subscriber device according to claim 41, wherein said private security devices comprise cryptographic security devices including at least one of:

(1) cryptographic algorithms; and

(2) cryptographic keys.

44. A subscriber device according to claim 43, wherein said cryptographic security devices comprise asymmetric cryptographic security devices.

45. A subscriber device according to claim 43, wherein said cryptographic security devices comprise symmetric cryptographic security devices.

46. A subscriber device according to claim 41, wherein:

(1) said set of available security devices comprise at least four private security devices; and

(2) each subset of said preprogrammed private security devices comprise at least two private security devices.

47. A subscriber device according to claim 41, wherein said subset of said private security devices are provided to each subscriber substantially according to n-select-n/2.

48. A subscriber device according to claim 41:

wherein said private security devices comprise data representing security keys; and

wherein a subset of said security keys are provided to each subscriber substantially according to n-select-n/2.

49. A subscriber device according to claim 41, wherein said message is decomposed into message portions by applying an invertible mathematical function to said message which produces a substantially unpredictable output.

50. A subscriber device according to claim 41, wherein said message is decomposed into message portions by performing a bit-by-bit exclusive-OR operation on said message and substantially random bits of equal or greater length.

51. A group manager comprising:

(a) a source interface for receiving private messages and list of selected subscriber devices to receive the private message;

(b) a processing system coupled to the source interface for processing the received list of selected subscriber devices and excluded subscriber devices plus their associated keys into key-sets and for processing the private message into message-parts;

(c) wherein the processing system is programmed to determine the management crypto-keys held by the selected subscriber devices and the management crypto-keys held by the excluded subscriber devices;

(d) wherein the processing system is programmed to decompose the private message into a message-parts, all of which are required to recompose the private message, at least one message-part for and associated to each excluded subscriber device that has a management key in common with an included subscriber device, wherein the processing system is programmed to copy the message-parts, one copy for each of a management crypto-key held by the selected subscriber devices and not held by the associated excluded device, each message-part intended to be encrypted using the held management crypto-keys, and wherein the processing system is programmed to encrypt each of the message-parts using the management crypto-keys intended for each message-part, and deliver the encrypted message-parts to at least the selected subscriber devices in the group, in a form usable by the included subscriber devices to recompose the private message; and

(e) a distribution interface coupled to the processing system for presenting the encrypted message-part messages to a broadcast network.

52. A group manager according to claim 51, wherein the number of message-parts necessary to securely broadcast is reduced by pre-combing message parts prior to transmission.