Multi-step digital signature method and system

• US 20050204129A1
• Filed: 04/12/2005
• Published: 09/15/2005
• Est. Priority Date: 06/05/1995
• Status: Abandoned Application

• Current Assignee: Frank W. Sudia, Peter C. Freund, Stuart T F Huang
• Original Assignee: Frank W. Sudia, Peter C. Freund, Stuart T F Huang
• Inventors: Sudia, Frank W., Freund, Peter C., Huang, Stuart T.F.
• Application Number:
  US11/103,561
• Publication Number:
  US 20050204129A1
• Time in Patent Office: Days
• US Class Current: 713/158
• 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 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

Abstract

A multi-step signing system and method uses multiple signing devices to affix a single signature which can be verified using a single public verification key. Each signing device posesses a share of the signature key and affixes a partial signature in response to authorization from a plurality of authorizing agents. In a serial embodiment, after a first partial signature has been affixed, a second signing device exponentiates the first partial signature. In a parallel embodiment, each signing device affixes a partial signature, and the plurality of partial signatures are multiplied together to form the final signature. Security of the system is enhanced by distributing capability to affix signatures among a plurality of signing devices and by distributing authority us affix a partial signature amond a plurality of authorizing agents.

Claims

1-4. -4. (canceled)

5. A digital signature formed by the steps of:

generating shares of a private signature key;

storing shares in separate electronic signing devices;

certifying multiple authorizing agents for signing devices; and

for each of a plurality of signing devices, affixing a partial signature to an electronic message in response to authorization from a minimum number of authorizing agents;

wherein a plurality of partial signatures constitutes a digital signature.

6. The digital signature of claim 5, wherein said plurality of signing devices affix the plurality of partial signatures to the message in accordance with a method comprising the steps of:

transmitting said message to a first of said plurality of signing devices said first signing device thereafter affixing a first partial signature to said message; and

transmitting said message having said first partial signature to a second of said plurality of signing devices said second signing device thereafter affixing a second partial signature to said message.

7. The digital signature of claim 6, wherein said transmitting step is repeated for each of said plurality of signing devices.

8. The digital signature of claim 7, wherein said plurality of signing devices is a quorum of the signing devices that have stored shares of the private signature key.

9. The digital signature of claim 8, wherein the quorum of signing devices necessary to form said digital signature may be modified while maintaining the same private signature key by redistributing shares of the private signature key in accordance with a method comprising the steps of:

recombining the shares from each of said signing devices to form the private signature key;

generating new shares of the private signature key such that the quorum of shares necessary to form a digital signature is modified as desired; and

storing the new shares in separate electronic signing devices.

10. The digital signature of claim 9, wherein the quorum is modified by increasing the number of partial signatures necessary to form a digital signature.

11. The digital signature of claim 10, wherein the quorum is modified by increasing the number of signing devices.

12. The digital signature of claim 5, wherein a plurality of authorizing agents are assigned to at least one of said electronic signing devices;

and

wherein authorization from a quorum of said plurality of authorizing agents is required for said electronic device to affix said partial signature.

13. The digital signature of claim 5, wherein said plurality of signing devices affix the plurality of partial signatures to the message in accordance with a method comprising the steps of:

transmitting said message separately to each of said plurality of signing devices and affixing a partial signature to said message at each of said plurality of signing devices to form a plurality of messages having partial signatures; and

combining said plurality of messages having partial signatures to form said message having said digital signature.

14. The digital signature of claim 13, wherein said plurality of signing devices is a quorum of said signing devices that have stored shares of the private signature key.

15. The digital signature of claim 5, wherein the digital signature comprises a value derived by combining the plurality of partial signatures.

16. A partial digital signature used in a digital signing method, said digital signing method comprising steps of:

generating shares of a private signature key;

storing shares in separate electronic signing devices;

certifying multiple authorizing agents for signing devices; and

for each of a plurality of signing devices, affixing a partial signature to an electronic message in response to authorization from a minimum number of authorizing agents;

wherein a plurality of partial signatures constitutes a digital signature.

17. The partial signature of claim 16, wherein said plurality of signing devices affix the plurality of partial signatures to the message in accordance with a method comprising the steps of:

transmitting said message to a first of said plurality of signing devices said first signing device thereafter affixing a first partial signature to said message; and

transmitting said message having said first partial signature to a second of said plurality of signing devices said second signing device thereafter affixing a second partial signature to said message.

18. The partial signature of claim 17, wherein said transmitting step is repeated for each of said plurality of signing devices.

19. The partial signature of claim 18, wherein said plurality of signing devices is a quorum of the signing devices that have stored shares of the private signature key.

20. The partial signature of claim 19, wherein the quorum of signing devices necessary to form said digital signature may be modified while maintaining the same private signature key by redistributing shares of the private signature key in accordance with a method comprising the steps of:

recombining the shares from each of said signing devices to form the private signature key;

generating new shares of the private signature key such that the quorum of shares necessary to form a digital signature is modified as desired; and

storing the new shares in separate electronic signing devices.

21. The partial signature of claim 20, wherein the quorum is modified by increasing the number of partial signatures necessary to form a digital signature.

22. The partial signature of claim 21, wherein the quorum is modified by increasing the number of signing devices.

23. The partial signature of claim 16, wherein a plurality of authorizing agents are assigned to at least one of said electronic signing devices;

and

wherein authorization from a quorum of said plurality of authorizing agents is required for said electronic device to affix said partial signature.

24. The partial signature of claim 16, wherein said plurality of signing devices affix the plurality of partial signatures to the message in accordance with a method comprising the steps of:

transmitting said message separately to each of said plurality of signing devices and affixing a partial signature to said message at each of said plurality of signing devices to form a plurality of messages having partial signatures; and

combining said plurality of messages having partial signatures to form said message having said digital signature.

25. The partial signature of claim 24, wherein said plurality of signing devices is a quorum of said signing devices that have stored shares of the private signature key.

26. The partial signature of claim 16, wherein the digital signature comprises a value derived by combining the plurality of partial signatures.