Method for certifying public keys in a digital signature scheme

• US 5,604,804 A
• Filed: 04/23/1996
• Issued: 02/18/1997
• Est. Priority Date: 04/23/1996
• Status: Expired due to Term

• Current Assignee: Assa Abloy AB
• Original Assignee: Silvio Micali
• Inventors: Micali, Silvio
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/636,854
• Time in Patent Office: 301 Days
• Field of Search: 380/9, 380/21, 380/23, 380/25, 380/29, 380/30, 380/49, 380/50
• US Class Current: 713/157
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

A method for certifying public keys of a digital signature scheme in a communications system is provided. The secure communications system is one in which there are at least two levels of authorities. A user presents a piece of data to an intermediate level authority who, upon verifying the data, causes an issuing authority to issue a certificate that the piece of data posses a given property. Although the certificate is compacted by not having it contain a pubic key of the intermediate authority, nonetheless, information is stored in order to keep the intermediate authority accountable.

Claims

1. A method for certifying pieces of data in a system having authorities that certify data, comprising the steps of:

(a) presenting a piece of data requiring certification to a first authority for inspection of a given property;

(b) if the piece of data passes the inspection of the first authority, causing a second authority to receive an indication that the piece of data has passed the inspection of at least the first authority;

(c) having the second authority issue a certificate that the piece of data possesses the given property, the second authority including in the certificate a signature of the second authority and the second authority omitting from the certificate a public key of the first authority; and

(d) storing accountability information that renders at least the first authority accountable for pieces of data that the first authority contributes to certify.

2. A method for certifying, according to claim 1, wherein the piece of data presented is a public key having at least one corresponding secret key associated therewith.

3. A method for certifying, according to claim 2, wherein the given property of the public key includes a given user choosing the public key to be used in connection with at least one of:

a digital signature system and a public key encryption system.

4. A method for certifying, according to claim 3, wherein the inspection by the first authority includes identifying the presenting user.

5. A method for certifying, according to claim 4, wherein the inspection includes verifying that the user knows the secret key that corresponds to the public key.

6. A method for certifying, according to claim 5, wherein the inspection includes checking a digital signature of a given message signed by the user relative to said public key, to determine that the user knows the secret key associated with the public key.

7. A method for certifying, according to claim 5, wherein the inspection includes verifying that the user knows the secret key associated with the public key by having the user decrypt a given message that is encrypted using the public key.

8. A method for certifying, according to claim 1, wherein a certified public verification key of the second authority is sufficient to verify the certificate.

9. A method for certifying, according to claim 1, wherein the piece of data is included in the certificate.

10. A method for certifying, according to claim 9, wherein the second authority contributes additional data that is included in the certificate.

11. A method for certifying, according to claim 1, wherein the accountability information identifies the first authority.

12. A method for certifying, according to claim 1, wherein the accountability information is a digital signature of the first authority.

13. A method for certifying, according to claim 12, wherein the certificate includes a digital signature of the first authority.

14. A method for certifying, according to claim 11, wherein the accountability information indicates the name of the first authority.

15. A method for certifying, according to claim 11, wherein the certificate includes a digital signature of the first authority.

16. A method for certifying, according to claim 1, wherein at least a portion of the accountability information is stored in the certificate.

17. A method for certifying, according to claim 16, wherein all of the accountability information is stored in the certificate.

18. A method for certifying, according to claim 1, wherein the certificate includes a digital signature of the first authority.

19. A method for certifying, according to claim 1, further comprising the step of:

(e) the second authority causing additional information to be saved which, when combined with the accountability information, proves that the first authority contributed to certification of the piece of data.

20. A method for certifying, according to claim 1, further comprising the step of:

(e) a witness causing information to be saved that indicates that the first authority contributed to certification of the piece of data, wherein the information that is saved by the witness is separate from the accountability information and wherein the accountability information is stored in a way to indicate the identity of the witness.

21. A method for certifying, according to claim 20, wherein the information caused to be saved by the witness includes a portion of a digital signature and the accountability information includes an other portion of the digital signature.

22. A method for certifying, according to claim 21, wherein the portions of the digital signature, when combined, prove that the first authority contributed to certification of the piece of data.

23. A method for certifying public keys where there are a plurality of authorities A₁, . . . , A_n that certify data, where each i<

n authority A_i is configured to send authority A_i+1 authenticated messages that are verifiable by A_i+1 as having genuinely come from A_i, and authority A_n has a signing key SK_n and an associated certified public key, PK_n, the method comprising the steps of;

(a) having a verification key PK_U presented to authority A₁ ;

(b) having authority A₁ verify, by means of a predetermined procedure, that PK_U possesses some properties out of a set of given properties;

(c) for all i<

n, having authority A_i send authority A_i+1 a message indicating that PK_U has been verified to possess the given properties;

(d) having A_n issue a certificate for PK_U, A_n including in the certificate a signature provided using SK_n and A_n omitting from the certificate a public key of at least one authority A_j for some j<

n; and

(e) storing accountability information that renders A_j accountable for keys that A_j contributes to certify.

24. A method for certifying, according to claim 23, wherein the certificate does not include a public key of at least one other authority A_k.

25. A method for certifying, according to claim 24, wherein the certificate does not include public keys of any authorities A₁, A₂ . . . A_n-2, A_n-1.

26. A method for certifying, according to claim 25, wherein the certificate does not include a public key for A_n.

27. A method for certifying, according to claim 25, wherein the certificate includes a public key for A_n.

28. A method for certifying, according to claim 23, wherein knowledge of PK_n is sufficient to verify the certificate.

29. A method for certifying, according to claim 23, wherein PK_U is included in the certificate.

30. A method for certifying, according to claim 29, wherein at least one authority A_i, i<

n, contributes additional data that is included in the certificate.

31. A method for certifying, according to claim 30, wherein all authorities contribute additional data that is included in the certificate.

32. A method for certifying, according to claim 23, wherein a digital signature of A_j is included in the certificate.

33. A method for certifying, according to claim 32, wherein digital signatures of all of the authorities are included in the certificate.

34. A method for certifying, according to claim 23, wherein for all i<

n, authority A_i sends authority A_i+1 a digital signature of A_i.

35. A method for certifying, according to claim 34, wherein for all i<

n, authority A_i sends authority A_i+1 a digital signature of A_i along with digital signatures of all previous authorities A_i-1, A_i-2 . . . A₁.

36. A method for certifying, according to claim 35, wherein digital signatures of all of the authorities are included in the certificate.

37. A method for certifying, according to claim 23, wherein the accountability information identifies A_j.

38. A method for certifying, according to claim 37, wherein the accountability information is a digital signature of A_j.

39. A method for certifying, according to claim 37, wherein the accountability information indicates the name of A_j.

40. A method for certifying, according to claim 23, wherein at least a portion of the accountability information is stored in the certificate.

41. A method for certifying, according to claim 40, wherein all of the accountability information is stored in the certificate.

42. A method for certifying, according to claim 23, further comprising the step of:

(f) an authority A_k causing additional information to be saved which, when combined with the accountability information, proves that A_j contributed to the certification of PK_U.

43. A method for certifying, according to claim 42, wherein k>

j.

44. A method for certifying, according to claim 23, further comprising the step of:

(f) a witness causing information to be saved that indicates that A_j contributed to the certification of PK_U, wherein the information that is saved is separate from the accountability information and the accountability information indicates the identity of the witness.

45. A method for certifying, according to claim 44, wherein the information that is caused to be saved by the witness includes a portion of a digital signature and the accountability information includes an other portion of the digital signature.

46. A method for certifying, according to claim 45, wherein the portions of the digital signature, when combined, prove that A_j contributed to the certificate being issued.