| Fine-grained forward-secure signature scheme -> Monitor Keywords |
|
|
  Fine-grained forward-secure signature schemeUSPTO Application #: 20060233364Title: Fine-grained forward-secure signature scheme 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. (end of abstract) Agent: Louis Paul Herzberg - Monsey, NY, US Inventor: Jan Camenisch USPTO Applicaton #: 20060233364 - Class: 380044000 (USPTO) Related Patent Categories: Cryptography, Key Management, Having Particular Key Generator The Patent Description & Claims data below is from USPTO Patent Application 20060233364. Brief Patent Description - Full Patent Description - Patent Application Claims
TECHNICAL FIELD [0001] The present invention relates to a method for providing a secret cryptographic key and public cryptographic key applicable in a network of connected computer nodes using a signature scheme. Moreover, the invention relates to methods for providing and verifying a signature value on a message in the network of connected computer nodes. A method for communicating the validity of the generated signature value in the event of a detected intrusion is also disclosed herein. BACKGROUND OF THE INVENTION [0002] Electronic or digital signatures are used to authenticate information, that is to securely tie the contents of an electronic document to a signer, more precisely, to the signer's public key. Only the true signer should be able to produce valid signatures, and anyone should be able to verify them in order to convince oneself that the signer indeed signed the document. While many digital signature schemes have been proposed so far, a few are used in practice today. [0003] Ordinary digital signature schemes suffer from a fundamental shortcoming: once the secret key is leaked, for example because a hacker managed to break into the signer's computer, and, when this leakage is detected, the public key is revoked then all signatures produced by the signer become reputable, i.e., it is no longer possible to distinguish whether a signature was produced by the signer or the hacker. Therefore ordinary signature schemes can pre se not provide non-repudiation. One possibility to achieve non-repudiation is to use a so-called time-stamping service. Here each signature is sent to a trusted third party who signs a message containing the signature and the current date and time. A signature is considered non-reputable if it was time-stamped before the signer revoked her public key. Hence, assuming that the trusted third party's key is never leaked, non-repudiation is guaranteed. However, this solution requires frequent interaction with a trusted third party, e.g., the time-stamping service, which is not desirable. [0004] Another possibility is to change the keys frequently, i.e., to use a different key pair each day and delete all the secret keys of past days. It then is understood that if a day has passed without that the user has revoked that day's key then all the signatures made with respect to the key are non-reputable. This either requires again frequent interaction with the trusted third party, or, the public key becomes large, i.e., a list of many public keys. Forward secure signature schemes as introduced by R. Anderson in "Two remarks on public-key cryptography", Manuscript, presented by the author at the 4th ACM CCS (1997), September 2000, and formalized by Bellare and Miner in "A forward-secure digital signature scheme", In Michael Wiener, editor, Advances in Cryptology--CRYPTO '99, volume 1666 of LNCS, pages 431-448, Springer Verlag, 1999, solve this problem by having only one public key but many secret keys--one for each time period. In fact, most forward secure signature schemes allow one to derive the secret key of the current time period from the one of the previous period in a one-way fashion. [0005] In principle, a forward secure signature scheme can be obtained from any ordinary signature scheme: the signer chooses new secret and public keys for each time period. The public key of the forward secure signature scheme become the set of the ordinary public keys index by the time period for which they are valid. To sign a message the signer uses the secret key of that period. Once a time period has passed, the signer deletes the respective secret key. It is easy to see that this scheme is forward secure. However, the scheme is rather inefficient in terms of (public and secret) storage. [0006] However, current forward secure signature schemes suffer from the following problem. In case of a hacker's break-in all the signatures made in this time-period have to be recalled and the (honest) signer needs to re-issue them. One solution to this is to use small time-periods which only works if the complexity of the key update is comparable to the complexity of signing. [0007] From the above it follows that there is a call for an improved forward secure signature scheme that is more secure and efficient. The scheme should furthermore allow to react on a hacker's break-in immediately without re-issuing signatures for the past. SUMMARY AND ADVANTAGES OF THE INVENTION [0008] In accordance with a first aspect of the present invention, there is given a method for providing a secret cryptographic key sk and a public cryptographic key pk applicable in a network of connected computer nodes using a signature scheme. The method is executable by a first computer node and comprises the steps of generating the secret cryptographic key sk by selecting two random factor values P, Q, multiplying the two selected random factor values P, Q to obtain a modulus value (N), and selecting a secret base value g', h', x' in dependence on the modulus value N, wherein the secret base value g', h', x' forms part of the secret cryptographic key g', h', x'. The method further comprises generating the public cryptographic key pk by selecting a number I of exponent values e.sub.1, . . . , e.sub.I, and deriving a public base value g, h, x from the exponent values e.sub.1, . . . , e.sub.I and the secret base value g', h', x' wherein the public base value g, h, x and the modulus value N form part of the public cryptographic key g, h, x, N. The method further comprises the steps of deleting the two random factor values P, Q; and providing the public cryptographic key g, h, x, N within the network; such that the public cryptographic key g, h, x, N and at least one of the selected exponent values e.sub.1, . . . , e.sub.I is usable for verifying a signature value i, y, a on a message m to be sent within the network to a second computer node for verification. [0009] In a second aspect of the present invention, there is given a method for providing a signature value i, y, a on a message m in a network of connected computer nodes, the method being executable by a first computer node and comprising the steps of selecting a first signature element a; selecting a signature exponent value e.sub.i from a number I of exponent values e.sub.1, . . . , e.sub.I; and deriving a second signature element y from a provided secret cryptographic key g'.sub.i, h'.sub.1, x'.sub.i, the message m, and the number I of exponent values e.sub.1, . . . , e.sub.I such that the first signature element a, the second signature element y, and the signature exponent value e.sub.i satisfy a known relationship with the message m and a provided public cryptographic key g, h, x, N, wherein the signature value i, y, a comprises the first signature element a, the second signature element y, and a signature reference i to the signature exponent value e.sub.i, the signature value i, y, a being sendable within the network to a second computer node for verification. [0010] In a third aspect of the present invention, there is given a method for verifying a signature value i, y, a on a message m in a network of connected computer nodes, the method being executable by a second computer node and comprising the steps of receiving the signature value i, y, a from a first computer node; deriving a signature exponent value e.sub.i from the signature value i, y, a; and verifying whether the signature exponent value e.sub.i and part of the signature value i, y, a satisfy a known relationship with the message m and a provided public cryptographic key g, h, x, N, otherwise refusing the signature value i, y, a, wherein the signature value i, y, a was generated from a first signature element a, a number I of exponent values e.sub.1, . . . , e.sub.I, a provided secret cryptographic key g'.sub.i, h'.sub.i, x'.sub.i, and the message m. [0011] In a fourth aspect of the present invention, there is given a method for communicating within a network of connected computer nodes the validity of a signature value i, y, a in the event of an exposure of a secret cryptographic key sk relating to the signature value i, y, a, the method comprising the steps of defining an order of exponent values e.sub.1, . . . , e.sub.I; publishing a description of the exponent values e.sub.1, . . . , e.sub.I and the order of the exponent values e.sub.1, . . . , e.sub.I within the network; publishing a revocation reference j to one of the exponent values e.sub.1, . . . , e.sub.I within the network such that the validity of the signature value i, y, a is determinable by using the revocation reference j, the order of exponent values e.sub.1, . . . , e.sub.I and a provided public cryptographic key pk. [0012] The presented methods form the basis of a forward-secure signature scheme that is provably secure, i.e., its security relies on no heuristic such as the random oracle model. Moreover, the presented methods form also the basis of a fine-grained forward-secure signature scheme that is secure and efficient. The latter scheme allows one to react immediately on hacker break-ins such that signature values from the past still remain valid without re-issuing them and future signature values based on an exposed key can be identified accordingly. In other words, when using the fine-grained forward-secure signature scheme there is no need to re-sign signature values produced in a current time period in the event of a secret-cryptographic-key exposure. Re-signing is tedious, because it would involve to contact the parties again, and possibly some re-negotiating. [0013] In general, the presented methods form the basis of a forward-secure signature scheme, in which each prepared signature value, also referred to as signature, carries an ascending signature reference i, that also is contemplated as an ascending index i. This index i is attached to the signature value i, y, a in a way such that once it is used, no lower index can be used again 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. [0014] Instead of using time periods, like in ordinary forward-secure signature schemes, the fine-grained forward-secure signature scheme updates the secret cryptographic key whenever a new message is signed. In the event of a break into a signer's system, which can be immediately noticed due to existence of tools called intrusion detection systems, one can revoke the public cryptographic key g, h, x, N and publish the last used index i. Thereby other computer nodes can be informed about the validity of already issued signatures. This prevents other parties form using the exposed provided secret cryptographic key g'.sub.i, h'.sub.i, x'.sub.i to sign while not requiring to re-issue past signatures. [0015] A description of the exponent values e.sub.1, . . . , e.sub.I can be provided within the network. This allows every interested party to verify the validity of the signature. [0016] It can be defined an order of the selected exponent values e.sub.1, . . . , e.sub.I for enabling to communicate the validity of the signature value i, y, a in the event of a detected intrusion. This enables the fine-grained property of the presented scheme. [0017] Each of the exponent values e.sub.1, . . . , e.sub.I can be applied to at most one signature value i, y, a, which allows to provide a secure signature scheme. [0018] A more efficient signature generation can be achieved when the derivation of the signature element y further comprises the step of deriving a signature base value g.sub.i, h.sub.i, x.sub.i by using the provided public cryptographic key g, h, x, N, the provided secret cryptographic key g'.sub.i, h'.sub.i, x'.sub.i, and the exponent values e.sub.1, . . . , e.sub.I. [0019] When a new secret cryptographic key g'.sub.i+1, h'.sub.i+, x'.sub.i+1 is derived from the provided secret cryptographic key g'.sub.i, h'.sub.i, x'.sub.i and the selected signature exponent value e.sub.i, then the advantage occurs that forward security can be achieved. DESCRIPTION OF THE DRAWINGS [0020] Preferred embodiments of the invention are described in detail below, by way of example only, with reference to the following schematic drawings. Continue reading... Full patent description for Fine-grained forward-secure signature scheme Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Fine-grained forward-secure signature scheme patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Fine-grained forward-secure signature scheme or other areas of interest. ### Previous Patent Application: Method and apparatus for composable block re-encryption of publicly distributed content Next Patent Application: Random number generator Industry Class: Cryptography ### FreshPatents.com Support Thank you for viewing the Fine-grained forward-secure signature scheme patent info. IP-related news and info Results in 4.17815 seconds Other interesting Feshpatents.com categories: Novartis , Pfizer , Philips , Polaroid , Procter & Gamble , |
||
