Method of changing key fragments in a multi-step digital signature system

• US 6,411,716 B1
• Filed: 12/23/1998
• Issued: 06/25/2002
• Est. Priority Date: 06/05/1995
• Status: Expired due to Term

• Current Assignee: Certco
• Original Assignee: Certco
• Inventors: Brickell, Ernest F.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US09/219,835
• Time in Patent Office: 1,280 Days
• Field of Search: 380/286, 380/30, 713/180
• US Class Current: 380/286
• 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 method for changing the key fragments held by key fragment members in a k-of-n multi-step digital signature system, comprising:

(a) selecting a subgroup of k of the n key fragment members;

(b) each of the subgroup of key fragment members;

(i) selecting a polynomial of degree k′

−

1, where k′

is not equal to k and is the number of key fragment members needed to generate a digital signature after the change of the key fragments;

(ii) computing n′

values using the selected polynomial, where n′

is the number of key fragment members after the change of the key fragments;

(iii) distributing one of the computed values to each of the n′

key fragment members;

(iv) receiving a computed value from each other member of the subgroup; and

(v) combining the received computed values with one of the generated computed values to form a new key fragment; and

(c) for each of the key fragment members not part of the subgroup deriving a new key fragment from the received computed values.

2. The method of claim 1, further comprising the step of destroying the old key fragments.

3. The method of claim 1, wherein n is less than n′

.

4. The method of claim 3, further comprising the step of destroying the old key fragments.

5. The method of claim 1, wherein n is greater than n′

.

6. The method of claim 5, further comprising the step of destroying the old key fragments.

7. The method of claim 1, wherein n is equal to n′

.

8. The method of claim 7, further comprising the step of destroying the old key fragments.

9. A method for changing a threshold in a threshold cryptosystem comprising:

(a) establishing a threshold cryptosystem having parameters n and k by sharing a secret value among a total number, n, of shareholders in the form of initial shares such that a threshold number, k, of shareholders can perform a cryptographic protocol using initial shares of the secret value without reconstructing the secret value;

(b) establishing a modified threshold cryptosystem having a modified threshold number k, said establishing of a modified threshold cryptosystem accomplished at least in part by selecting a number k of shareholders, and for each of the selected shareholders;

(i) computing n′

new values derived from its key fragment, where n′

is a number of shareholders to hold shares of the secret value in the modified threshold cryptosystem; and

(ii) distributing a computed new value to each of the n′

shareholders;

(c) having each of the n′

shareholders derive a new share of the secret value from the received computed new values such that k′

is the number of shareholders needed to perform the cryptographic protocol, and k′

is changed relative to k; and

(d) having shareholders destroy initial shares of the secret value after deriving new shares of the secret value.

10. A method for changing a threshold in a threshold cryptosystem comprising:

(a) establishing a threshold cryptosystem having parameters n and k by sharing a secret value among a total number, n, of shareholders in the form of initial shares such that a threshold number, k, of shareholders can perform a cryptographic protocol using initial shares of the secret value without reconstructing the secret value;

(b) establishing a modified threshold cryptosystem having a modified threshold number k, said establishing of a modified threshold cryptosystem accomplished at least in part by selecting a number k of shareholders, and for each of the selected shareholders;

(i) computing n′

new values derived from its key fragment, where n′

is a number of shareholders to hold shares of the secret value in the modified threshold cryptosystem; and

(ii) distributing a computed new value to each of the n′

shareholders;

(c) having each of the n′

shareholders derive a new share of the secret value from the received computed new values such that k′

is the number of shareholders needed to perform the cryptographic protocol, and k′

is changed relative to k; and

said distributing a computed new value includes a step of encrypting the computed new value.

11. A method for changing a threshold in a threshold cryptosystem comprising:

(a) establishing a threshold cryptosystem having parameters n and k by sharing a secret value among a total number, n, of shareholders in the form of initial shares such that a threshold number, k, of shareholders can perform a cryptographic protocol using initial shares of the secret value without reconstructing the secret value;

(b) establishing a modified threshold cryptosystem having a modified threshold number k, said establishing of a modified threshold cryptosystem accomplished at least in part by selecting a number k of shareholders, and for each of the selected shareholders;

(i) computing n′

new values derived from its key fragment, where n′

is a number of shareholders to hold shares of the secret value in the modified threshold cryptosystem; and

(ii) distributing a computed new value to each of the n′

shareholders;

(c) having each of the n′

shareholders derive a new share of the secret value from the received computed new values such that k′

is the number of shareholders needed to perform the cryptographic protocol, and k′

is changed relative to k; and

said distributing a computed new value includes a step of signing the computed new value.

12. A method for changing a threshold in a threshold cryptosystem comprising:

(a) establishing a threshold cryptosystem having parameters n and k by sharing a secret value among a total number, n, of shareholders in the form of initial shares such that a threshold number, k, of shareholders can perform a cryptographic protocol using initial shares of the secret value without reconstructing the secret value;

(b) establishing a modified threshold cryptosystem having a modified threshold number k, said establishing of a modified threshold cryptosystem accomplished at least in part by selecting a number k of shareholders, and for each of the selected shareholders;

(i) computing n′

new values derived from its key fragment, where n′

is a number of shareholders to hold shares of the secret value in the modified threshold cryptosystem; and

(ii) distributing a computed new value to each of the n′

shareholders;

(c) having each of the n′

shareholders derive a new share of the secret value from the received computed new values such that k′

is the number of shareholders needed to perform the cryptographic protocol, and k′

is changed relative to k; and

said distributing a computed new value includes encrypting and signing the computed new value.