Patent Document ID: 8180049
Application ID: 12711924
Patent Flag: 1

Claim One:
1. A method of generating a first signature of a digital message M communicated between a signer and a verifier, wherein the signer is t levels below a root PKG (Private Key Generator) in a hierarchical system, and wherein the signer is associated with a signer ID tuple (ID 1 ,. .. , ID t ) that includes identity information ID t associated with the signer and identity information ID i associated with each of (t−1) lower-level PKGs in the hierarchy between the root PKG and the signer, the method comprising: (1) obtaining the signer's secret element operable to provide, to the signer, a value S t which is a linear combination, in a predefined group G 1 , of values P i with integer coefficients s i-1 , wherein i varies from 1 to t inclusive, wherein: for each i from 1 to t−1 inclusive, P i is a public element of the predefined group G 1 , wherein P i is generated for each of the signer's t−1 ancestral lower-level PKGs and depends at least on ID i ; P t is the signer's public element of the group G 1 , and depends at least on ID t ; for each i greater than 1 but less than or equal to t, the integer coefficient s i-1 of P i is an integer lower-level key generation secret generated for the corresponding ancestral lower-level PKG; (2) generating a signer private key s t which is an integer associated with the signer; (3) selecting a random message M′ and a random number r′; (4) generating a value operable to provide, to the verifier, a value 
 U=S t +s t P M′ wherein P M′ is an element of the group G 1 and is a value of a trapdoor hash function which maps a pair of a message value and an integer value into an element of the group G 1 , wherein P M′ is the value of the trapdoor hash function on a pair (M′;r′) of the random message M′ and the random number r′; (5) after operation (4), obtaining the digital message M; (6) identifying a number r such that the value of the trapdoor hash function on a pair (M;r) of the digital message M and the number r is equal to P M′ ; and (7) generating the first signature from the value U and the number r.