Nova Patents
US7590854B2

Hierarchical identity-based encryption and signature schemes

Summary by NHIP

Hierarchical Identity-Based Signature

The method generates a digital signature by combining a signer's secret key with a message-dependent value using group operations. Distinctive elements include the hierarchical derivation where each entity Eᵢ receives key Sᵢ from parent Eᵢ₋₁ and generates secret sᵢ to compute Sᵢ₊₁ = Sᵢ + sᵢPᵢ₊₁, with Pᵢ depending on identities of entities Eⱼ where 1≤j≤i.

Claim Score by NHIP

Read claim 1, the broadest

Abstract

A signature {Sig, {Qi}} is generated on a message M by a signer Et in a hierarchical system including the entities E0, E1, . . . , Et, each entity Ei (i>0) being a child of Ei−1. Here Sig=St+st⁢PM=∑i=1t⁢si-1⁢Pi, where: each Si is a secret key of Ei; each si is a secret of Si; PM is a public function of M; each Pi is a public function of the ID's of all entities Ej such that 1≦j≦i; each Qi=siP0 where P0 is public. The verifier confirms that e^⁡(P0,Sig)e^⁡(Qt,PM)⁢∏i⁢⁢e^⁡(Qi-1,Pi)=V, where: the product Πiê(Qi−1,Pi) is taken over all integers i in a proper subset of the integers from 1 to t inclusive; ê is a bilinear non-degenerate mapping; V can be ê(Q0,Pi0) where i0 is predefined (e.g. 1), or V can be another expression is a verifier is part of the hierarchical system.

US7590854B2, drawing sheet 1
Sheet 1 of 272

Term

Term ended

Expired 3 June 2023, 3.3 years ago.

  1. Priority
  2. Filed
  3. Granted
  4. Expired
  5. Today

25 claims: 4 independent, 21 dependent

  1. 1
    Broadest claimClaim Score 38, average(NHIP)A computer-implemented method of generating a digital signature on a message M for a signer E t which is an entity t levels below an entity E 0 in a hierarchical system including at least the entities E 0 , E 1 , . . . , E t , t≧2, wherein each entity E i (i=1, . . . ,t) is a child of entity E i−1 in the hierarchical system, the method comprising:(1) obtaining the signer's secret key S t which is a member of a group G 1 ;(2) obtaining the signer's integer secret s t ;(3) generating a signature component Sig on the message M as a value Sig=S t +s t P M wherein: “+” is a group operation in the group G 1 ;and P M is a value depending on the message M and is a member of the group G 1 .
  2. 10
    A computer-implemented method of verifying a digital signature on a message M to verify that the digital signature is a valid signature by a signer E t which is an entity t levels below an entity E 0 in a hierarchical system including at least the entities E 0 , E 1 , . . . , E t , t≧2, wherein each entity E i (i=1, . . . ,t) is a child of entity E i−1 in the hierarchical system, the method comprising:(1) obtaining a signature component Sig which is an element of a predefined group G 1 ;(2) obtaining one or more values Q i associated with respective one or more entities E i , the one or more values Q i including a value Q t ;(3) confirming that e ^ ⁡ ( P 0 , Sig ) e ^ ⁡ ( Q t , P M ) ⁢ ∏ i ⁢ ⁢ e ^ ⁡ ( Q i - 1 , P i ) = V wherein: P 0 is a predefined element of a group G 1 ;the product Π i ê(Q i−1 ,P i ) is taken over all integers i in a proper subset of the integers from 1 to t inclusive;each Q i−1 =s i−1 P 0 , where s i−1 is an integer secret of the entity E i−1 ;Q t =s t P 0 , where s i is an integer secret of the entity E t ;ê is a bilinear non-degenerate mapping of G 1 ×G 1 into a predefined group G 2 ;P M is a value depending on the message M and is a member of the group G 1 ;each P i depends on an identity of the entity E i ;V is an element of the group G 2 .
  3. 15
    An apparatus operable to generate a digital signature on a message M for a signer E t which is an entity t levels below an entity E 0 in a hierarchical system including at least the entities E 0 , E 1 , . . . , E t , t≧2, wherein each entity E i (i=1, . . . ,t) is a child of entity E i−1 in the hierarchical system, the apparatus comprising circuitry for:(1) obtaining the signer's secret key S t which is a member of a group G 1 ;(2) obtaining the signer's integer secret s t ;(3) generating a signature component Sig on the message M as a value Sig=S t +s t P M wherein: “+” is a group operation in the group G 1 ;and P M is a value depending on the message M and is a member of the group G 1 .
  4. 21
    An apparatus operable to verify a digital signature on a message M to confirm that the digital signature is a valid signature by a signer E t which is an entity t levels below an entity E 0 in a hierarchical system including at least the entities E 0 , E 1 , . . . , E t , t≧2, wherein each entity E i (i=1, . . . ,t) is a child of entity E i−1 in the hierarchical system, the apparatus comprising circuitry for:(1) obtaining a signature component Sig which is an element of a predefined group G 1 ;(2) obtaining one or more values Q i associated with respective one or more entities E i , the one or more values Q i including a value Q t ;(3) confirming that e ^ ⁡ ( P 0 , Sig ) e ^ ⁡ ( Q t , P M ) ⁢ ∏ i ⁢ e ^ ⁡ ( Q i - 1 , P i ) = V wherein: P 0 is a predefined public element of a group G 1 ;ê is a bilinear non-degenerate mapping of G 1 ×G 1 into a predefined group G 2 ;P M is a value depending on the message M and is a member of the group G 1 ;each P i depends on an identity of the entity E i ;V is an element of the group G 2 .
Independent claims4