Hierarchical identity-based encryption and signature schemes

A computer-implemented encryption method for encrypting a message M for decryption by an intended recipient entity E which is to use secret information obtained using a value or values generated by one or more of E's parents in a hierarchical cryptographic scheme, the method comprising:

• generating a variable value;
• combining the variable value with E's ID to obtain a first ciphertext portion which is independent of the message M but is dependent on E's ID;
• generating a value gr equal to a function of the variable value and a value of a bilinear non-degenerate mapping ê:G1×G1→G2 on two elements one of which is a function of ID's of one or more of E's parents, wherein G1, G2 are groups, the value gr being independent of E's ID;
• generating a second ciphertext portion depending on the message M and the value gr;
• generating a ciphertext which includes the first and second ciphertext portions.

A computer-implemented encryption method comprising:

• obtaining a specification of elements Q0,P0,P1, . . . , Pt of a group G1 and of a non-degenerate bilinear mapping ê:G1×G1→G2 where G2 is a group and t>1;
• obtaining a variable integer value r;
• obtaining a value gr, where g=ê(Q0,Pj) for a selected integer jε[1,t];
• obtaining a message M to be encrypted;
• obtaining a value W1 from gr and M such that W1 incorporates a first encryption of M which is decryptable using gr;
• obtaining values Ui=rPi for at least each iε[0,t] such that i≠j;
• and
• providing a ciphertext C which is an encryption of M, the ciphertext C comprising said values Ui and the value W1.

A computer-implemented decryption method for recovering a message M from a ciphertext C on behalf of an entity E possessing E's secret information obtained using a value or values obtained from one or more of E's parents in a hierarchical cryptographic scheme, E's secret information comprising an element S(E) of a group G1, wherein S(E) is a linear combination of first members of the group G1, each first member being associated with a respective integer coefficient in said linear combination, the first members comprising one or more first elements of the group G1 each of which depends on E's ID, the first members comprising one or more second elements of the group G1 each of which is independent of E's ID, the method comprising:

• (1) computing a value gr from:
• the ciphertext C;
• the element S(E);
• and
• a set of one or more elements Q of the group G1;
• wherein each element Q is independent of the ciphertext C but is dependent on one or more of the first and second elements' coefficients, wherein the value gr does not depend on E's ID but depends on one or more of the second elements' coefficients, the value gr being computed as a function of a ratio A/B, wherein:
• (i) A is a first product of one or more elements of a group G2, the one or more elements of the first product comprising an element which is a value of a bilinear non-degenerate mapping ê:G1×G1→G2 on two elements at least one of which depends on S(E) and at least one of which depends on the ciphertext C;
• and
• (ii) B is a second product of one or more elements of the group G2, the one or more elements of the second product including one or more elements each of which is a value of the mapping ê on two elements at least one of which depends on one or more of the elements Q and at least one of which depends on the ciphertext C;
• (2) using the value gr to recover the message M from C.

A computer-implemented decryption method for a hierarchical decryption system, the method comprising an entity Et at a level t>1 performing operations of:

• obtaining a secret St from a value obtained from an entity Et−1 at level t−1;
• obtaining a specification of a set of elements Qi of a group G1 for at least each integer iε[0,t] such that t>1 and i is not equal to a selected integer jε[1,t−1], and of a non-degenerate bilinear mapping ê:G1×G1→G2 where G2 is a group and t>1;
• obtaining a ciphertext C comprising an element Ui of the group G1 for each iε[0,f] such that i≠j, the ciphertext C also comprising a value W1;
• using each said element Ui and the secret St to compute a value gr defined by
• e
• ^
• ⁡
• (
• U
• 0
• ,
• S
• t
• )
• ∏
• 1
• ≤
• i
• ≤
• t
• ,
• i
• ≠
• j
• ⁢
• ⁢
• e
• ^
• ⁡
• (
• Q
• i
• -
• 1
• ,
• U
• i
• )
• ;
• ⁢
• combining the value gr with the value W1 to recover a message encrypted in the ciphertext C.

A computer-implemented key extraction method for a hierarchical cryptographic scheme comprising a plurality of entities each of which is to be associated with a cryptographic secret value S (“S-value”) which is an element of a group G1, the method comprising, on behalf of an entity Et−1 which is one of said entities and which has a hierarchical level t−1, where t>1 and where a root entity E0 has a hierarchical level 0:

• (1) obtaining a first secret value corresponding to Et−1 from data received from Et−1's immediate parent;
• (2) obtaining Et−1's S-value St−1 from the first secret value corresponding to Et−1;
• (3) for each of Et−1's one or more immediate children Et:
• obtaining a value Pt which is a function of Et's ID and is an element of the group G1;
• generating data incorporating a value St−1+st−1Pt as a first secret value corresponding to Et, where st−1 is a secret value generated by Et−1;
• and
• providing the data incorporating the first secret value St−1+st−1Pt to Et to enable Et to generate Et's secret S-value.