Patent ID: 7400732

Claim:
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.