HIERARCHICAL IDENTITY-BASED ENCRYPTION AND SIGNATURE SCHEMES

• US 20080052521A1
• Filed: 10/24/2007
• Published: 02/28/2008
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Gentry, Craig, Silverberg, Alice
• Granted Patent: US 7,590,854 B2
• Time in Patent Office: Days
• US Class Current: 713/180
• CPC Class Codes: H04L 9/007 involving hierarchical structures
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A signature {Sig, {Q_i}} is generated on a message M by a signer E_t in a hierarchical system including the entities E₀, E₁, . . . , E_t, each entity E_i (i>0) being a child of E_i−1. Here $\mathrm{Sig}=S_t+s_t{P}_M=\sum _{i=1}^t{s}_{i-1}{P}_i,$
where: each S_i is a secret key of E_i; each s_i is a secret of S_i; P_M is a public function of M; each P_i is a public function of the ID'"'"'s of all entities E_j such that 1≦j≦i; each Q_i=s_iP₀ where P₀ is public. The verifier confirms that $\frac{\hat{e}\left(P_0,\mathrm{Sig}\right)}{\hat{e}\left(Q_t,P_M\right)\prod _i\hat{e}\left(Q_{i-1},P_i\right)}=V,$
where: 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; ê is a bilinear non-degenerate mapping; V can be ê(Q₀,P_i0) where i₀ is predefined (e.g. 1), or V can be another expression is a verifier is part of the hierarchical system.

Claims

1. 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₀ in a hierarchical system including at least the entities E₀, E₁, . . . , E_t, t≧

2, wherein each entity E_i (i=1, . . . ,t) is a child of entity E<sub>i−

1</sub> in the hierarchical system, the method comprising;

(1) obtaining the signer'"'"'s secret key S_t which is a member of a group G₁;

(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_tP_M

wherein;

“

+”

is a group operation in the group G₁; and

P_M is a value depending on the message M and is a member of the group G₁.

2. The method of claim 1 wherein

$S_t=\sum _{}^{}$

i = 1 t ⁢

s i - 1 ⁢

P i ,

wherein each P_i is a public function of an identity of the entity E_i, and each s<sub>i−

1</sub> is an integer secret of the entity E<sub>i−

1</sub>.

3. The method of claim 2 wherein in operation (1), the signer obtains S_t from the entity E_t−

1, and in operation (2) the signer generates s_t.

4. The method of claim 2, wherein each P_i depends on the identity of each entity E_j such that 1≦

j≦

i.

5. The method of claim 1 wherein:

each entity E_i (i>

0) receives its secret key S_i from the entity E<sub>i−

1</sub>;

each entity E_i (i<

t) generates its secret s_i and also generates a secret key S_i+1 as;

S_i+1=S_i+s_iP_i+1

and provides the secret key S_i+1 to the entity E_i+1;

each entity E_i (0≦

i≦

t) generates a value Q_i=s_iP₀, where P₀ is a predefined element of the group G₁, and each entity E_i (1≦

i≦

t) obtains the values Q_j for all j<

i.

6. The method of claim 5 further comprising providing the signature component Sig to a verifier, wherein the verifier has access to values {Q_i} for values i in a subset of integers from 0 to t inclusive.

7. The method of claim 6 wherein said subset of integers from 0 to t inclusive comprises each integer from 0 to t inclusive except the integer 1.

8. The method of claim 6 wherein said subset of integers from 0 to t inclusive is the set of all integers from L to t inclusive, where L is an integer greater than 1;

and

the verifier is a child of the entity E_L in the hierarchical system.

9. The method of claim 5, wherein each P_i depends on the identity of each entity E_j such that 1≦

j≦

i and also on each Q_j such that 1≦

j≦

i.

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₀ in a hierarchical system including at least the entities E₀, E₁, . . . , E_t, t≧

2, wherein each entity E_i (i=1, . . . ,t) is a child of entity E<sub>i−

1</sub> in the hierarchical system, the method comprising;

(1) obtaining a signature component Sig which is an element of a predefined group G₁;

(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

$\frac{\hat{e}<br><br>\left(P_0,\mathrm{Sig}\right)}{\hat{e}<br><br>\left(Q_t,P_M\right)<br><br>\underset{i}{\prod <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{i-1},P_i\right)}=V$

wherein;

P₀ is a predefined element of a group G₁;

the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integers i in a proper subset of the integers from 1 to t inclusive;

each Q<sub>i−

1</sub>=s<sub>i−

1</sub>P₀, where s<sub>i−

1</sub> is an integer secret of the entity E<sub>i−

1</sub>;

Q_t=s_tP₀, where s_i is an integer secret of the entity E_t;

ê

is a bilinear non-degenerate mapping of G₁×

G₁ into a predefined group G₂;

P_M is a value depending on the message M and is a member of the group G₁;

each P_i depends on an identity of the entity E_i;

V is an element of the group G₂.

11. The method of claim 10 wherein the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integers i from 1 to t inclusive except a predefined integer i₀, and V=ê

(Q₀,P_i0).

12. The method of claim 10 wherein the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integers i from 2 to t inclusive, and V=ê

(Q₀,P₁).

13. The method of claim 10 wherein:

operations (1), (2), (3) are performed by an entity E_zm which is m levels below the entity E₀ in the hierarchical system, and the hierarchical system includes the entities E_z(L+1), . . . , E_zm, wherein each entity E_zi (i=L+1, . . . ,m) is i levels below E₀, where L is a predefined integer greater than 1 and less than t and less than m;

the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integer i from L+1 to t inclusive; and

$V=\frac{\hat{e}<br><br>\left(P_0,S_{\mathrm{zm}}\right)}{\underset{i=L+1}{\overset{m}{\prod <br><br>}}<br><br>\hat{e}<br><br>\left(Q_{z<br><br>\left(i-1\right)},P_{\mathrm{zi}}\right)}$

wherein;

$S_{\mathrm{zm}}=\underset{i=1}{\overset{L}{\sum <br><br>}}<br><br>s_{i-1}<br><br>P_i+\underset{i=L+1}{\overset{m}{\sum <br><br>}}<br><br>s_{z<br><br>\left(i-1\right)}<br><br>P_{\mathrm{zi}};<br><br>$

each P_zi (i>

L) is a public function of an identity of the entity E_zi;

each s<sub>i−

1</sub> is an integer secret of the entity E<sub>i−

1</sub>, and each s<sub>z(i−

1)</sub> is an integer secret of the entity E<sub>z(i−

1)</sub>.

14. The method of claim 10 wherein:

each entity E_i (i>

0) receives its secret key S_i from the entity E<sub>i−

1</sub>;

each entity E_i (i<

t) generates its secret s_i and also generates a secret key S_i+1 as;

S_i+1=S_i+s_iP_i+1

and provides the secret key S_i+1 to the entity E_i+1;

each entity E_i (0≦

i≦

t) generates a value Q_i=s_iP₀, where P₀ is a predefined element of the group G₁.

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₀ in a hierarchical system including at least the entities E₀, E₁, . . . , E_t, t≧

2, wherein each entity E_i (i=1, . . . ,t) is a child of entity E<sub>i−

1</sub> 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₁;

(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_tP_M

wherein;

“

+”

is a group operation in the group G₁; and

P_M is a value depending on the message M and is a member of the group G₁.

16. The apparatus of claim 15 wherein

$S_t=\sum _{}^{}$

i = 1 t ⁢

s i - 1 ⁢

P i ,

wherein each P_i is a public function of an identity of the entity E_i, and each s<sub>i−

1</sub> is an integer secret of the entity E<sub>i−

1</sub>.

17. The apparatus of claim 16 wherein in operation (1), the signer obtains S_t from the entity E_t−

1, and in operation (2) the signer generates s_t.

18. The apparatus of claim 16 wherein:

each entity E_i (i>

0) receives its secret key S_i from the entity E<sub>i−

1</sub>;

each entity E_i (i<

t) generates its secret s_i and also generates a secret key S_i+1 as;

S_i+1=S_i+s_iP_i+1

and provides the secret key S_i+1 to the entity E_i+1;

each entity E_i (0≦

i≦

t) generates a value Q_i=s_iP₀, where P₀ is a predefined element of the group G₁, and each entity E_i (1≦

i≦

t) obtains the values Q_j for all j<

i.

19. The apparatus of claim 18 wherein the apparatus is further for providing the signature component Sig to a verifier, wherein the verifier has access to values {Q_i} for values i in a subset of integers from 0 to t inclusive, wherein said subset of integers from 0 to t inclusive comprises each integer from 0 to t inclusive except one integer.

20. The apparatus of claim 18 wherein said subset of integers from 0 to t inclusive is the set of all integers from L to t inclusive, where L is an integer greater than 1 and less than t;

and

the verifier is a child of the entity E_L in the hierarchical system.

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₀ in a hierarchical system including at least the entities E₀, E₁, . . . , E_t, t≧

2, wherein each entity E_i (i=1, . . . ,t) is a child of entity E<sub>i−

1</sub> in the hierarchical system, the apparatus comprising circuitry for;

(1) obtaining a signature component Sig which is an element of a predefined group G₁;

(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

$\frac{\hat{e}<br><br>\left(P_0,\mathrm{Sig}\right)}{\hat{e}<br><br>\left(Q_t,P_M\right)<br><br>\underset{i}{\prod <br><br>}<br><br>\hat{e}<br><br>\left(Q_{i-1},P_i\right)}=V$

wherein;

P₀ is a predefined public element of a group G₁;

ê

is a bilinear non-degenerate mapping of G₁×

G₁ into a predefined group G₂;

P_M is a value depending on the message M and is a member of the group G₁;

each P_i depends on an identity of the entity E_i;

V is an element of the group G₂.

22. The apparatus of claim 21 wherein the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integers i from 1 to t inclusive except one integer i₀, and V=ê

(Q₀,P_i0).

23. The apparatus of claim 22 wherein the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integer i from 2 to t inclusive, and V=ê

(Q₀,P₁).

24. The apparatus of claim 21 wherein:

operations (1), (2), (3) are performed for an entity which is m levels below the entity E₀ in the hierarchical system, and the hierarchical system includes the entities E_z(L+1), . . . , E_zm, wherein each entity E_zi (i=L+1, . . . ,m) is i levels below E₀, where L is a predefined integer greater than 1 and less than t and less than m;

the product Π

_iê

(Q<sub>i−

1</sub>,P_i) is taken over all integer i from L+1 to t inclusive; and

$V=\frac{\hat{e}<br><br>\left(P_0,S_{\mathrm{zm}}\right)}{\underset{i=L+1}{\overset{m}{\prod <br><br>}}<br><br>\hat{e}<br><br>\left(Q_{z<br><br>\left(i-1\right)},P_{\mathrm{zi}}\right)}$

wherein;

$S_{\mathrm{zm}}=\underset{i=1}{\overset{L}{\sum <br><br>}}<br><br>s_{i-1}<br><br>P_i+\underset{i=L+1}{\overset{m}{\sum <br><br>}}<br><br>s_{z<br><br>\left(i-1\right)}<br><br>P_{\mathrm{zi}};<br><br>$

each P_zi (i>

L) is a public function of an identity of the entity E_zi;

each s<sub>i−

1</sub> is an integer secret of the entity E<sub>i−

1</sub>, and each s<sub>z(i−

1)</sub> is an integer secret of the entity E<sub>z(i−

1)</sub>.

25. The apparatus of claim 21 wherein:

each entity E_i (i>

0) receives its secret key S_i from the entity E<sub>i−

1</sub>;

each entity E_i (i<

t) generates its secret s_i and also generates a secret key S_i+1 as;

S_i+1=S_i+s_iP_i+1

and provides the secret key S_i+1 to the entity E_i+1;

each entity E_i (0≦

i≦

t) generates a value Q_i=s_iP₀, where P₀ is a predefined element of the group G₁.