Fine-grained forward-secure signature scheme

• US 20060233364A1
• Filed: 07/07/2003
• Published: 10/19/2006
• Est. Priority Date: 07/29/2002
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Camenisch, Jan
• Application Number:
  US10/522,472
• Publication Number:
  US 20060233364A1
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

The presented methods form the basis of a forward-secure signature scheme that is provably secure. Moreover, the presented methods form also the basis of a fine-grained forward-secure signature scheme that is secure and efficient. The scheme allows to react immediately on hacker break-ins such that signatures from the past still remain valid without re-issuing them and future signature values based on an exposed key can be identified accordingly. In general, each prepared signature carries an ascending index such that once an index is used, no lower index can be used to sign. Then, whenever an adversary breaks in, an honest signer can just announce the current index, e.g., by signing some special message with respect to the current index, as part of the revocation message for the current time period. It is then understood that all signatures made in prior time periods as well as all signatures make in the revoked period up to the announced index are valid, i.e., non-reputable.

Claims

1. A method comprising providing a secret cryptographic key and a public cryptographic key applicable in a network of connected computer nodes using a signature scheme, the method being executable by a first computer node and the step of providing comprising the steps of:

generating the secret cryptographic key by

selecting two random factor values,

multiplying the two selected random factor values to obtain a modulus value, and

selecting a secret base value in dependence on the modulus value, wherein the secret base value forms part of the secret cryptographic key;

generating the public cryptographic key by

selecting a number of exponent values, and

deriving a public base value from the exponent values and the secret base value, wherein the public base value and the modulus value form part of the public cryptographic key;

deleting the two random factor values; and

providing the public cryptographic key within the network;

such that the public cryptographic key and at least one of the selected exponent values is usable for verifying a signature value on a message to be sent within the network to a second computer node for verification.

2. The method according to claim 1, further comprising providing a description of the exponent values within the network.

3. The method according to claim 1, further comprising defining an order of the selected exponent values for enabling to communicate the validity of the signature value in the event of a detected intrusion.

9. The method according to claim 1, further comprising applying each of the exponent values to at most one signature value.

10. A computer program element comprising program code means for performing the method of claim 1 when said program is run on a computer.

11. A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform the method according to claim 1.

12. A network device comprising:

a computer program product according to claim 11;

a processor for executing the method;

the processor having access to exchanged messages in the network.

22. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing functions of a network device, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 12.

4. A method comprising providing a signature value on a message in a network of connected computer nodes, the method being executable by a first computer node and the step of providing comprising the steps of:

selecting a first signature element;

selecting a signature exponent value from a number of exponent values; and

deriving a second signature element from a provided secret cryptographic key, the message, and the number of exponent values such that the first signature element, the second signature element, and the signature exponent value satisfy a known relationship with the message and a provided public cryptographic key, wherein the signature value comprises the first signature element, the second signature element, and a signature reference to the signature exponent value,

the signature value being sendable within the network to a second computer node for verification.

5. The method according to claim 4, wherein the step of deriving a second signature element further comprises deriving a signature base value using a provided public cryptographic key, the provided secret cryptographic key, and the exponent values.

6. The method according to claim 4, further comprising deriving a new secret cryptographic key from the provided secret cryptographic key and the selected signature exponent value.

13. The method according to claim 4, further comprising applying each of the exponent values to at most one signature value.

16. A computer program element comprising program code means for performing the method of claim 4, when said program is run on a computer.

17. A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform a method according to claim 4.

7. A method comprising verifying signature value on a message in a network of connected computer nodes, the method being executable by a second computer node and the step of verifying comprising the steps of:

receiving the signature value from a first computer node;

deriving a signature exponent value from the signature value; and

verifying whether the signature exponent value and part of the signature value satisfy a known relationship with the message and a provided public cryptographic key, otherwise refusing the signature value,

wherein the signature value was generated from a first signature element, a number of exponent values, a provided secret cryptographic key, and the message.

14. The method according to claim 7, further comprising applying each of the exponent values to at most one signature value.

18. A computer program element comprising program code means for performing the method of claim 7, when said program is run on a computer.

19. A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform a method according to claim 7.

8. A method comprising communicating within a network of connected computer nodes the validity of a signature value in the event of an exposure of a secret cryptographic key relating to the signature value, the step of communicating comprising the steps of:

defining an order of exponent values;

publishing a description of the exponent values and the order of the exponent values within the network;

publishing a revocation reference to one of the exponent values within the network such that the validity of the signature value is determinable by using the revocation reference, the order of exponent values, and a provided public cryptographic key.

15. The method according to claim 8, further comprising applying each of the exponent values to at most one signature value.

20. A computer program element comprising program code means for performing the method of claim 8, when said program is run on a computer.

21. A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform a method according to claim 8.