Method and apparatus for generating a cryptographic key

• US 7,397,917 B2
• Filed: 07/03/2003
• Issued: 07/08/2008
• Est. Priority Date: 07/05/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Harrison, Keith Alexander, Soldera, David, Chen, Liqun
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Simitoski; Michael J.
• Application Number:
  US10/613,750
• Publication Number:
  US 20040131191A1
• Time in Patent Office: 1,832 Days
• Field of Search: 380/30, 380/44, 380/286
• US Class Current: 380/44
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• 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/321 involving a third party or a trusted authority

Abstract

A method and apparatus are provided for generating a cryptographic key from multiple data sets each related to a respective association of a trusted party and user identity. The cryptographic key is, for example, one of an encryption key, a decryption key, a signature key and a verification key, and is preferably generated by applying Tate or Weil bilinear mappings to the data sets. At least two of the data sets may relate to different user identities and/or different trusted authorities. Where multiple trusted authorities are involved, these authorities may be associated with different elements to which the bilinear mapping can be applied, each trusted authority having an associated public key formed from its associated element and a secret of that trusted authority.

Claims

1. A method of generating an identifier-based asymmetric cryptographic key concerning a user with which multiple independent user identities are associated, each user identity being intended for use by a respective trusted authority;

the method comprising using computer equipment to apply a bilinear mapping function to process multiple data sets each comprising data related to the user'"'"'s identity with a respective one of the trusted authorities and data related to a secret held by that trusted authority, the secrets of the trusted authorities being unrelated to each other.

2. A method according to claim 1, wherein the cryptographic key is an encryption key, each data set comprising an identity-based public key derived from said user identity, and a public key element of the trusted authority that is based on the secret of the latter.

3. A method according to claim 2, wherein there are n data sets and the encryption key is generated as:

$\underset{1\le <br><br>i\le <br><br>n}{\prod <br><br>}<br><br><br><br>p<br><br>\left(R_{\mathrm{TAi}},r<br><br><br><br>Q_{\mathrm{IDi}}\right)$

where;

p() is said bilinear mapping function,

Q_IDi is the identity-based public key associated with the i^th data set,

R_TAi is the public key element of the trusted authority associated with the i^th data set, and

r is a random number.

4. A method according to claim 1, wherein the cryptographic key is a decryption key, each data set comprising an identity-based private key derived from said user identity and the secret of the trusted authority.

5. A method according to claim 4, wherein there are n data sets and the decryption key is generated as:

$p<br><br>\left(U,\underset{1\le <br><br>i\le <br><br>n}{\sum <br><br>}<br><br><br><br>S_i\right)$

where;

p() is said bilinear mapping function,

Si is the identity-based private key associated with the i^th data set, and

U is an based on a random number and an element of a public key of the trusted authority associated with the i^th data set.

6. A method according to claim 1, wherein the cryptographic key is a signature key, each data set comprising an identity-based private key derived from said user identity and the secret of the trusted authority.

7. A method according to claim 1, wherein the cryptographic key is a verification key, each data set comprising an identity-based public key derived from said user identity, and a public key element of the trusted authority that is based on the secret of the latter.

8. A method according to claim 6, wherein there are n data sets and the signature key is generated as:

$p<br><br>\left(\underset{\left(1\le <br><br>i\le <br><br>n\right)}{\sum <br><br>}<br><br><br><br>d_{\mathrm{IDi}},P\right)$

where;

p() is said bilinear mapping function,

d_IDi is the identity-based private key associated with the i^th data set, and

P is a public key element of the trusted authority associated with the i^th data set.

9. A method according to claim 7, wherein there are n data sets and the verification key is generated as:

$\underset{\left(1\le <br><br>i\le <br><br>n\right)}{\prod <br><br>}<br><br><br><br>p<br><br>\left(Q_{\mathrm{IDi}},P_{\mathrm{pubi}}\right)$

where;

p()is said bilinear mapping function,

Q_IDi is the identity-based public key associated with the i^th data set, and

P_pubi is the public key element of the trusted authority associated with the i^th data set.

10. A method according to claim 1, wherein:

the user identity and trusted authority of each data set are each associated with a respective point on an elliptic curve;

the point associated with the user identity is formed by a map-to-point hash function applied to the user identity, the combination of this point with a secret of the trusted authority forming an identity-based private key; and

the point associated with the trusted authority forms, together with a combination of this point with the secret of the trusted authority, a public key of the trusted authority.

11. A method according to claim 1, wherein the bilinear mapping function pairing is one of a Tate pairing and a Weil pairing.

12. A method according to claim 1, wherein data from the multiple data sets are combined before processing by the bilinear mapping function.

13. A method according to claim 1, wherein data from the multiple data sets are combined after processing by the bilinear mapping function.

14. A computer program product arranged, when installed in computing apparatus, to condition the apparatus for generating an identifier-based asymmetric cryptographic key concerning a user with which multiple independent user identities are associated, each user identity being intended for use by a respective trusted authority, the conditioned apparatus using a bilinear mapping function to process multiple data sets each comprising data related to the user'"'"'s identity with a respective one of the trusted authorities and data related to a secret held by that trusted authority, the secrets of the trusted authorities being unrelated to each other;

data from the multiple data sets being combined either before or after processing by the bilinear mapping function.

15. A computer program product as for generating an identifier-based asymmetric cryptographic key according to claim 14, wherein the cryptographic key is an encryption key, each data set comprising an identity-based public key derived from said user identity, and a public key element of the trusted authority that is based on the secret of the latter.

16. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 15, wherein there are n data sets and the encryption key is generated as:

$\underset{1\le <br><br>i\le <br><br>n}{\prod <br><br>}<br><br><br><br>p<br><br>\left(R_{\mathrm{TAi}},r<br><br><br><br>Q_{\mathrm{IDi}}\right)$

where;

p() is said bilinear mapping function,

Q_IDi is the identity-based public key associated with the i^th data set,

R_TAi is the public key element of the trusted authority associated with the i^th data set, and

r is a random number.

17. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 14, wherein the cryptographic key is a decryption key, each data set comprising an identity-based private key derived from said user identity and the secret of the trusted authority.

18. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 17, wherein there are n data sets and the decryption key is generated as:

$p<br><br>\left(U,\underset{1\le <br><br>i\le <br><br>n}{\sum <br><br>}<br><br><br><br>S_i\right)$

where;

p() is said bilinear mapping function,

S_i is the identity-based private key associated with the i^th data set, and

U is an element based on a random number and an element of a public key of the trusted authority associated with the i^th data set.

19. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 14, wherein the cryptographic key is a signature key, each data set comprising an identity-based private key derived from said user identity and the secret of the trusted authority.

20. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 19, wherein there are n data sets and the signature key is generated as:

$p<br><br>\left(\underset{\left(1\le <br><br>i\le <br><br>n\right)}{\sum <br><br>}<br><br><br><br>d_{\mathrm{IDi}},P\right)$

where;

p() is said bilinear mapping function,

d_IDi is the identity-based private key associated with the i^th data set, and

P is a public key element of the trusted authority associated with the i^th data set.

21. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 14, wherein the cryptographic key is a verification key, each data set comprising an identity-based public key derived from said user identity, and a public key element of the trusted authority that is based on the secret of the latter.

22. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 21, wherein there are n data sets and the verification key is generated as:

$\underset{\left(1\le <br><br>i\le <br><br>n\right)}{\prod <br><br>}<br><br><br><br>p<br><br>\left(Q_{\mathrm{IDi}},P_{\mathrm{pubi}}\right)$

where;

p() is said bilinear mapping function,

Q_IDi is the identity-based public key associated with the i^th data set, and

P_pubi is the public key element of the trusted authority associated with the i^th data set.

23. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 14, wherein:

the user identity and trusted authority of each data set are each associated with a respective point on an elliptic curve;

the point associated with the user identity is formed by a map-to-point hash function applied to the user identity, the combination of this point with a secret of the trusted authority forming an identity-based private key; and

the point associated with the trusted authority forms, together with a combination of this point with the secret of the trusted authority, a public key of the trusted authority.

24. A computer program product for generating an identifier-based asymmetric cryptographic key according to claim 14, wherein the bilinear mapping function pairing is one of a Tate pairing and a Weil pairing.

25. The computer program product of claim 14 wherein data from the multiple data sets are combined before processing by the bilinear mapping function.

26. The computer program product of claim 14 wherein data from the multiple data sets are combined after processing by the bilinear mapping function.

27. A computer apparatus for generating an identifier-based asymmetric cryptographic key concerning a user with which multiple independent user identities are associated, each user identity being intended for use by a respective trusted authority, the computer apparatus using a bilinear mapping function to process multiple data sets each comprising data related to the user'"'"'s identity with a respective one of the trusted authorities and data related to a secret held by that trusted authority, the secrets of the trusted authorities being unrelated to each other.

28. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 27, wherein the cryptographic key is an encryption key, each data set comprising an identity-based public key derived from said user identity, and a public key element of the trusted authority that is based on the secret of the latter.

29. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 28, wherein there are n data sets and the encryption key is generated as:

$\underset{1\le <br><br>i\le <br><br>n}{\prod <br><br>}<br><br><br><br>p<br><br>\left(R_{\mathrm{TAi}},r<br><br><br><br>Q_{\mathrm{IDi}}\right)$

where;

p( ) is said bilinear mapping function,

Q_IDi is the identity-based public key associated with the i^th data set,

R_TAi is the public key element of the trusted authority associated with the i^th data set, and

r is a random number.

30. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 27, wherein the cryptographic key is a decryption key, each data set comprising an identity-based private key derived from said user identity and the secret of the trusted authority.

31. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 30, wherein there are n data sets and the decryption key is generated as:

$p<br><br>\left(U,\underset{1\le <br><br>i\le <br><br>n}{\sum <br><br>}<br><br><br><br>S_i\right)$

where;

p() is said bilinear mapping function,

S_i is the identity-based private key associated with the i^th data set, and

U is an element based on a random number and an element of a public key of the trusted authority associated with the i^th data set.

32. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 27, wherein the cryptographic key is a signature key, each data set comprising an identity-based private key derived from said user identity and the secret of the trusted authority.

33. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 32, wherein there are n data sets and the signature key is generated as:

$p<br><br>\left(\underset{\left(1\le <br><br>i\le <br><br>n\right)}{\sum <br><br>}<br><br><br><br>d_{\mathrm{IDi}},P\right)$

where;

p() is said bilinear mapping function,

d_IDi is the identity-based private key associated with the i^th data set, and

P is a public key element of the trusted authority associated with the i^th data set.

34. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 27, wherein the cryptographic key is a verification key, each data set comprising an identity-based public key derived from said user identity, and a public key element of the trusted authority that is based on the secret of the latter.

35. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 34, wherein there are n data sets and the verification key is generated as:

$\underset{\left(1\le <br><br>i\le <br><br>n\right)}{\prod <br><br>}<br><br><br><br>p<br><br>\left(Q_{\mathrm{IDi}},P_{\mathrm{pubi}}\right)$

where;

p() is said bilinear mapping function,

Q_IDi is the identity-based public key associated with the i^th data set, and

P_pubi is the public key element of the trusted authority associated with the i^th data set.

36. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 27, wherein:

the user identity and trusted authority of each data set are each associated with a respective point on an elliptic curve;

the point associated with the user identity is formed by a map-to-point hash function applied to the user identity, the combination of this point with a secret of the trusted authority forming an identity-based private key; and

the point associated with the trusted authority forms, together with a combination of this point with the secret of the trusted authority, a public key of the trusted authority.

37. A computer apparatus for generating an identifier-based asymmetric cryptographic key according to claim 27, wherein the bilinear mapping function pairing is one of a Tate pairing and a Weil pairing.

38. The computer apparatus of claim 27 wherein data from the multiple data sets are combined before processing by the bilinear mapping function.

39. The computer apparatus of claim 27 wherein data from the multiple data sets are combined after processing by the bilinear mapping function.