Compact digital signatures

• US 5,638,447 A
• Filed: 05/15/1996
• Issued: 06/10/1997
• Est. Priority Date: 05/15/1996
• Status: Expired due to Term

• Current Assignee: Silvio Micali
• Original Assignee: Silvio Micali
• Inventors: Micali, Silvio
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/648,344
• Time in Patent Office: 391 Days
• Field of Search: 380/9, 380/21, 380/23, 380/25, 380/29, 380/30, 380/49, 380/50
• US Class Current: 713/180
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

Digitally signing data includes collecting a group of signers, each having a public key and a corresponding secret key, a subgroup of signers each producing a partial digital signature of the data, and obtaining a combined signature of the data by combining the partial digital signatures of the data, where the combined digital signature keeps the subgroup of signers accountable for the data for which the subgroup of signers each produce a partial digital signature. Verifying a digital signature of data includes ascertaining members of a subgroup of signers that contributed to provide the digital signature of the data, determining a combined public key corresponding to individual secret keys of a the subgroup of signers, and using the combined public key to verify that the subgroup of signers have each contributed to provide the digital signature of the data.

Claims

1. A method of digitally signing data, comprising the steps of:

(a) selecting a plurality of public keys and corresponding secret keys for a group of signers to provide each member of the group with at least one of the secret keys that is different from an other one of the secret keys provided to an other member of the group;

(b) each signer of a first subgroup of signers producing an individual digital signature of the data relative to one of the public keys;

(c) obtaining a combined digital signature of the data relative to one or more of the public keys by combining individual digital signatures of a second subgroup of signers that is less than the group of signers; and

(d) keeping members of the second subgroup accountable by having the combined digital signature depend on the secret keys of the members of the second subgroup.

2. A method of digitally signing data, according to claim 1, wherein the first subgroup of signers is the entirety of the group of signers.

3. A method for digitally signing data, according to claim 1, wherein the second subgroup is identical to the first subgroup.

4. A method of digitally signing data, according to claim 1, wherein the step of keeping members of the second subgroup accountable includes having the combined digital signature contain information identifying the members of the second subgroup of signers.

5. A method of digitally signing data, according to claim 1, wherein the step of obtaining a combined digital signature includes having the combined digital signature of the data be relative to a verification key that is a combination of the public keys of the members of the second subgroup of signers.

6. A method of digitally signing data, according to claim 5, wherein the step of keeping members of the second subgroup accountable includes having the combined digital signature contain information identifying the members of the second subgroup of signers.

7. A method of digitally signing data, according to claim 1, further comprising the steps of:

(e) predetermining the second subgroup of signers; and

(f) using an individual signature of a member of the first subgroup of signers to obtain a digital signature of the data for the predetermined second subgroup of signers.

8. A method of digitally signing data, according to claim 1, wherein the step of keeping members of the second subgroup accountable includes using the combined digital signature to prove that all the members of the second subgroup of signers provided an individual digital signature of the data.

9. A method of digitally signing data, according to claim 8, further comprising the step of:

(e) choosing the second subgroup to be any one of all possible subsets, of the group of signers, having greater than a predetermined number of members.

10. A method of digitally signing data, according to claim 1, further comprising the step of:

(e) choosing the second subgroup to be any one of all possible subsets, of the group of signers, having greater than a predetermined number of members.

11. A method of digitally signing data, comprising the steps of:

(a) selecting a common public key;

(b) selecting a plurality of individual secret keys for a group of signers to provide each member of the group with at least one of the secret keys that is different from an other one of the secret keys provided to an other member of the group;

(c) each signer of a first subgroup of one or more signers using the corresponding individual secret key to produce a partial digital signature of the data;

(d) combining the partial digital signatures of a second subgroup of signers, less than the group of signers, to provide a combined digital signature of the data relative to the common public key; and

(e) keeping members of the second subgroup accountable by having the combined digital signature depend on the secret keys of the members of the second subgroup.

12. A method of digitally signing data, according to claim 11, wherein the first subgroup of signers is the entirety of the group of signers.

13. A method for digitally signing data, according to claim 11, wherein the second subgroup is identical to the first subgroup.

14. A method of digitally signing data, according to claim 11, wherein the step of keeping members of the second subgroup accountable includes having the combined digital signature contain information identifying the members of the second subgroup of signers.

15. A method of digitally signing data, according to claim 11, wherein the step of obtaining a combined digital signature includes having the combined digital signature of the data be relative to a verification key that is a combination of the public keys of the members of the second subgroup of signers.

16. A method of digitally signing data, according to claim 15, wherein the step of keeping members of the second subgroup accountable includes having the combine digital signature contain information identifying the members of the second subgroup of signers.

17. A method of digitally signing data, according to claim 11, further comprising the steps of:

(e) predetermining the second subgroup of signers; and

(f) using an individual signature of a member of the first subgroup of signers to obtain a digital signature of the data for the predetermined second subgroup of signers.

18. A method of digitally signing data, according to claim 11, wherein the step of keeping members of the second subgroup accountable includes using the combined digital signature to prove that all the members of the second subgroup of signers provided an individual digital signature of the data.

19. A method of digitally signing data, according to claim 18, further comprising the step of;

(e) choosing the second subgroup to be any one of all possible subsets, of the group of signers, having greater than a predetermined number of members.

20. A method of digitally signing data, according to claim 11, further comprising the step of:

(e) choosing the second subgroup to be any one of all possible subsets, of the group of signers, having greater than a predetermined number of members.

21. A method of verifying a digital signature of data, comprising the steps of:

(a) ascertaining members of a subgroup of signers containing a plurality, but not all, members of a group of all possible singers each having one or more secret keys assigned thereto;

(b) determining a combined public key corresponding to the secret keys;

(c) using the combined public key to verify the digital signature; and

(d) keeping members of the subgroup accountable by verifying that the digital signature depends on the secret keys of the subgroup.

22. A method of verifying a digital signature of data, according to claim 21, wherein the step of determining a combined public key includes combining a sequence of individual public keys, each of which corresponds to one of the secret keys.