Adaptive multi-step digital signature system and method of operation thereof

• US 5,867,578 A
• Filed: 08/19/1996
• Issued: 02/02/1999
• Est. Priority Date: 06/05/1995
• Status: Expired due to Term

• Current Assignee: Certco
• Original Assignee: Certco
• Inventors: Brickell, Ernest F., Sudia, Frank W., Kravitz, David William, Freund, Peter C., Angeles, Patrick J.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/699,579
• Time in Patent Office: 897 Days
• Field of Search: 380/30, 380/23
• US Class Current: 713/180
• CPC Class Codes: G06F 21/40 by quorum, i.e. whereby two or more security principals are required
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures
• CPC Class Codes: H04L 9/3265 using certificate chains, trees or paths; Hierarchical trust model

Abstract

A multi-step digital signature system and method is provided having a distributed root certifying authority 20. Messages received at the root certifying authority 20 are distributed to root certifying authority members 22-30 who attach partial signatures to the message using root key fragments. In the system and method provided, the system adapts to system events such as the addition or removal of key fragment holders, the need to modify key fragments, etc., by changing key fragments.

Claims

1. A multi-step digital signature system, comprising:

a distributed certifying authority;

said distributed certifying authority including a plurality of certifying authority members, wherein approval of a plurality of said plurality of certifying authority members is required to generate a digital signature for the distributed certifying, authority, wherein at least one of said plurality of certifying authority members includes an input device for receiving instructions from a plurality of signing officers.

2. The multi-step digital signature system of claim 1, wherein said instructions from said plurality of signing officers permit said certifying authority member to generate a digital signature.

3. The multi-step digital signature system of claim 2, wherein approval from a quorum of the plurality of signing officers is required before the certifying authority member is approved to generate a digital signature.

4. The multi-step digital signature system of claim 1, wherein said instructions from said plurality of signing officers direct a change in the signing protocol for the certifying authority member.

5. The multi-step digital signature system of claim 4, wherein approval from a quorum of the plurality of signing officers is required before the certifying authority member is approved to generate a digital signature.

6. A multi-step digital signature system, comprising

a distributed certifying authority,

said distributed certifying authority including a plurality of certifying authority members, wherein approval of a plurality of said plurality of certifying authority members is required to generate a digital signature for the distributed certifying, authority, wherein said distributed certifying authority is one of a plurality of certifying authorities communicating to form a plurality of hierarchical certifying tiers, wherein at least one of said plurality of certifying authority members of said distributed certifying authority includes an input device for receiving instructions from a plurality of signing officers.

7. The multi-step digital signature system of claim 6, wherein said instructions from said plurality of signing officers permit said certifying authority member to generate a digital signature.

8. The multi-step digital signature system of claim 7, wherein approval from a quorum of the plurality of signing officers is required before the certifying authority member is approved to generate a digital signature.

9. The multi-step digital signature system of claim 6, wherein said instructions from said plurality of signing officers direct a change in the signing protocol for the certifying authority member.

10. The multi-step digital signature system of claim 9, wherein the signing protocol for the certifying authority member may be changed to increase the number of signing officers.

11. The multi-step digital signature system of claim 9, wherein the signing protocol for the certifying authority member may be changed to decrease the number of signing officers.

12. The multi-step digital signature system of claim 9, wherein approval from a quorum of the plurality of signing officers is required before the certifying authority member is approved to generate a digital signature.

13. A method for decreasing the verification chain length in a hierarchical digital signature system, comprising the steps of:

obtaining a signature certificate for a user from a certifying authority at a first tier of said hierarchical digital signature system;

presenting said signature certificate from said first tier certifying authority to a higher tier certifying authority;

receiving, from said higher tier certifying authority, a certificate authenticating the signature of the first tier certifying authority; and

presenting said authenticating certificate of said higher tier certifying authority from a user to a verifier.

14. A method of generating a digital signature in a n-of-n multi-step digital signature system having n certifying authority members in a distributed certifying authority, comprising the steps of:

receiving, at said distributed certifying authority, a message (m) to be signed;

distributing said message to each of said n certifying authority members;

preparing separate messages (HASHr), at each of said certifying authority members, in accordance with a method including the following steps;

selecting a random number (k);

calculating a value (r) from said random number (k) using the function

space="preserve" listing-type="equation">r=g.sup.kD(m, HASH) mod p;

calculating the HASH of said r value to obtain HASHr;

distributing said HASHr values such that the HASHr value prepared by each certifying authority member is received by each of the other n-1 certifying authority members;

distributing said r values such that the HASHr value prepared by each certifying authority member is received by each of the other n-1 certifying authority members;

confirming, at each of the certifying authority members, the r values for each of the other n-1 certifying authority members using the function SHA(r)=HASHr;

computing, at each of the certifying authority members, a composite r value as the product of all of the r values;

computing, at each of the certifying authority members, a signature fragment value using the composite r value.

15. A method of generating a digital signature in a n-of-n multi-step digital signature system having n certifying authority members in a distributed certifying authority, comprising the steps of:

receiving, at said distributed certifying authority, a message (m) to be signed;

distributing said message to each of said n certifying authority members;

computing a separate value (r), at each of said certifying authority members, in accordance with a method including the following steps;

selecting a random number (k);

calculating a value (r) from said random number (k) using the function

space="preserve" listing-type="equation">r=g.sup.kD(m, HASH) mod p;

providing evidence that the discrete log of r mod p is known;

distributing said evidence such that the evidence of each certifying authority member is received by each of the other n-1 certifying authority members;

distributing said r values such that the r value computed by each certifying authority member is received by each of the other n-1 certifying authority members;

verifying, at each of the certifying authority members, the evidence to confirm the knowledge of the discrete log of the r values of each of the other n-1 certifying authority members;

computing, at each of the certifying authority members, a composite r value as the product of all of the r values;

computing, at each of the certifying authority members, a signature fragment value using the composite r value.

16. In a k-of-n multi-step digital signature system, a method of identifying the k members that participated in generating a signature, comprising the steps of:

appending a set of n bits to the end of the message to be signed wherein each of said n bits is associated with one of said n members of the k-of-n multi-step digital signature system;

indicating with said n bits which k members participated in generating said signature.

17. The method of claim 16, wherein said indicating step includes indicating with a logic high the k members who participated in generating said signature and indicating with a logic low said members who did not participate.