Patent Document ID: 20100153712
Application ID: 12711924
Patent Flag: 0

Claim One:
1. A method of generating and verifying a signature Sig of a digital message M communicated between a signer and a verifier, wherein the signer is t levels below a root PKG in a hierarchical system, and wherein the signer is associated with a signer ID tuple (ID y1 ,. .. , ID yt ) that includes identity information ID yt associated with the signer and identity information ID yi associated with each of (t−1) lower-level PKGs in the hierarchy between the root PKG and the signer, the method comprising: generating a first cyclic group G 1 of elements and a second cyclic group G 2 of elements; selecting a bilinear, non-degenerate pairing e 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 first 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 yi for each of the t lower-level PKGs, wherein P yi =H 1 (ID y1 ,. .. , ID yi ) for 1≦i≦(t−1); selecting a lower-level key generation secret s yi for each of the n lower-level PKGs, wherein each lower-level key generation secret s yi is known only to its associated lower-level PKG; generating a lower-level secret element S yi for each of the m lower-level PKGs, wherein S yi =S y(i−1) +s y(i−1) P yi for 1≦i≦(t−1); generating a lower-level key generation parameter Q y for each of the m lower-level PKGs, wherein Q yi =s yi P 0 for 1≦i≦(t−1); generating a signer public element P yt =H 1 (ID y1 ,. .. , ID yt ) associated with the signer; generating a signer secret element s yt = S y ( t - 1 ) + s y ( t - 1 ) P yt = ∑ i = 1 t s y ( i - 1 ) P y i associated with the signer; selecting a random signer trapdoor secret s′ yt εZ/qZ; generating a public hash key Q′ yt =s′ yt P 0 ; selecting a random message M′ and a random number r′; signing the random message M′ to generate a digital signature Sig = ( ∑ i = 1 t s i - 1 P i ) + s i P M ′ , wherein P M′ =H((M′+r′ s′ yt )P 0 ); generating r=(s′ yt ) −1 (M′−M)+r′; and verifying the digital signature Sig by confirming that e(Sig, P 0 )=e(Q yt , P M )π i=1 t e(Q y(i−1) , P i ), wherein P M =H 1 (MP 0 +rQ′ yt ).