Key Distribution in Systems for Selective Access to Information

• US 20080101611A1
• Filed: 11/16/2004
• Published: 05/01/2008
• Est. Priority Date: 11/16/2004
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Lindholm, Fredrik, Kreitz, Gunnar
• Granted Patent: US 7,949,135 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• 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/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

A combination of stateless and state-full techniques enable reduced overall key management messages. A set of encryption keys is created based on a stateless subset cover scheme, where each user is associated with a leaf in the subset cover scheme. A state key and a corresponding state representing a subset of users that have the state key and a subset of users that do not have the state key is established, and a subset cover based on information representative of the established state is determined. Finally, a group key management message can be determined at least partly based on the calculated subset cover. The introduced state opens up for efficient subset cover calculation, reducing the size of the key management message.

Claims

1. A method for improved key distribution in a system for selective access to services, wherein a group key management message, including a service access key, is transferred to a group of users for access to a selected service, said method comprising:

creating a set of encryption keys based on a stateless subset cover scheme, each user being associated with a leaf in said subset cover scheme;

establishing a state key and a corresponding state representing a subset of users that have the state key and a subset of users that do not have the state key;

determining a subset cover based on information representative of the established state; and

determining said group key management message at least partly based on the determined subset cover.

2. The method of claim 1, wherein said step of determining a group key management message comprises the step of determining a first message part extractable by a sub-group of users which have the state key.

3. The method of claim 2, wherein the sub-group of users that have the state key comprises users that have the state key and shall remain active.

4. The method of claim 2, further comprising the steps of:

protecting an information protection key at least partly based on the state key; and

incorporating said protected information protection key into said group key management message.

5. The method of claim 4, wherein said step of protecting an information protection key is based on the state key as well as an additional key, wherein said additional key is protected based on encryption keys of a subset cover of users which shall remain active and incorporated in protected form into said first part of said group key management message.

6. The method of claim 5, wherein said group key management message M is determined according to:

M={T, S_rs, E(H_Srs, K_P) . . . S_tu, E(H_Stu, K_P), E(K_E, K_M)}, K_E=F(K_P, K_state)

where T is a state identifier, K_state is the current state key, S_rs, . . . , S_tu are user sets covering users that shall remain active among those users which have the state key, E is an encryption function, H_Srs, . . . H_Stu. are encryption keys of the stateless subset cover scheme corresponding to said user sets, K_P is said additional key, K_E is an envelope key calculated as a function F of said additional key and the state key, and K_M is the information protection key.

7. The method of claim 4, wherein said information protection key as well as a new state key are protected at least partly based on the current state key, and said protected new state key is also incorporated into said group key management message.

8. The method of claim 2, wherein said step of determining a group key management message further comprises the step of determining a second message part extractable by a sub-group of users which do not have the state key.

9. The method of claim 8, wherein the sub-group of users that do not have the state key comprises users to be joined as active users.

10. The method of claim 8, wherein said state key and a media protection key are protected based on encryption keys of a subset cover of users to be joined as active users and incorporated in protected form into said second part of said group key management message.

11. The method of claim 1, wherein said step of determining a subset cover comprises the steps of:

marking users based on said state information, and

computing said subset cover based on said user markings.

12. The method of claim 11, wherein said step of marking users based on said state information comprises the step of marking users without the state key as active users, and said computing step involves using a general subset cover calculation procedure.

13. The method of claim 11, wherein said step of marking users based on said state information is performed based on a categorization of users into three types:

users that have the state key but shall be revoked;

users that have the state key and shall remain active; and

users without the state key.

14. The method of claim 13, wherein said step of marking users based on said state information comprises the steps of:

initially marking users without the state key as undefined users;

marking each user with the state key as one of;

a user that shall remain active, referred to as a member, and a user that shall be revoked, referred to as not a member; and

remarking each undefined user as one of;

a member and not a member, depending on the previous marking of users with the state key.

15. The method of claim 11, wherein said step of marking users based on said state information and said step of computing said subset cover based on said user markings are performed simultaneously in an integrated manner.

16. The method of claim 15, wherein said integrated marking and computing steps are performed based on a categorization of users into three types:

users that have the state key but shall be revoked;

users that have the state key and shall remain active; and

users without the state key.

17. The method of claim 16, wherein colors are assigned to users depending on said categorization, and said integrated marking and computing steps are performed according to a coloring algorithm.

18. The method of claim 1 wherein the group key management message includes a plurality of keys for access to a plurality of services, wherein:

said step of establishing further comprises establishing, for each of the plurality of services, a service state key and corresponding state representing a subset of users that have the service state key and a subset of users that do not have the service state key;

said step of determining a subset cover further comprises determining, for each of the plurality of services, a service subset cover based on information representative of the established service state;

said step of determining said group key management message comprises determining, for each service, a component of the management message at least partly based on information representative of said established service subset covers, and further comprising the step of

combining said components for forming said group key management message.

19. An arrangement for improved key distribution in a system for selective access to services, wherein a group key management message is transferred to a group of users, said arrangement comprising:

means for creating set of encryption keys based on a stateless subset cover scheme, each user being associated with a leaf in said scheme;

means for establishing at least a state key and a corresponding at least a state representing a subset of users that have the at least a state key and a subset of users that do not have the at least a state key;

means for determining at least a subset cover based on information representative of the established at least a state; and

means for determining at least part of said group key management message at least partly based on the determined said at least a subset cover.

20. The arrangement of claim 19, wherein said means for determining a group key management message comprises means for determining a first message part extractable by a sub-group of users which have said at least a state key.

21. The arrangement of claim 20, wherein the sub-group of users that have said at least a state key comprises users that have said at least a state key and shall remain active.

22. The arrangement of claim 20, further comprising:

means for protecting at least a service protection key at least partly based on said at least a state key; and

means for incorporating said protected at least service protection key into said group key management message.

23. The arrangement of claim 22, wherein said means for protecting an at least a service protection key is operable for protecting said at least a service protection key based on said at least a state key as well as at least an additional key, wherein said at least an additional key is protected based on encryption keys of a subset cover of users which shall remain active and incorporated in protected form into said first part of said group key management message.

24. The arrangement of claim 23, wherein said at least a state key includes a main state key K_state and wherein said means for determining a group key management message is operable to determine at least a message part M according to:

M={T, S_rs, E(H_Srs, K_P) . . . S_t, E(H_Stu, K_P), E(K_E, K_M)}, K_E=F(K_P, K_state)

where T is a state identifier, S_rs S_tu are user sets covering users which shall remain active among those users which have said at least a state key, E is an encryption function, H_Srs, . . . , H_Stu are encryption keys of the stateless subset cover scheme corresponding to said user sets, K_P is said at least an additional key and K_E a corresponding envelope key calculated as a function F of said at least an additional key and said main state key, and K_M is a service protection key.

25. The arrangement of claim 22, wherein said at least a service protection key as well as a new state key are protected at least partly based on said main state key, and said protected new state key is also incorporated into said group key management message.

26. The arrangement of claim 20, wherein said means for determining a group key management message further comprises means for determining a second message part extractable by a sub-group of users which do not have the at least a state key.

27. The arrangement of claim 26, wherein the sub-group of users that do not have the at least a state key comprises users to be joined as active users.

28. The arrangement of claim 27, further comprising means for protecting said at least a state key and a service protection key based on encryption keys of a subset cover of users to be joined as active users and means for incorporating them in protected form into said second part of said group key management message.

29. The arrangement of claim 19, wherein said means for determining a subset cover comprises:

means for marking users based on said state information; and

means for computing said subset cover based on said user markings.

30. The arrangement of claim 29, wherein said means for marking users based on said state information comprises means for marking users without the at least a state key as active users, and said computing means operates according to a general subset cover calculation procedure

31. The arrangement of claim 29, wherein said means for marking users based on said state information is operable to mark users based on a categorization of users into three types:

users that have the at least a state key but shall be revoked;

users that have the at least a state key and shall remain active; and

users without the at least a state key.

32. The arrangement of claim 31, wherein said means for marking users based on said state information comprises:

means for initially marking users without the at least a state key as undefined users;

means for marking each user with the at least a state key as one of

a user that shall remain active, referred to as a member, and

a user that shall be revoked, referred to as not a member; and

means for re-marking each undefined user as one of;

a member and not a member, depending on the previous marking of users with the at least a state key.

33. The arrangement of claim 29, wherein said means for marking users based on said state information and said means for computing said subset cover based on said user markings are configured to operate simultaneously in an integrated manner.

34. The arrangement of claim 33, wherein said integrated operation of marking and computing is based on a categorization of users into three types:

users that have the at least a state key but shall be revoked;

users that have the at least a state key and shall remain active; and

users without the at least a state key.

35. The arrangement of claim 34, further comprising means for assigning colors to users depending on said categorization, and wherein said integrated operation of marking and computing is performed according to a coloring algorithm.

36. The arrangement of claim 19, wherein said arrangement is implemented at a key server.

37. The arrangement of claim 19, further comprising:

means for transmitting to an identified user a subset of the set of encryption keys, a state identifier, and a state key.

38. The arrangement of claim 37, further comprising means for receiving and storing said subset, state identifier, and state key.

39. The arrangement of claim 38, wherein the means for receiving and storing is implemented at a user terminal unit.