Hierarchical identity-based encryption and signature schemes
View Patent ↗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.
1. 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 1 of elements and a second cyclic group G 2 of elements;
selecting a function ê capable of generating an element of the second cyclic group G 2 from two elements of the first cyclic group G 1 ;
selecting a root generator P 0 of the first cyclic group G 1 ;
selecting a random root key generation secret s 0 associated with and known only to the root PKG;
generating a root key generation parameter Q 0 =s 0 P 0 ; selecting a function H 1 capable of generating an element of the first cyclic group G 1 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 1 (ID 1 , . . . , 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 zi(i−1) +S z(i−1) P zi for 1≦i≦n, wherein S z0 =S 0 , 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 zi P 0 for 1≦i≦n;
generating a recipient public element P z(n+1) =H 1 (ID z1 , . . . , ID z(n+1) ) associated with the recipient, wherein P z(n+1) is an element of the first cyclic group G 1 ; and
generating a recipient private key
S
z
(
n
+
1
)
=
S
zn
+
s
zn
P
z
(
n
+
1
)
=
∑
i
=
1
n
+
1
s
z
(
i
-
1
)
P
zi
associated with the recipient.
2. A method of generating a private key as in claim 1 , wherein:
both the first group G 1 and the second group G 2 are of the same prime order q.
3. A method of generating a private key as in claim 1 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
4. A method of generating a private key as in claim 1 , wherein:
the function ê is an admissible pairing.
5. A method of generating a private key as in claim 1 , wherein:
s 0 is an element of the cyclic group Z/qZ;
Q 0 is an element of the first cyclic group G 1;
each of the public elements P zi is an element of the first cyclic group G 1;
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 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ; and
the recipient private key S z(n+1) is an element of the first cyclic group G 1 .
6. 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 1 of elements and a second cyclic group G 2 of elements;
selecting a function ê capable of generating an element of the second cyclic group G 2 from two elements of the first cyclic group G 1 ;
selecting a root generator P 0 of the first cyclic group G 1 ;
selecting a random root key generation secret s 0 associated with and known only to the root PKG;
generating a root key generation parameter Q 0 =s 0 P 0 ;
selecting a first function H 1 capable of generating an element of the first cyclic group G 1 from a first string of binary digits;
selecting a second function H 2 capable of generating a second string of binary digits from an element of the second cyclic group G 2 ;
generating a public element P zi for each of the n lower-level PKGs, wherein P zi =H 1 (ID 1 , . . . , 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 z(i−1) +S z(i−1) P zi for 1≦i≦n, wherein S z0 =S 0 , 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 zi P 0 for 1≦i≦n;
generating a recipient public element P z(n+1) =H 1 (ID z1 , . . . , ID z(n+1) ) associated with the recipient;
generating a recipient secret element
S
z
(
n
+
1
)
=
S
zn
+
s
zn
P
z
(
n
+
1
)
=
∑
i
=
1
n
+
1
s
z
(
i
-
1
)
P
zi
associated with the recipient;
encoding the message M to generate a ciphertext C using at least the recipient ID-tuple (ID 1 , . . . , ID zi ) and the root key generation parameter Q 0 ; and
decoding the ciphertext C to recover the message M using at least the recipient secret element S z(n+1) .
7. A method of encoding and decoding a digital message M as in claim 6 , wherein:
both the first group G 1 and the second group G 2 are of the same prime order q.
8. A method of encoding and decoding a digital message M as in claim 6 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
9. A method of encoding and decoding a digital message M as in claim 6 , wherein:
the function ê is a bilinear, non-degenerate, and efficiently computable pairing.
10. A method of encoding and decoding a digital message M as in claim 6 , wherein:
s 0 is an element of the cyclic group Z/qZ;
Q 0 is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
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 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ; and
the recipient secret element S z(n+1) is an element of the first cyclic group G 1 .
11. A method of encoding and decoding a digital message M as in claim 1 , wherein:
encoding the message M further includes:
selecting a random parameter r; and
generating the ciphertext C=[U 0 , U 2 , . . . , U n+1 , V], wherein U i =rP zi for i=0 and for 2 ≦i≦n+1, wherein V=M⊕H 2 (g r ), and wherein g=ê(Q 0 , P z1 ); and
decoding the ciphertext C further includes:
recovering the message M, using
m
=
V
⊗
H
2
(
e
^
(
U
0
,
S
z
(
n
+
1
)
)
∏
i
=
2
n
+
1
e
^
(
Q
i
-
1
,
U
i
)
)
.
12. A method of encoding and decoding a digital message M as in claim 11 , wherein:
both the first group G 1 and the second group G 2 are of the same prime order q.
13. A method of encoding and decoding a digital message M as in claim 11 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
14. A method of encoding and decoding a digital message M as in claim 11 , wherein:
the function ê is a bilinear, non-degenerate, and efficiently computable pairing.
15. A method of encoding and decoding a digital message M as in claim 11 , wherein:
s 0 is an element of the cyclic group Z/qZ;
Q 0 is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
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 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ;
the recipient secret element S z(n+1) is an element of the first cyclic group G 1 ;
r is an element of the cyclic group Z/qZ; and
g is an element of the second cyclic group G 2 .
16. A method of encoding and decoding a digital message M as in claim 6 , further comprising:
selecting a third function H 3 capable of generating an integer of the cyclic group Z/qZ from a third string of binary digits; and
selecting a fourth function H 4 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 3 (σ, M, W), wherein W=E H 4 (σ) (M); and
generating the ciphertext C=[U 0 , U 2 , . . . , U n+1 , V, W], wherein U i =rP zi for i=0 and for 2≦i≦n+1, wherein V=σ⊕H 2 (g r ), and wherein g=ê(Q 0 , P z1 ); and
wherein decoding the ciphertext C further includes:
recovering the random binary string σ using
σ
=
V
⊕
H
2
(
e
^
(
U
0
,
S
z
(
n
+
1
)
)
∏
i
=
2
n
+
1
e
^
(
Q
i
-
1
,
U
i
)
)
;
and
recovering the message M using M=E H 4 (σ) −1 (W).
17. A method of encoding and decoding a digital message M as in claim 16 , wherein:
both the first cyclic group G 1 and the second cyclic group G 2 are of the same prime order q.
18. A method of encoding and decoding a digital message M as in claim 16 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
19. A method of encoding and decoding a digital message M as in claim 16 , wherein:
the function ê is a bilinear, non-degenerate, and efficiently computable pairing.
20. A method of encoding and decoding a digital message M as in claim 16 , further comprising:
confirming the internal consistency of the ciphertext C by:
computing an experimental random integer r′=H 3 (σ, M, W); and
confirming that U 0 =r′P 0 and U i =r′P zi for 2≦i≦n+1.
21. A method of encoding and decoding a digital message M as in claim 16 , wherein:
s 0 is an element of the cyclic group Z/qZ;
Q 0 is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
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 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ;
the recipient secret element S z(n+1) is an element of the first cyclic group G 1 ;
r is an element of the cyclic group Z/qZ; and
g is an element of the second cyclic group G 2 .
22. 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 sendery, 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 further comprising:
generating a first cyclic group G 1 of elements and a second cyclic group G 2 of elements;
selecting a function ê capable of generating an element of the second cyclic group G 2 from two elements of the first cyclic group G 1 ;
selecting a root generator P 0 of the first cyclic group G 1 ;
selecting a random root key generation secret s 0 associated with and known only to the root PKG;
generating a root key generation parameter Q 0 =s 0 P 0 ;
selecting a first function H 1 capable of generating an element of the first cyclic group G 1 from a first string of binary digits;
selecting a second function H 2 capable of generating a second string of binary digits from an element of the second cyclic group G 2 ;
generating a public element P yi for each of the m lower-level PKGs, wherein P yi =H 1 (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 1 (ID 1 , . . . , 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 y(i−1) +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 z(i−1) +S z(i−1) P zi for 1≦i≦n, wherein s z0 =s 0 , 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 yi P 0 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 then lower-level PKGs, wherein Q zi =s zi P 0 for 1≦i≦n;
generating a sender public element P y(m+1) =H 1 (ID y1 , . . . , ID y(m+1) ) associated with the sender y;
generating a recipient public element P z(n+1) =H 1 (ID z1 , . . . , ID z(n+1) ) associated with the recipient;
generating a sender secret element
S
y
(
m
+
1
)
=
S
ym
+
s
ym
P
y
(
m
+
1
)
=
∑
i
=
1
m
+
1
s
y
(
i
-
1
)
P
yi
associated with the sender;
generating a recipient secret element
S
z
(
n
+
1
)
=
S
zn
+
S
zn
P
z
(
n
+
1
)
=
∑
i
=
1
n
+
1
s
z
(
i
-
1
)
P
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 yi(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.
23. A method of encoding and decoding a digital message M as in claim 22 , wherein encoding the message M further includes using the lower level key generation parameter Q yl .
24. A method of encoding and decoding a digital message M as in claim 22 , wherein decoding the message M further includes using the lower level key generation parameter Q zl .
25. A method of encoding and decoding a digital message M as in claim 22 , wherein:
both the first cyclic group G 1 and the second cyclic group G 2 are of the same prime order q.
26. A method of encoding and decoding a digital message M as in claim 22 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
27. A method of encoding and decoding a digital message M as in claim 22 , wherein:
the function ê is a bilinear, non-degenerate, and efficiently computable pairing.
28. A method of encoding and decoding a digital message M as in claim 22 , wherein:
s 0 is an element of the cyclic group Z/qz;
Q 0 is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
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 1 ;
each secret element S yi is an element of the first cyclic group G 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
each of the lower-level key generation parameters Q yi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ;
the sender public element P y(m+1) is an element of the first cyclic group G 1 ;
the recipient secret element S z(n+1) is an element of the first cyclic group G 1 ;
the sender secret element S y(m+1) is an element of the first cyclic group G 1 ;
r is an element of the cyclic group Z/qZ; and
g is an element of the second cyclic group G 2 .
29. A method of encoding and decoding a message as in claim 22 :
wherein encoding the message M further includes:
selecting a random parameter r; and
encoding the message M to generate a ciphertext C=[U 0 , U l+1 , . . . , U n+1 , V], wherein U 0 =rP 0 , wherein U i =rP zi for l+1≦i≦n+1, wherein V=M⊕H 2 (g yl r ), and
wherein
g
yi
=
e
^
(
P
0
,
S
y
(
m
+
1
)
)
∏
i
=
l
+
1
m
+
1
e
^
(
Q
y
(
i
-
1
)
,
P
yi
)
decoding the ciphertext C further includes:
recovering the message M using
M
=
V
⊕
H
2
(
e
(
U
0
,
S
z
(
n
+
1
)
)
∏
i
=
l
+
1
n
+
1
e
(
Q
z
(
i
-
1
)
,
U
zi
)
)
.
30. A method of encoding and decoding a digital message M as in claim 29 , wherein:
both the first cyclic group G 1 and the second cyclic group G 2 are of the same prime order q.
31. A method of encoding and decoding a digital message M as in claim 29 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
32. A method of encoding and decoding a digital message M as in claim 29 , wherein:
the function ê is a bilinear, non-degenerate, and efficiently computable pairing.
33. A method of encoding and decoding a digital message M as in claim 29 , wherein:
s 0 is an element of the cyclic group Z/qZ;
Q 0 is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
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 1 ;
each secret element S yi is an element of the first cyclic group G 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
each of the lower-level key generation parameters Q yi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ;
the sender public element P y(m+1) is an element of the first cyclic group G 1 ;
the recipient secret element S z(n+1) is an element of the first cyclic group G 1 ;
the sender secret element S y(m+1) is an element of the first cyclic group G 1 ;
r is an element of the cyclic group Z/qZ; and
g yl is an element of the second cyclic group G 2 .
34. A method of encoding and decoding a digital message M as in claim 22 :
wherein encoding the message M further includes:
selecting a random parameter r; and
encoding the message M to generate a ciphertext C=[U 0 , U l+1 , . . . , U n+1 , V], wherein U 0 =rP 0 , 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 2 (g y(l+1) r ), and wherein
g
y
(
l
+
1
)
=
e
^
(
P
0
,
S
y
(
n
+
1
)
)
∏
i
=
l
+
2
m
e
^
(
Q
y
(
i
-
1
)
,
P
yi
)
=
e
^
(
P
0
,
S
y
(
l
+
1
)
)
;
and
decoding the ciphertext C further includes:
recovering the message M using
M
=
V
⊕
H
2
(
e
^
(
U
0
,
S
z
(
n
+
1
)
)
e
^
(
U
l
+
1
,
Q
zl
)
∏
i
=
l
+
2
n
e
^
(
Q
z
(
i
-
1
)
,
U
i
)
)
.
35. A method of encoding and decoding a digital message M as in claim 22 ,
wherein encoding the message M further includes:
selecting a random parameter r; and
encoding the message M to generate a ciphertext C=[U 0 , U l+2 , . . . , U n , V], wherein U 0 =rP 0 , wherein U i =rP zi for l+ 2 ≦i≦n wherein V=M⊕H 2 (g z(l+1) r ), and wherein
g
z
(
l
+
1
)
=
e
^
(
P
0
,
S
y
(
m
+
1
)
)
e
^
(
Q
yl
,
(
P
z
(
l
+
1
)
-
P
y
(
l
+
1
)
)
)
∏
i
=
l
+
2
m
e
^
(
Q
y
(
i
-
1
)
,
P
yi
)
=
e
^
(
P
0
,
S
z
(
l
+
1
)
)
;
and
decoding the ciphertext C further includes:
recovering the message M using
M
=
V
⊕
H
2
(
e
^
(
U
0
,
S
z
(
n
+
1
)
)
∏
i
=
l
+
2
n
e
^
(
Q
z
(
i
-
1
)
,
U
i
)
)
.
36. A method of encoding and decoding a digital message M as in claim 35 , wherein:
both the first cyclic group G 1 and the second cyclic group G 2 are of the same prime order q.
37. A method of encoding and decoding a digital message M as in claim 35 , wherein:
the first cyclic group G 1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G 2 is a multiplicative subgroup of a finite field.
38. A method of encoding and decoding a digital message M as in claim 35 , wherein:
the function ê is a bilinear, non-degenerate, and efficiently computable pairing.
39. A method of encoding and decoding a digital message M as in claim 35 , wherein:
s 0 is an element of the cyclic group Z/qZ;
Q 0 is an element of the first cyclic group G 1 ;
each of the public elements P zi is an element of the first cyclic group G 1 ;
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 1 ;
each secret element S zi is an element of the first cyclic group G 1 ;
each of the lower-level key generation parameters Q zi is an element of the first cyclic group G 1 ;
each of the lower-level key generation parameters Q yi is an element of the first cyclic group G 1 ;
the recipient public element P z(n+1) is an element of the first cyclic group G 1 ;
the sender public element P y(m+1) is an element of the first cyclic group G 1 ;
the recipient secret element S z(n+1) is an element of the first cyclic group G 1 ;
the sender secret element S y(m+1) is an element of the first cyclic group G 1 ;
r is an element of the cyclic group Z/qZ; and
g yl is an element of the second cyclic group G 2 .
40. A method of encoding and decoding a digital message M as in claim 35 , further comprising:
confirming the internal consistency of the ciphertext C by:
computing an experimental random integer r′=H 3 (σ, M, W); and
confirming that U 0 =r′P 0 and U i =r′P zi for l+1≦i≦n+1.
41. A method of encoding and decoding a digital message M as in claim 22 , further comprising:
selecting a third function H 3 capable of generating an integer of the cyclic group Z/qZ from a third string of binary digits; and
selecting a fourth function H 4 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 3 (σ, M, W), wherein W=E H 4 (σ) (M); and
generating the ciphertext C=[U 0 , 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 2 (g yl r ), and wherein
g
yl
=
e
^
(
P
0
,
S
y
(
m
+
1
)
)
∏
i
=
l
+
1
m
+
1
e
^
(
Q
y
(
i
-
1
)
,
P
yi
)
;
and
wherein decoding the ciphertext C further includes:
recovering the random binary string σ using
σ
=
V
⊕
H
2
(
e
^
(
U
0
,
S
z
(
n
+
1
)
)
∏
i
=
l
+
1
n
+
1
e
^
(
Q
z
(
i
-
1
)
,
U
zi
)
)
;
and
recovering the message M using M=E H 4 (σ) −1 (W).