Patent ID: 7853016

Claim:
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 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 performing, by a machine associated with the signer, operations of: (1) obtaining the signer's secret element operable to provide, to the signer, a value S yt , wherein s yt = S y ⁡ ( t - 1 ) + s y ⁡ ( t - 1 ) ⁢ P yt = ∑ i = 1 t ⁢ s y ⁡ ( i - 1 ) ⁢ P y i wherein: s 0 is an integer root key generation secret associated with the root PKG; for each i from 1 to t−1 inclusive, s yi is an integer lower-level key generation secret generated for each of the signer's t−1 ancestral lower-level PKGs; for each i from 1 to t−1 inclusive, P yi is a public element of a predefined group G 1 , wherein in defining S yt as Σ i=1 t s y(i−1) P yi the group law on G 1 is written additively, wherein P yi is generated for each of the signer's t−1 ancestral lower-level PKGs and depends at least on ID yi ; P yt is the signer's public element of the group G 1 , and depends at least on ID yt ; (2) generating a signer private key s yt which is an integer associated with the signer; (3) selecting a random message M′ and a random number r′; (4) generating an offline signature operable to provide, to the verifier, a value U=S yt +s yt 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) 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 offline signature and the number r.