Fine-grained forward-secure signature scheme

• US 8,139,767 B2
• Filed: 05/14/2008
• Issued: 03/20/2012
• Est. Priority Date: 07/29/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Camenisch, Jan, Koprowski, Maciel
• Primary Examiner(s): Truong, Thanhnga B
• Application Number:
  US12/120,349
• Publication Number:
  US 20090316886A1
• Time in Patent Office: 1,406 Days
• Field of Search: 380 28- 30, 380/44, 380277-278, 713/167, 713/180, 705/52, 345/503, 345/522
• 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:

using an apparatus configured to adapt a transmission parameter to a current link quality of a data communication channel to perform 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;

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;

publishing a parameter as part of the public cryptographic key, wherein said parameter sets a time-period during which a user is able to note that the secret cryptographic key was compromised;

using the public cryptographic key and at least one of the selected exponent values usable for verifying a signature value on a message;

sending the message to a second computer node within the network for verification; and

aborting signing of the message when the public cryptographic key has been revoked.

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.

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

5. 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:

using an apparatus configured to adapt a transmission parameter to a current link quality of a data communication channel to perform steps of;

selecting a first signature element;

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

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;

publishing a parameter as part of the public cryptographic key, wherein said parameter sets a time-period during which a user is able to note that the provided secret cryptographic key was compromised;

using the provided public cryptographic key and at least one of the selected exponent values usable for verifying the signature value on the message;

sending the message to a second computer node within the network for verification; and

aborting signing of the message when the public cryptographic key has been revoked.

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

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

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

9. A method comprising verifying a 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:

using an apparatus configured to adapt a transmission parameter to a current link quality of a data communication channel to perform 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;

refusing the signature value when it is determined that the signature exponent value and the part of the signature value do not satisfy a known relationship with the message;

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

publishing a parameter as part of the provided public cryptographic key, wherein said parameter sets a time-period during which a user is able to note that the provided secret cryptographic key was compromised;

using the provided public cryptographic key and at least one of the selected exponent values usable for verifying the signature value on the message;

sending the message to a second computer node within the network for verification; and

aborting signing of the message when the public cryptographic key has been revoked.

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