Patent ID: 7349538

Claim:
A method of generating a private key for a recipient z in a system, wherein the recipient z is n+1 levels below a root PKG in the hierarchy, and wherein the recipient is associated with a recipient ID-tuple (ID z1 , . . . , ID z(n+1 ) that includes identity information ID z)n+1) associated with the recipient and identity information ID zi associated with each of n lower-level PKGs in the hierarchy between the root PKG and the recipient, the method comprising: generating a first cyclic group G 1 of elements and a second cyclic group G 2 of elements; selecting a function ê capable of generating an element of the second cyclic group G 2 from two elements of the first cyclic group G 1 ; selecting a root generator P 0 of the first cyclic group G 1 ; selecting a random root key generation secret s 0 associated with and known only to the root PKG; generating a root key generation parameter Q 0 =s 0 P 0 ; selecting a function H 1 capable of generating an element of the first cyclic group G 1 from a first string of binary digits; generating a public element P zi for each of the n lower-level PKGs, wherein P zi =H 1 (ID 1 , . . . , ID zi ) for 1≦i≦n; selecting a lower-level key generation secret s zi for each of the n lower-level PKGs, wherein each lower-level key generation secret s zi is known only to its associated lower-level PKG; generating a lower-level secret element S zi for each of the n lower-level PKGs, wherein S zi =S zi(i−1) +S z(i−1) P zi for 1≦i≦n, wherein S z0 =S 0 , and wherein S z0 is defined to be zero; generating a lower-level key generation parameter Q zi for each of the n lower-level PKGs, wherein Q zi =S zi P 0 for 1≦i≦n; generating a recipient public element P z(n+1) =H 1 (ID z1 , . . . , ID z(n+1) ) associated with the recipient, wherein P z(n+1) is an element of the first cyclic group G 1 ; and generating a recipient private key S z ⁡ ( n + 1 ) = S zn + s zn ⁢ P z ⁡ ( n + 1 ) = ∑ i = 1 n + 1 ⁢ s z ⁡ ( i - 1 ) ⁢ P zi associated with the recipient.