Granted Patent B2

US 7,400,732 · App. 10/255,964 · Granted Jul 15, 2008

Abstract

Claims (94)

1. A collusion resistant method for determining an intermediate session key contained in a transmitted but missed intermediate key distribution broadcast, the intermediate key distribution being of a sequence of a plurality of key distributions distributed to a plurality of users, wherein the method is resistant to collusion attack by any coalition of up to a predetermined number t of users which have been revoked, the method comprising:

(a):

receiving at a local user a first broadcast that precedes the intermediate key distribution broadcast, wherein the first broadcast corresponds to a first session that precedes the intermediate session, and wherein the first broadcast includes:

a first polynomial corresponding to a first portion of the intermediate session key; and

a first set of t polynomials corresponding to the identifiers of the t revoked users and the index of the first session;

plugging the local user's identifier into the first set of t polynomials to obtain a first set of t data points;

evaluating the first portion of the intermediate session key based on:

(1) an interpolation of the first set of t data points and the local user's personal key; and

(2) the local user's identifier;

(b):

receiving at the local user a second broadcast that follows the intermediate key distribution broadcast, wherein the second broadcast corresponds to a second session that follows the intermediate session, and wherein the second broadcast includes:

a second polynomial corresponding to a second portion of the intermediate session key; and

a second set of t polynomials corresponding to the identifiers of the t revoked users and the index of the second session;

plugging the local user's identifier into the second set of t polynomials to obtain a second set of t data points;

evaluating the second portion of the intermediate session key based on:

(1) an interpolation of the second set of t data points and the local user's personal key; and

(2) the local user's identifier; and

(c):

combining the first portion and the second portion to obtain the intermediate session key.

2. The method of claim 1 , further comprising constructing the personal key by:

receiving a set of polynomials each of which has two variables and is of an order of t; and

plugging the local user's identifier as the value for both variables for the received polynomials to obtain a corresponding number of values, r.

3. The method of claim 1 , wherein combining the first portion and the second portion to obtain the intermediate session key involves:

evaluating the first polynomial to obtain a first value by plugging the local user's identifier into the first polynomial;

evaluating the second polynomial to obtain a second value by plugging the local user's identifier into the second polynomial;

producing a sum by adding the first value to the second value;

producing a third value by plugging the local user's identifier into the interpolation obtained in operation (a)(1) or (b)(1) as recited in claim 1 ; and

subtracting the third value from the sum.

4. The method of claim 1 , wherein the first portion of the intermediate session key contained within the preceding key distribution broadcast is one of a plurality of session key shares corresponding to a number of session keys to be contained in key distribution broadcasts following the preceding key distribution broadcast.

5. The method of claim 1 , wherein the second portion of the intermediate session key contained within the subsequent key distribution broadcast is one of a plurality of session key shares corresponding to a number of session keys that were contained in key distribution broadcasts that preceded the subsequent key distribution broadcast.

6. The method of claim 1 , wherein the intermediate distribution broadcast, the preceding key distribution broadcast and the subsequent key distribution broadcast are distributed over an non-secure communication network.

7. The method of claim 1 , wherein combining at least the first portion of the intermediate session key contained within the preceding key distribution broadcast and the second portion of the intermediate session key contained within the subsequent key distribution broadcast uses one or more self-healing session key combination techniques.

8. A computer-readable medium storing instructions which, when executed by a computer, cause the computer to perform a collusion resistant method for determining an intermediate session key contained in a transmitted but missed intermediate key distribution broadcast, the intermediate key distribution being of a sequence of a plurality of key distributions distributed to a plurality of users, wherein the method is resistant to collusion attack by any coalition of up to a predetermined number t of users which have been revoked, the method comprising:

(a):

receiving at a local user a first broadcast that precedes the intermediate key distribution broadcast, wherein the first broadcast corresponds to a first session that precedes the intermediate session, and wherein the first broadcast includes:

a first polynomial corresponding to a first portion of the intermediate session key; and

a first set of t polynomials corresponding to the identifiers of the t revoked users and the index of the first session;

plugging the local user's identifier into the first set of t polynomials to obtain a first set of t data points;

evaluating the first portion of the intermediate session key based on:

(1) an interpolation of the first set of t data points and the local user's personal key; and

(2) the local user's identifier;

(b):

receiving at the local user a second broadcast that follows the intermediate key distribution broadcast, wherein the second broadcast corresponds to a second session that follows the intermediate session, and wherein the second broadcast includes:

a second polynomial corresponding to a second portion of the intermediate session key; and

a second set of t polynomials corresponding to the identifiers of the t revoked users and the index of the second session; plugging the local user's identifier into the second set of t polynomials to obtain a second set of t data points;

evaluating the second portion of the intermediate session key based on:

(1) an interpolation of the second set of t data points and the local user's personal key; and

(2) the local user's identifier; and

(c):

combining the first portion and the second portion to obtain the intermediate session key.

9. The computer-readable medium of claim 8 , wherein the method further comprises constructing the personal key by:

receiving a set of polynomials each of which has two variables and is of an order of t; and

plugging the local user's identifier as the value for both variables for the received polynomials to obtain a corresponding number of values, r.

10. The computer-readable medium of claim 8 , wherein combining the first portion and the second portion to obtain the intermediate session key involves:

evaluating the first polynomial to obtain a first value by plugging the local user's identifier into the first polynomial;

evaluating the second polynomial to obtain a second value by plugging the local user's identifier into the second polynomial;

producing a sum by adding the first value to the second value;

producing a third value by plugging the local user's identifier into the interpolation obtained in operation (a)(1) or (b)(1) as recited in claim 1 ; and

subtracting the third value from the sum.

11. The computer-readable medium of claim 8 , wherein the first portion of the intermediate session key contained within the preceding key distribution broadcast is one of a plurality of session key shares corresponding to a number of session keys to be contained in key distribution broadcasts following the preceding key distribution broadcast.

12. The computer-readable medium of claim 8 , wherein the second portion of the intermediate session key contained within the subsequent key distribution broadcast is one of a plurality of session key shares corresponding to a number of session keys that were contained in key distribution broadcasts that preceded the subsequent key distribution broadcast.

13. The computer-readable medium of claim 8 , wherein the intermediate distribution broadcast, the preceding key distribution broadcast and the subsequent key distribution broadcast are distributed over an non-secure communication network.

14. The computer-readable medium of claim 8 , wherein combining at least the first portion of the intermediate session key and the second portion of the intermediate session key involves using one or more self-healing session key combination techniques.

15. A collusion resistant method for distributing an intermediate session key contained in a transmitted but missed intermediate key distribution broadcast, the intermediate key distribution being of a sequence of a plurality of key distributions distributed to a plurality of users, wherein the method is resistant to collusion attack by any coalition of up to a predetermined number t of users which have been revoked, the method comprising:

(a):

transmitting to a remote device a first broadcast that precedes the intermediate key distribution broadcast, wherein the first broadcast corresponds to a first session that precedes the intermediate session, and wherein the first broadcast includes:

a first polynomial corresponding to a first portion of the intermediate session key; and

a first set of t polynomials corresponding to the identifiers of the t revoked users and the index of the first session;

allowing the remote device to plug a user's identifier into the first set of t polynomials to obtain a first set of t data points;

allowing the remote device to evaluate the first portion of the intermediate session key based on:

(1) an interpolation of the first set of t data points and the local user's personal key; and

(2) the local user's identifier;

(b):

transmitting to the remote device a second broadcast that follows the intermediate key distribution broadcast, wherein the second broadcast corresponds to a second session that follows the intermediate session, and wherein the second broadcast includes:

a second polynomial corresponding to a second portion of the intermediate session key; and

a second set of t polynomials corresponding to the identifiers of the t revoked users and the index of the second session;

allowing the remote device to plug the user's identifier into the second set of t polynomials to obtain a second set of t data points;

allowing the remote device to evaluate the second portion of the intermediate session key based on:

(1) an interpolation of the second set of t data points and the local user's personal key; and

(2) the local user's identifier; and

(c):

allowing the remote device to combine the first portion and the second portion to obtain the intermediate session key.

16. The method of claim 15 , further comprising:

transmitting to the remote device a set of polynomials each of which has two variables and is of an order of t; and

allowing the remote device to construct the personal key by plugging the local user's identifier as the value for both variables for the received polynomials to obtain a corresponding number of values, r.

17. The method of claim 15 , wherein allowing the remote device to combine the first portion and the second portion to obtain the intermediate session key involves allowing the remote device to:

evaluate the first polynomial to obtain a first value by plugging the local user's identifier into the first polynomial;

evaluate the second polynomial to obtain a second value by plugging the local user's identifier into the second polynomial;

produce a sum by adding the first value to the second value;

produce a third value by plugging the local user's identifier into the interpolation obtained in operation (a)(1) or (b)(1) as recited in claim 1 ; and

subtract the third value from the sum.

18. The method of claim 15 , wherein the first portion of the intermediate session key contained within the preceding key distribution broadcast is one of a plurality of session key shares corresponding to a number of session keys to be contained in key distribution broadcasts following the preceding key distribution broadcast.

19. The method of claim 15 , wherein the second portion of the intermediate session key contained within the subsequent key distribution broadcast is one of a plurality of session key shares corresponding to a number of session keys that were contained in key distribution broadcasts that preceded the subsequent key distribution broadcast.

20. The method of claim 15 , wherein the intermediate distribution broadcast, the preceding key distribution broadcast and the subsequent key distribution broadcast are distributed over an non-secure communication network.

Assignments (8)