Hierarchical identity-based encryption and signature schemes

• US 20030179885A1
• Filed: 03/07/2003
• Published: 09/25/2003
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: DOCOMO Communications Laboratories USA, Inc.
• Inventors: Gentry, Craig B., Silverberg, Alice
• Granted Patent: US 7,349,538 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• 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

Methods are provided for encoding and decoding a digital message between a sender and a recipient in a system including a plurality of private key generators (“PKGs”). The PKGs include at least a root PKG and n lower-level PKG in the hierarchy between the root PKG and the recipient. A root key generation secret is selected and is known only to the root PKG. A root key generation parameter is generated based on the root key generation secret. A lower-level key generation secret is selected for each of the n lower-level PKGs, wherein each lower-level key generation secret is known only to its associated lower-level PKG. A lower-level key generation parameter also is generated for each of the n lower-level PKGs using at least the lower-level key generation secret for its associated lower-level private key generator. The message is encoded to form a ciphertext using at least the root key generation parameter and recipient identity information associated with the recipient. A recipient private key is generated such that the recipient private key is related to at least the root key generation secret, one or more of the n lower-level key generation secrets, and the recipient identity information. The ciphertext is decoded to recover the message using at least the recipient private key.

Claims

1. A method of encoding and decoding a digital message between a sender and a recipient, wherein the recipient is n+1 levels below a root PKG in a hierarchical system including a plurality of PKGs, the plurality of PKGs including at least the root PKG and n lower-level PKGs in the hierarchy between the root PKG and the recipient, wherein n≧

1, the method comprising;

selecting a root key generation secret that is known only to the root PKG;

generating a root key generation parameter based on the root key generation secret;

selecting a lower-level key generation secret for each of the n lower-level PKGs, wherein each lower-level key generation secret is known only to its associated lower-level PKG;

generating a lower-level key generation parameter for each of the n lower-level PKGs, wherein each lower-level key generation parameter is generated using at least the lower-level key generation secret for its associated lower-level PKG;

encoding the message to form a ciphertext using at least the root key generation parameter and recipient identity information;

generating a recipient private key such that the recipient private key is related to at least the root key generation secret, one or more of the n lower-level key generation secrets associated with the n lower-level PKGs in the hierarchy between the root PKG and the recipient, and the recipient identity information; and

decoding the ciphertext to recover the message using at least the recipient private key.

2. A method of encoding and decoding a message as in claim 1, wherein the recipient identity information comprises a recipient ID-tuple (ID_z1, . . . , ID_z(n+1)) that includes identity information ID_z(n+1) associated with the recipient and identity information ID_zi associated with each of n lower-level PKGs in the hierarchy between the root PKG and the recipient.

3. A method of encoding and decoding a message as in claim 1, wherein the recipient private key is related to all of the n lower-level key generation secrets associated with the n lower-level PKGs in the hierarchy between the root PKG and the recipient.

4. A method of encoding and decoding a message as in claim 1, wherein encoding the message further includes securing the ciphertext against chosen-ciphertext attacks.

5. A method of encoding and decoding a message as in claim 4:

wherein encoding the message further includes

encrypting the message according to a symmetrical encryption scheme to form a symmetrical encryption; and

encrypting the symmetrical encryption according to a one-way encryption scheme to form the ciphertext; and

wherein decoding the ciphertext further includes

decrypting the ciphertext according to the one-way encryption scheme to recover the symmetrical encryption; and

decrypting the symmetrical encryption according to the symmetrical encryption scheme to recover the message.

6. A method of encoding and decoding a message between a sender and a recipient in a system including a plurality of PKGs, the plurality of PKGs including m lower-level PKGs in the hierarchy between the root PKG and the sender, wherein m≧

1, and n lower-level PKGs in the hierarchy between the root PKG and the recipient, wherein n≧

1, wherein at least l of the plurality of PKGs in the hierarchy are common ancestors to both the sender and the recipient, wherein l≧

1, and wherein PKG_l is a common ancestor PKG to both the sender and the recipient, the method further comprising;

selecting a root key generation secret that is known only to the root PKG;

generating a root key generation parameter based on the root key generation secret;

selecting a lower-level key generation secret for each of the m and n lower-level PKGs, wherein each lower-level key generation secret is known only to its associated lower-level PKG;

generating a lower-level key generation parameter for each of the m and n lower-level PKGs, wherein each lower-level key generation parameter is generated using at least the lower-level key generation secret for its associated lower-level PKG;

generating a sender private key such that the sender private key is related to at least sender identity information, the root key generation secret, and one or more of the m lower-level key generation secrets associated with the m PKGs between the root PKG and the sender;

generating a recipient private key such that is related to at least recipient identity information, the root key generation secret, and one or more of the n lower-level key generation secrets associated with the n lower-level PKGs in the hierarchy between the root PKG and the recipient;

encoding the message using at least the recipient identity information, the sender private key, and zero or more of the lower-level key generation parameters associated with the (m−

l+1) PKGs between the root PKG and the sender that are at or below the level of the common ancestor PKG_l, but not any of the lower-level key generation parameters that are associated with the (l−

1) PKGs above the common ancestor PKG_l; and

decoding the ciphertext using at least the recipient private key and zero or more of the lower-level key generation parameters associated with the (n−

l+1) PKGs between the root PKG and the recipient that are at or below the level of the lowest common ancestor PKG_l, but not using any of the lower-level key generation parameters that are associated with the (l−

1) PKGs that above the common ancestor PKG_l.

7. A method of encoding and decoding a message as in claim 6:

wherein encoding the message further includes using one or more of the lower-level key generation parameters associated with the (m−

l+1) PKGs between the root PKG and the sender that are at or below the level of the common ancestor PKG_l; and

wherein decoding the message further includes using one or more of the lower-level key generation parameters associated with the (n−

l+1) PKGs between the root PKG and the recipient that are at or below the level of the lowest common ancestor PKG_l.

8. A method of encoding and decoding a message as in claim 6:

wherein encoding the message further includes using one or more of the lower-level key generation parameters associated with the (m−

l+1) PKGs between the root PKG and the sender that are at or below the level of the common ancestor PKG_l; and

wherein decoding the message further includes using zero of the lower-level key generation parameters associated with the (n−

l+1) PKGs between the root PKG and the recipient that are at or below the level of the lowest common ancestor PKG_l.

9. A method of encoding and decoding a message as in claim 6:

wherein encoding the message further includes using zero of the lower-level key generation parameters associated with the (m−

l+1) PKGs between the root PKG and the sender that are at or below the level of the common ancestor PKG_l; and

wherein decoding the message further includes using one or more of the lower-level key generation parameters associated with the (n−

l+1) PKGs between the root PKG and the recipient that are at or below the level of the lowest common ancestor PKG_l.

10. A method of encoding and decoding a message as in claim 6, wherein the message is encoded using all of the lower-level key generation parameters associated with the (m−

l+1) PKGs between the root PKG and the sender that are at or below the level of the common ancestor PKG_l.

11. A method of encoding and decoding a message as in claim 6, wherein the message is decoded using all of the lower-level key generation parameters associated with the (n−

l+1) PKGs between the root PKG and the recipient that are at or below the level of the common ancestor PKG_l.

12. A method of generating and verifying a digital signature of a message between a sender and a recipient, wherein the sender is m+1 levels below a root PKG in a hierarchical system including a plurality of PKGs, the plurality of PKGs including at least the root PKG and m lower-level PKGs in the hierarchy between the root PKG and the sender, wherein m≧

1, the method comprising;

selecting a root key generation secret that is known only to the root PKG;

generating a root key generation parameter based on the root key generation secret;

generating a lower-level key generation secret for each of the m lower-level PKGs, wherein each lower-level key generation secret is known only to its associated lower-level PKG;

generating a lower-level key generation parameter for each of the m lower-level PKGs, wherein each lower-level key generation parameter is generated using at least the lower-level key generation secret for its associated lower-level PKG;

generating a sender private key for the sender such that the sender private key is related to at least sender identity information, the root key generation secret, and one or more of the m lower-level key generation secrets associated with the m lower-level PKGs in the hierarchy between the root PKG and the sender;

signing the message to generate the digital signature using at least the sender private key; and

verifying the digital signature using at least the root key generation parameter and the sender identity information.

13. A method of generating and verifying a digital signature as in claim 12, wherein:

one or more of the lower-level key generation parameters also is used to verify the digital signature.

14. A method of generating a private key for an entity in a system including a plurality of PKGs, the plurality of PKGs including at least a root PKG and n lower-level PKGs in the hierarchy between the root PKG and the entity, wherein n≧

1, the method comprising;

generating a root key generation secret that is known only to the root PKG;

generating a root key generation parameter based on the root key generation secret;

generating a lower-level key generation secret for each of the n lower-level PKGs, wherein each lower-level key generation secret is known only to its associated lower-level PKG;

generating a lower-level key generation parameter for each of the n lower-level PKGs, wherein each lower-level key generation parameter is generated using at least the lower-level key generation secret for its associated lower-level PKG;

generating a private key for the entity such that the private key is related to at least identity information associated with the entity, the root key generation secret, and one or more of the n lower-level key generation secrets associated with the n lower-level PKGs in the hierarchy between the root PKG and the entity; and

providing the private key to the entity.

15. A method of generating a private key for a recipient z in a system, wherein the recipient z is n+1 levels below a root PKG in the hierarchy, and wherein the recipient is associated with a recipient ID-tuple (ID_z1, . . . , ID_z(n+1)) that includes identity information ID_z(n+1) associated with the recipient and identity information ID_zi associated with each of n lower-level PKGs in the hierarchy between the root PKG and the recipient, the method comprising:

generating a first cyclic group G₁ of elements and a second cyclic group G₂ of elements;

selecting a function ê

capable of generating an element of the second cyclic group G₂ from two elements of the first cyclic group G₁;

selecting a root generator P₀ of the first cyclic group G₁;

selecting a random root key generation secret s₀ associated with and known only to the root PKG;

generating a root key generation parameter Q₀=s₀P₀;

selecting a function H₁ capable of generating an element of the first cyclic group G₁ from a first string of binary digits;

generating a public element P_zi for each of the n lower-level PKGs, wherein P_zi=H₁(ID₁, . . . , ID_zi) for 1≦

i≦

n;

selecting a lower-level key generation secret s_zi for each of the n lower-level PKGs, wherein each lower-level key generation secret s_zi is known only to its associated lower-level PKG;

generating a lower-level secret element S_zi for each of the n lower-level PKGs, wherein S_zi=S<sub>z(i−

1)</sub>+s<sub>z(i−

1)</sub>P_zi for 1≦

i≦

n, wherein s_z0=s₀, and wherein S_z0 is defined to be zero;

generating a lower-level key generation parameter Q_zi for each of the n lower-level PKGs, wherein Q_zi=s_ziP₀ for 1≦

i≦

n

generating a recipient public element P_z(n+1)=H₁(ID_z1, . . . , ID_z(n+1)) associated with the recipient, wherein P_z(n+1) is an element of the first cyclic group G₁; and

generating a recipient private key

$S_{z<br><br>\left(n+1\right)}=S_{\mathrm{zn}}+s_{\mathrm{zn}}<br><br>P_{z<br><br>\left(n+1\right)}=\underset{i=1}{\overset{n+1}{\sum <br><br>}}<br><br>s_{z<br><br>\left(i-1\right)}<br><br>P_{\mathrm{zi}}$

 

associated with the recipient.

16. A method of generating a private key as in claim 15, wherein:

both the first group G₁ and the second group G₂ are of the same prime order q.

17. A method of generating a private key as in claim 15, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

18. A method of generating a private key as in claim 15, wherein:

the function ê

is an admissible pairing.

19. A method of generating a private key as in claim 15, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G₁;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁; and

the recipient private key S_z(n+1) is an element of the first cyclic group G₁.

20. A method of encoding and decoding a digital message M communicated between a sender and a recipient z, wherein the recipient z is n+1 levels below a root PKG in a hierarchical system, and wherein the recipient is associated with a recipient ID-tuple (ID_z1, . . . , ID_z(n+1)) that includes identity information ID_z(n+1) associated with the recipient and identity information ID_zi associated with each of n lower-level PKGs in the hierarchy between the root PKG and the recipient, the method comprising:

generating a first cyclic group G₁ of elements and a second cyclic group G₂ of elements;

selecting a function ê

capable of generating an element of the second cyclic group G₂ from two elements of the first cyclic group G₁;

selecting a root generator P₀ of the first cyclic group G₁;

selecting a random root key generation secret s₀ associated with and known only to the root PKG;

generating a root key generation parameter Q₀=s₀P₀;

selecting a first function H₁ capable of generating an element of the first cyclic group G₁ from a first string of binary digits;

selecting a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

generating a public element P_zi for each of the n lower-level PKGs, wherein P_zi=H₁(ID₁, . . . , ID_zi) for 1≦

i≦

n;

selecting a lower-level key generation secret s_zi for each of the n lower-level PKGs, wherein each lower-level key generation secret s_zi is known only to its associated lower-level PKG;

generating a lower-level secret element S_zi for each of the n lower-level PKGs, wherein S_zi=S<sub>z(i−

1)</sub>+s<sub>z(i−

1)</sub>P_zi for 1≦

i≦

n, wherein s_z0=s₀, and wherein S_z0 is defined to be zero;

generating a lower-level key generation parameter Q_zi for each of the n lower-level PKGs, wherein Q_zi=s_ziP₀ for 1≦

i≦

n;

generating a recipient public element P_z(n+1)=H₁(ID_z1, . . . , ID_z(n+1)) associated with the recipient;

generating a recipient secret element

$S_{z<br><br>\left(n+1\right)}=S_{\mathrm{zn}}+s_{\mathrm{zn}}<br><br>P_{z<br><br>\left(n+1\right)}=\underset{i=1}{\overset{n+1}{\sum <br><br>}}<br><br>s_{z<br><br>\left(i-1\right)}<br><br>P_{\mathrm{zi}}$

 

associated with the recipient;

encoding the message M to generate a ciphertext C using at least the recipient ID-tuple (ID₁, . . . , ID_zi) and the root key generation parameter Q₀; and

decoding the ciphertext C to recover the message M using at least the recipient secret element S_z(n+1).

21. A method of encoding and decoding a digital message M as in claim 20, wherein:

both the first group G₁ and the second group G₂ are of the same prime order q.

22. A method of encoding and decoding a digital message M as in claim 20, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

23. A method of encoding and decoding a digital message M as in claim 20, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

24. A method of encoding and decoding a digital message M as in claim 20, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G₁;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁; and

the recipient secret element S_z(n+1) is an element of the first cyclic group G₁.

25. A method of encoding and decoding a digital message M as in claim 20, wherein:

encoding the message M further includes;

selecting a random parameter r; and

generating the ciphertext C=[U₀, U₂, . . . , V_n+1, V], wherein U_i=rP_zi for i=0 and for 2≦

i≦

n+1, wherein V=M⊕

H₂(g^r), and wherein g=ê

(Q₀, P_z1); and

decoding the ciphertext C further includes;

recovering the message M, using

$m=V\otimes <br><br>H_2<br><br>\left(\frac{\hat{e}\left(U_0,S_{z<br><br>\left(n+1\right)}\right)}{\underset{i=2}{\overset{n+1}{\prod <br><br>}}<br><br>\hat{e}\left(Q_{i-1},U_i\right)}\right)<br><br>\text{\hspace{1em}<br><br>}.$

26. A method of encoding and decoding a digital message M as in claim 25, wherein:

both the first group G₁ and the second group G₂ are of the same prime order q.

27. A method of encoding and decoding a digital message M as in claim 25, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

28. A method of encoding and decoding a digital message M as in claim 25, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

29. A method of encoding and decoding a digital message M as in claim 25, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G₁;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁;

the recipient secret element S_z(n+1) is an element of the first cyclic group G₁;

r is an element of the cyclic group Z/qZ; and

g is an element of the second cyclic group G₂.

30. A method of encoding and decoding a digital message M as in claim 20, further comprising:

selecting a third function H₃ capable of generating an integer of the cyclic group Z/qZ from a third string of binary digits; and

selecting a fourth function H₄ capable of generating a fourth string of binary digits from a fifth string of binary digits;

wherein encoding the message M further includes;

selecting a random binary string σ

,

selecting a symmetric encryption scheme E;

generating a random integer r=H₃(σ

, M, W), wherein W=E<sub>H4(σ

)</sub>(M); and

generating the ciphertext C=[U₀, U₂, . . . , U_n+1, V, W], wherein U_i=rP_zi for i=0 and for 2≦

i≦

n+1, wherein V=σ

⊕

H₂(g^r), and wherein g=ê

(Q₀, P_z1); and

wherein decoding the ciphertext C further includes;

recovering the random binary string σ

using

$\mathrm{\sigma <br><br>}=V\oplus <br><br>H_2<br><br>\left(\frac{\hat{e}\left(U_0,S_{z<br><br>\left(n+1\right)}\right)}{\underset{i=2}{\overset{n+1}{\prod <br><br>}}<br><br>\hat{e}\left(Q_{i-1},U_i\right)}\right)<br><br>\text{\hspace{1em}<br><br>};<br><br>$

 

and

recovering the message M using M=E<sub>H4(σ

)</sub><sup>−

1</sup>(W).

31. A method of encoding and decoding a digital message M as in claim 30, wherein:

both the first cyclic group G₁ and the second cyclic group G₂ are of the same prime order q.

32. A method of encoding and decoding a digital message M as in claim 30, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and p1 the second cyclic group G₂ is a multiplicative subgroup of a finite field.

33. A method of encoding and decoding a digital message M as in claim 30, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

34. A method of encoding and decoding a digital message M as in claim 30, further comprising:

confirming the internal consistency of the ciphertext C by;

computing an experimental random integer r′

=H₃(σ

, M, W); and

confirming that U₀=r′

P₀ and U_i=r′

P_zi for 2≦

i≦

n+1.

35. A method of encoding and decoding a digital message M as in claim 30, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G_i;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁;

the recipient secret element S_z(n+1) is an element of the first cyclic group G₁;

r is an element of the cyclic group Z/qZ; and

g is an element of the second cyclic group G₂.

36. A method of encoding and decoding a digital message M between a sender y and a recipient z in a system including a plurality of PKGs, the plurality of PKGs including m lower-level PKGs in the hierarchy between the root PKG and the sender y, wherein m≧

1, and n lower level PKGs in the hierarchy between the root PKG and the recipient z, wherein n≧

1, wherein at least l of the PKGs in the hierarchy are common ancestors to both the sender y and the recipient z, wherein l≧

1, wherein PKG_l is a common ancestor PKG to both the sender and the recipient, wherein the sender y is associated with a sender ID-tuple (ID_y1, . . . , ID_y(m+1)) that includes identity information ID_y(m+1) associated with the sender y and identity information ID_yi associated with each of m lower-level PKGs in the hierarchy between the root PKG and the sender y, and wherein the recipient is associated with a recipient ID-tuple (ID_zl, . . . , ID_z(n+1)) that includes identity information ID_z(n+1) associated with the recipient and identity information ID_zi associated with each of n lower-level PKGs in the hierarchy between the root PKG and the recipient, the method further comprising;

generating a first cyclic group G₁ of elements and a second cyclic group G₂ of elements;

selecting a function ê

capable of generating an element of the second cyclic group G₂ from two elements of the first cyclic group G₁;

selecting a root generator P₀ of the first cyclic group G₁;

selecting a random root key generation secret s₀ associated with and known only to the root PKG;

generating a root key generation parameter Q₀=s₀P₀;

selecting a first function H₁ capable of generating an element of the first cyclic group G₁ from a first string of binary digits;

selecting a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

generating a public element P_yi for each of the m lower-level PKGs, wherein P_yi=H₁(ID_y1, . . . , ID_yi) for 1≦

i≦

m, and wherein P_yi=P_zi for all i≦

l;

generating a public element P_zi for each of the n lower-level PKGs, wherein P_zi=H₁(ID₁, . . . , ID_zi) for 1≦

i≦

n;

selecting a lower-level key generation secret s_yi for each of the m lower-level PKGs, wherein s_yi=s_zi for all i≦

l;

selecting a lower-level key generation secret s_zi for each of the n lower-level PKGs, wherein each lower-level key generation secret s_zi 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<sub>y(i−

1)</sub>+s_y(i-1)P_yi for 1≦

i≦

m, and wherein S_yi=S_zi for all i≦

l;

generating a lower-level secret element S_zi for each of the n lower-level PKGs, wherein S_zi=S<sub>z(i−

1)</sub>+s<sub>z(i−

)</sub>P_zi for 1≦

i≦

n, wherein s_z0=s₀, and wherein S_z0 is defined to be zero;

generating a lower-level key generation parameter Q_yi for each of the m lower-level PKGs, wherein Q_yi=s_yiP₀ for 1≦

i≦

m, and wherein Q_yi=Q_zi for all i≦

l;

generating a lower-level key generation parameter Q_zi for each of the n lower-level PKGs, wherein Q_zi=s_ziP₀ for 1≦

i≦

n;

generating a sender public element P_y(m+1)=H_1(IDy1, . . . , ID_y(m+1)) associated with the sender y;

generating a recipient public element P_z(n+1)=H₁(ID_z1, . . . , ID_z(n+1)) associated with the recipient;

generating a sender secret element

$S_{y<br><br>\left(m+1\right)}=S_{\mathrm{ym}}+s_{\mathrm{ym}}<br><br>P_{y<br><br>\left(m+1\right)}=\underset{i=1}{\overset{m+1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_{y<br><br>\left(i-1\right)}<br><br>P_{\mathrm{yi}}$

 

associated with the sender;

generating a recipient secret element

$S_{z<br><br>\left(n+1\right)}=S_{\mathrm{zn}}+S_{\mathrm{zn}}<br><br>P_{z<br><br>\left(n+1\right)}=\underset{i=1}{\overset{n+1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_{z<br><br>\left(i-1\right)}<br><br>P_{\mathrm{zi}}$

 

associated with the recipient;

encoding the message M to generate a ciphertext C using at least the lower-level key generation parameters Q_yi for l<

i≦

m and the sender secret element S_y(m+1), but not using the lower-level key generation parameters Q_yi for i<

l; and

decoding the ciphertext C to recover the message M using at least the lower-level key generation parameters Q_zi for l<

i≦

n and the recipient secret element S_z(n+1), but not using the lower-level key generation parameters Q_zi for i<

l.

37. A method of encoding and decoding a digital message M as in claim 36, wherein encoding the message M further includes using the lower level key generation parameter Q_yl.

38. A method of encoding and decoding a digital message M as in claim 36, wherein decoding the message M further includes using the lower level key generation parameter Q_zl.

39. A method of encoding and decoding a digital message M as in claim 36, wherein:

both the first cyclic group G₁ and the second cyclic group G₂ are of the same prime order q.

40. A method of encoding and decoding a digital message M as in claim 36, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

41. A method of encoding and decoding a digital message M as in claim 36, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

42. A method of encoding and decoding a digital message M as in claim 36, wherein:

S₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G₁;

each of the public elements P_yi is an element of the first cyclic group G;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each of the lower-level key generation secrets S_yi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each secret element S_yi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_yi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁;

the sender public element P_y(m+1) is an element of the first cyclic group G₁;

the recipient secret element S_z(n+1) is an element of the first cyclic group G₁;

the sender secret element S_y(m+1) is an element of the first cyclic group G₁;

r is an element of the cyclic group Z/qZ; and

g is an element of the second cyclic group G₂.

43. A method of encoding and decoding a message as in claim 36:

wherein encoding the message M further includes;

selecting a random parameter r; and

encoding the message M to generate a ciphertext C=[U₀, U_l+1, . . . , U_n+1, V], wherein U₀=rP₀, wherein U_i=rP_zi for l+1≦

i<

n+1, wherein V=M ⊕

H₂(g_yl^r), and

$\mathrm{wherein}<br><br>\text{\hspace{1em}<br><br>}<br><br>g_{\mathrm{yi}}=\frac{\hat{e}<br><br>\left(P_0,\text{\hspace{1em}<br><br>}<br><br>S_{y<br><br>\left(m+1\right)}\right)}{\underset{i=l+1}{\overset{m+1}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{y<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{yi}}\right)}$

decoding the ciphertext C further includes;

recovering the message M using

$M=V\oplus <br><br>H_2<br><br>\left(\frac{e<br><br>\left(U_0,\text{\hspace{1em}<br><br>}<br><br>S_{z<br><br>\left(n+1\right)}\right)}{\underset{i=l+1}{\overset{n+1}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>e<br><br>\left(Q_{z<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>U_{\mathrm{zi}}\right)}\right)<br><br>\text{\hspace{1em}<br><br>}.$

44. A method of encoding and decoding a digital message M as in claim 43, wherein:

both the first cyclic group G₁ and the second cyclic group G₂ are of the same prime order q.

45. A method of encoding and decoding a digital message M as in claim 43, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

46. A method of encoding and decoding a digital message M as in claim 43, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

47. A method of encoding and decoding a digital message M as in claim 43, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G₁;

each of the public elements P_yi is an element of the first cyclic group G;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each of the lower-level key generation secrets s_yi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each secret element S_yi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_yi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁;

the sender public element P_y(m+1) is an element of the first cyclic group G₁;

the recipient secret element S_z(n+1) is an element of the first cyclic group G₁;

the sender secret element S_y(m+1) is an element of the first cyclic group G₁;

r is an element of the cyclic group Z/qZ; and

g_yl is an element of the second cyclic group G₂.

48. A method of encoding and decoding a digital message M as in claim 36:

wherein encoding the message M further includes;

selecting a random parameter r; and

encoding the message M to generate a ciphertext C=[U₀, U_l+1, . . . , U_n+1, V], wherein U₀=rP₀, wherein U_l+1=r(P_y(l+1)−

P_z(l+1)), wherein U_i=rP_zi for l+2≦

i≦

n, wherein V=M⊕

H₂(g_y(l+1)^r), and wherein

$g_{y<br><br>\left(l+1\right)}=\frac{\hat{e}<br><br>\left(P_0,\text{\hspace{1em}<br><br>}<br><br>S_{y<br><br>\left(n+1\right)}\right)}{\underset{i=l+2}{\overset{m}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{y<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{yi}}\right)}=\hat{e}<br><br>\left(P_0,\text{\hspace{1em}<br><br>}<br><br>S_{y<br><br>\left(l+1\right)}\right);<br><br>$

 

and

decoding the ciphertext C further includes;

recovering the message M using

$M=V\oplus <br><br>H_2<br><br>\left(\frac{\hat{e}<br><br>\left(U_0,\text{\hspace{1em}<br><br>}<br><br>S_{z<br><br>\left(n+1\right)}\right)<br><br>\hat{e}<br><br>\left(U_{l+1},\text{\hspace{1em}<br><br>}<br><br>Q_{\mathrm{zl}}\right)}{\underset{i=l+2}{\overset{n}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{z<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>U_i\right)}\right)<br><br>\text{\hspace{1em}<br><br>}.$

49. A method of encoding and decoding a digital message M as in claim 36:

wherein encoding the message M further includes;

selecting a random parameter r; and

encoding the message M to generate a ciphertext C=[U₀, U_l+2, . . . , U_n, V], wherein U₀=rP₀, wherein U_i=rP_zi for l+2≦

i≦

n wherein V=M⊕

H₂(g_z(l+1)^r), and wherein

$g_{z<br><br>\left(l+1\right)}=\frac{\hat{e}<br><br>\left(P_0,\text{\hspace{1em}<br><br>}<br><br>S_{y<br><br>\left(m+1\right)}\right)<br><br>\hat{e}<br><br>\left(Q_{\mathrm{yl}},\text{\hspace{1em}<br><br>}<br><br>\left(P_{z<br><br>\left(l+1\right)}-P_{y<br><br>\left(l+1\right)}\right)\right)}{\underset{i=l+2}{\overset{m}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{y<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{yi}}\right)}=\hat{e}<br><br>\left(P_0,\text{\hspace{1em}<br><br>}<br><br>S_{z<br><br>\left(l+1\right)}\right);<br><br>$

 

and

decoding the ciphertext C further includes;

recovering the message M using

$M=V\oplus <br><br>H_2<br><br>\left(\frac{\hat{e}<br><br>\left(U_0,\text{\hspace{1em}<br><br>}<br><br>S_{z<br><br>\left(n+1\right)}\right)}{\underset{i=l+2}{\overset{n}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{z<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>U_i\right)}\right)<br><br>\text{\hspace{1em}<br><br>}.$

50. A method of encoding and decoding a digital message M as in claim 36, further comprising:

selecting a third function H₃ capable of generating an integer of the cyclic group Z/qZ from a third string of binary digits; and

selecting a fourth function H₄ capable of generating a fourth string of binary digits from a fifth string of binary digits;

wherein encoding the message M further includes;

selecting a random binary string σ

;

computing a random integer r=H₃(σ

, M, W), wherein W=E<sub>H4 (σ

)</sub>(M); and

generating the ciphertext C=[U₀, U_l+1, . . . , U_n+1, V, W], wherein U_i=rP_zi for i=0 and for l+1≦

i≦

n+1, wherein V=σ

⊕

H₂(g_yl^r), and wherein

$g_{\mathrm{yl}}=\frac{\hat{e}<br><br>\left(P_0,\text{\hspace{1em}<br><br>}<br><br>S_{y<br><br>\left(m+1\right)}\right)}{\underset{i=l+1}{\overset{m+1}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{y<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{yi}}\right)};<br><br>$

 

and

wherein decoding the ciphertext C further includes;

recovering the random binary string σ

using

$\mathrm{\sigma <br><br>}=V\oplus <br><br>H_2<br><br>\left(\frac{\hat{e}<br><br>\left(U_0,\text{\hspace{1em}<br><br>}<br><br>S_{z<br><br>\left(n+1\right)}\right)}{\underset{i=l+1}{\overset{n+1}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{z<br><br>\left(i-1\right)},\text{\hspace{1em}<br><br>}<br><br>U_{\mathrm{zi}}\right)}\right);<br><br>$

 

and

recovering the message M using M=E<sub>H4(σ

)</sub><sup>−

1</sup>(W).

51. A method of encoding and decoding a digital message M as in claim 49, wherein:

both the first cyclic group G₁ and the second cyclic group G₂ are of the same prime order q.

52. A method of encoding and decoding a digital message M as in claim 49, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

53. A method of encoding and decoding a digital message M as in claim 49, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

54. A method of encoding and decoding a digital message M as in claim 49, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_zi is an element of the first cyclic group G₁;

each of the public elements P_yi is an element of the first cyclic group G;

each of the lower-level key generation secrets s_zi is an element of the cyclic group Z/qZ;

each of the lower-level key generation secrets s_yi is an element of the cyclic group Z/qZ;

each secret element S_zi is an element of the first cyclic group G₁;

each secret element S_yi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_zi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_yi is an element of the first cyclic group G₁;

the recipient public element P_z(n+1) is an element of the first cyclic group G₁;

the sender public element P_y(m+1) is an element of the first cyclic group G₁;

the recipient secret element S_z(n+1) is an element of the first cyclic group (G₁;

the sender secret element S_y(m+1) is an element of the first cyclic group G₁;

r is an element of the cyclic group Z/qZ; and

g_yl is an element of the second cyclic group G₂.

55. A method of encoding and decoding a digital message M as in claim 49, further comprising:

confirming the internal consistency of the ciphertext C by;

computing an experimental random integer r′

=H₃(σ

, M, W); and

confirming that U₀=r′

P₀ and U_i=r′

P_zi for l+1≦

i≦

n+1.

56. A method of generating and verifying a digital signature Sig of a digital message M communicated between a sender and a recipient, wherein the sender is m+1 levels below a root PKG in a hierarchical system, and wherein the sender is associated with a sender ID-tuple (ID_y1, . . . , ID_y(m+1)) that includes identity information ID_y(m+1) associated with the sender and identity information ID_yi associated with each of m lower-level PKGs in the hierarchy between the root PKG and the sender, the method comprising:

generating a first cyclic group G₁ of elements and a second cyclic group G₂ of elements;

selecting a bilinear, non-degenerate pairing ê

capable of generating an element of the second cyclic group G₂ from two elements of the first cyclic group G₁;

selecting a root generator P₀ of the first cyclic group G₁;

selecting a random root key generation secret s₀ associated with and known only to the root PKG;

generating a root key generation parameter Q₀=s₀P₀;

selecting a first function H₁ capable of generating an element of the first cyclic group G₁ from a first string of binary digits;

generating a public element P_yi for each of the m lower-level PKGs, wherein P_yi=H₁(ID_y1, . . . , ID_yi) for 1≦

i≦

m;

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<sub>y(i−

1)</sub>+S<sub>y(i−

1)</sub>P_yi for 1≦

i≦

m,;

generating a lower-level key generation parameter Q_yi for each of the m lower-level PKGs, wherein Q_yi=S_yiP₀ for 1≦

i≦

m;

generating a sender public element P_y(m+1)=H₁(IDy₁, . . . , ID_y(m+1)) associated with the sender;

generating a sender secret element S_y(m+1)=S_ym+s_ymP_y(m+1)=Σ

_i=1^m+1s<sub>y(i−

1)</sub>P_yi associated with the sender;

signing the message M to generate a digital signature Sig using at least the sender secret element S_y(m+1); and

verifying the digital signature Sig using at least the root key generation parameter Q₀ and the lower-level key generation parameters Q_yi.

57. A method of generating and verifying a digital signature Sig as in claim 56, wherein:

both the first group G₁ and the second group G₂ are of the same prime order q.

58. A method of generating and verifying a digital signature Sig as in claim 56, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

59. A method of encoding and decoding a digital message M as in claim 56, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

60. A method of encoding and decoding a digital message M as in claim 56, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_yi is an element of the first cyclic group G;

each of the lower-level key generation secrets s_yi is an element of the cyclic group Z/qZ;

each secret element S_yi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_yi is an element of the first cyclic group G₁;

the sender public element P_y(m+1) is an element of the first cyclic group G₁; and

the sender secret element S_y(m+1) is an element of the first cyclic group G₁.

61. A method of generating and verifying a digital signature Sig as in claim 56, further comprising:

selecting a second function H₃ capable of generating an element of the first cyclic group G₁ from a second string of binary digits;

selecting a sender key generation secret s_y(m+1) for the sender y, wherein the sender key generation secret s_y(m+1) is known only to the sender; and

generating a sender key generation parameter Q_y(m+1) associated with the sender, wherein Q_y(m+1)=s_y(m+1)P₀;

wherein signing the message M further includes;

generating a message element P_M=H₃(ID_y1, . . . , ID_y(m+1), M), wherein the message element P_M is an element of the first cyclic group G₁; and

generating the digital signature Sig using Sig=S_y(m+1)+S_y(m+1)P_M; and

wherein verifying the digital signature Sig further includes;

confirming that

$\frac{\hat{e}<br><br>\left(P_0,\mathrm{Sig}\right)}{\hat{e}<br><br>\left(Q_{y<br><br>\left(m+1\right)},P_M\right)<br><br>\underset{i=2}{\overset{m+1}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{e}<br><br>\left(Q_{y<br><br>\left(i-1\right)},P_{\mathrm{yi}}\right)}=\hat{e}<br><br>\left(Q_0,P_1\right).$

62. A method of generating and verifying a digital signature Sig as in claim 61, wherein:

both the first group G₁ and the second group G₂ are of the same prime order q.

63. A method of generating and verifying a digital signature Sig as in claim 61, wherein:

the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

64. A method of encoding and decoding a digital message M as in claim 61, wherein:

the function ê

is a bilinear, non-degenerate, and efficiently computable pairing.

65. A method of encoding and decoding a digital message M as in claim 61, wherein:

s₀ is an element of the cyclic group Z/qZ;

Q₀ is an element of the first cyclic group G₁;

each of the public elements P_yi is an element of the first cyclic group G;

each of the lower-level key generation secrets s_yi and the sender key generation secret S_y(m+1) is an element of the cyclic group Z/qZ;

each secret element S_yi is an element of the first cyclic group G₁;

each of the lower-level key generation parameters Q_yi and the sender key generation parameter Q_y(m+1) is an element of the first cyclic group G₁;

the sender public element P_y(m+1) is an element of the first cyclic group G₁; and

the sender secret element S_y(m+1) is an element of the first cyclic group G₁.