On-line/off-line digital signing - Patent Review 5016274

We claim:

1. A method for enabling a single signer to generate a digital signature of a message using first and second digital signature schemes, each of the digital signature schemes having a key generation algorithm for generating a pair of matching public and secret keys, a signing algorithm which uses the pair of matching public and secret keys to produce a signature with respect to the public key, and a verification algorithm for determining whether the signature produced by the signing algorithm is valid with respect to the public key, comprising the steps of:

(a) computing a signature .SIGMA. of the public key pk of the first digital signature scheme using the signing algorithm S of the second digital signature scheme; and

(b) computing a signature .sigma. of the message using the signing algorithm s of the first digital signature scheme to generate a digital signature of the message, the digital signature comprising a data string (.SIGMA.,.sigma.).

2. The method for generating a digital signature as described in claim 1 further including the steps of enriching the message with a data string to create an enriched message and applying a predetermined differentiating function H to the enriched message prior to computing the signature .sigma..

3. The method for generating a digital signature as described in claim 2 wherein the predetermined differentiating function is the identity function.

4. The method for generating a digital signature as described in claim 2 wherein the predetermined differentiating function is a hashing function and the data string includes one or more of the following: the public key pk, a hashed version of the public key pk, a hashed version of the public key pk enriched with a data string, the signature E, data identifying the signer, data identifying the date of signing, other data or no data.

5. The method for generating a digital signature as described in claim 1 further including the step of enriching the public key with a data string to create an enriched public key prior to computing the signature .SIGMA..

6. The method for generating a digital signature as described in claim 1 wherein the first digital signature scheme is a one-time scheme having a one-time key generation algorithm g, a one-time signing algorithm s and a one-time verification algorithm v.

7. A method for generating and verifying digital signatures using one or more one-time digital signature schemes and a second digital signature scheme, each of the digital signature schemes having a key generation algorithm for generating a pair of matching public and secret keys, a signing algorithm which uses the pair of matching public and secret keys to produce a signature with respect to the public key, and a verification algorithm for determining whether the signature produced by the signing algorithm is valid with respect to the public key, comprising the steps of:

(a) computing a signature .SIGMA. of the public key pk of one of the one-time digital signature schemes using the signing algorithm S of the second digital signature scheme;

(b) storing a data string in a storage area, the data string comprising a pre-computed signature which includes the signature .SIGMA. of the public key pk of the one-time digital signature scheme;

(c) selecting a message m to be signed;

(d) differentiating the message using a predetermined differentiating function H to generate a mapped message;

(e) computing a signature s of the mapped message using the signing algorithm s of the one-time digital signature scheme used in step (a); and

(f) generating a data string (S,s) representing a signature of the message m.

8. The method for generating and verifying digital signatures as described in claim 7 further including the step of:

(g) steps (a)-(f) using a different one-time digital signature scheme for each message selected to be signed.

9. The method for generating and verifying digital signatures as described in claim 7 further including the steps of:

(h) using the verification algorithm V of the second digital signature scheme to determine whether the signature .SIGMA. is the signature of the public key pk in the one-time digital signature scheme;

(i) if the signature .SIGMA. is the signature of the public key pk, using the predetermined differentiating function to generate the mapped message; and

(j) using verification algorithm v of the one-time digital signature scheme used in step (a) to verify that the signature .sigma. is the one-time signature of the mapped message.

10. The method for generating and verifying digital signatures as described in claim 7 wherein the pre-computed signature includes the secret key sk of the one-time digital signature scheme.

11. A method for generating digital signatures using a one-time digital signature scheme and a second digital signature scheme, each of the digital signature schemes having a key generation algorithm for generating a pair of matching public and secret keys, a signing algorithm which uses the pair of matching public and secret keys to produce a signature with respect to the public key, and a verification algorithm for determining whether the signature produced by the signing algorithm is valid with respect to the public key, comprising the steps of:

(a) enriching the public key pk of the one-time signature scheme and using a predetermined differentiating function H' to map the enriched public key into a data string H'(pk);

(b) computing a signature .SIGMA. of the data string H'(pk) using the signing algorithm S of the second digital signature scheme;

(c) selecting a message m to be signed;

(d) enriching the message and using a predetermined differentiating function H to map the enriched message and the data string H'(pk) into a data string H(m,H'(pk));

(e) computing a signature .sigma. of the data string H(m,H'(pk)) using the signing algorithm s of the one-time digital signature scheme; and

(f) generating a data string (.SIGMA.,.sigma.) representing a signature of the message m.

12. A method for generating digital signatures as described in claim 11 further including the step of:

(g) repeating steps (a)-(f) using a different one-time digital signature scheme for each message selected to be signed.

13. A method for enhancing the security of a known digital signature scheme which may be subject to an adaptive chosen plaintext attack, the known digital signature scheme having a key generation algorithm G for generating a pair of matching public and secret keys (PK,SK), a signing algorithm S which uses the pair of matching public and secret keys to produce a signature with respect to the public key PK, and a verification algorithm V for determining whether the signature produced by the signing algorithm is valid with respect to the public key PK, comprising the steps of:

(a) running a key generation algorithm g of a one-time digital signature scheme to generate a one-time public key pk and its associated one-time secret key sk;

(b) computing a signature S of the public key pk of the one-time digital signature scheme using the signing algorithm S of the known digital signature scheme;

(c) storing a data string in a storage area, the data string comprising a pre-computed signature which includes the signature S of the public key pk of the one-time digital signature scheme;

(d) selecting a message m to be signed;

(e) differentiating the message using a predetermined differentiating function H to generate an enriched message;

(f) computing a signature s of the enriched message using the signing algorithm s of the one-time digital signature scheme; and

(g) generating a data string (S,s) representing a signature of the message m.

14. The method for enhancing the security of a known digital signature scheme as described in claim 13 wherein the known digital signature scheme is the Rivest, Shamir and Adleman (RSA) scheme.

15. A method for on-line/off-line digital signing, comprising the steps of:

(a) pre-computing a data string x from a pair of matching public and secret keys of a digital signature scheme such that, for any message m later selected to be signed, a signature of the message m derived from x can be computed substantially faster than the signature of the message m derived from the matching Public and secret keys;

(b) selecting a message m to be signed;

(c) computing a signature .sigma. of the message m using the data string x.

16. The method for on-line/off-line signing as described in claim 15 wherein steps (a) and (c) are carried out by the same signer.

17. The method for on-line/off-line signing as described in claim 16 wherein each data string includes a different Pair of matching public and secret keys.

18. The method for on-line/off-line signing as described in claim 15 wherein steps (a) and (c) are carried out by a different signer.

19. The method for on-line/off-line signing as described in claim 15 wherein step (a) is run to generate a new data string for each message m to be signed.

20. A method for generating a digital signature of a message using first and second digital signature schemes, each of the digital signature schemes having a key generation algorithm, a signing algorithm and a verification algorithm, comprising the steps of:

(a) running the key generation algorithm g of the first digital signature scheme to generate a plurality of public keys and their associated secret keys;

(b) computing a signature .SIGMA. of the plurality of public keys of the first digital signature scheme using the signing algorithm S of the second digital signature scheme;

(c) storing a data string in a storage area, the data string comprising a pre-computed signature which includes the signature E of the plurality of public keys of the first digital signature scheme;

(d) selecting a message m to be signed;

(e) using a predetermined differentiating function H to map the message into a data string H(m);

(f) computing a signature .sigma. of the data string H(m) with respect to one of the public keys pk of the first digital signature scheme using the signing algorithm s of the first digital signature scheme; and

(g) generating a data string (.SIGMA.,.sigma.) representing a signature of the message m.

21. The method for generating a digital signature as described in claim 20 wherein steps (d)-(g) are repeated using a different public key of the first digital signature scheme for each message to be signed.

22. The method for generating a digital signature as described in claim 20 further including the step of hashing the plurality of Public keys prior to comPuting the signature .SIGMA..

23. The method for generating a digital signature as described in claim 22 wherein the data string includes the plurality of public keys to enable verification of the signature .sigma..

24. A method for generating a one-time digital signature of a message ready to be signed, the message having a length n, comprising the steps of:

(a) selecting a predetermined one-way function f which can be composed with itself;

(b) generating k randomly-selected input strings as a one-time secret key, where the number of input strings k is less than the length n of the message;

(c) applying the one-way function f to the input strings of the one-time secret key to generate a one-time public key corresponding to the one-time secret key; and

(d) applying the one-way function f to the input strings of the secret key a predetermined number of times x, where x is polynomial in n, to generate a one-time signature of the message relative to the one-time public key.

25. The method for generating a one-time digital signature as described in claim 24 wherein the input strings of the one-time secret key are selected in psuedo-random manner.

26. A method for generating a one-time digital signature of a message ready to be signed, the message having a length n which is less than or equal to the product (ek) where e and k are integers, comprising the steps of:

(a) selecting a predetermined one-way function f which can be composed with itself;

(b) generating a sequence of randomly-selected inputs r.sub.1, . . . , r.sub.k+1 as a one-time secret key;

(c) using the predetermined one-way function f and the one-time secret key to generate a sequence s.sub.1, . . . , s.sub.k+1 as a one-time public key, where

s.sub.i =f.sup.2.spsp.e (r.sub.i)

for i=0, . . . , k and

s.sub.k+1 =f.sup.k.multidot.2.spsp.e (r.sub.k+1);

(d) selecting a message m to be signed;

(e) dividing the message m into k segments to obtain k e-bit strings m.sub.1, . . . , m.sub.k, each of the strings being an integer between 0 and 2.sup.e ; and

(f) generating a one-time signature of the message m

comprising the sequence .sigma..sub.1, . . . , .sigma..sub.k+1, where

.sigma..sub.i =f.sup.-m i(S.sub.i)

for i=0, . . . , k and

.sigma..sub.k+1 =f.sup.-(k.multidot.2.spsp.e.sup.-(m.sbsp.1.sup.+. . . +m.sbsp.k.sup.)) (s.sub.k+1).

27. A card for use in effecting transactions, comprising:

a body portion;

a memory within said body portion for storing a data string x pre-computed from a pair of matching public and secret keys of a digital signature scheme such that, for any message m later selected to be signed, a signature of the message m derived from x can be computed substantially faster than the signature of the message m derived from the matching public and secret keys; and

means for computing a signature s of the message m using the data string x.

28. A card for use in effecting transactions, comprising:

a body portion;

a memory within said body portion for storing a signature .SIGMA., the signature .SIGMA. being the digital signature of a public key pk of a first digital signature scheme derived by a signing algorithm S of a second digital signature scheme; and

means within the body portion for computing a signature .sigma. of a transaction data message using a signing algorithm s of the first digital signature scheme.

29. A system for allowing authorized users of transaction cards to effect transactions via at least one transaction terminal, comprising:

a plurality of said cards, each of the cards having a memory for storing a data string x pre-computed from a pair of matching public and secret keys of a digital signature scheme such that, for any message m later selected to be signed, a signature of the message m derived from x can be computed substantially faster than the signature of the message m derived from the matching public and secret keys, each card further including means for computing a signature s of the message m using the data string x; and

at least one transaction terminal having means for communicating with the card and for receiving the signature s of the message m computed by the card.

30. The system for allowing authorized users of transaction cards to effect transactions as described in claim 29 wherein the transaction terminal further includes means for generating the message m.

31. A system for allowing authorized users of transaction cards to effect transactions via at least one transaction terminal, comprising:

a plurality of said transaction cards, each of the cards having stored therein a signature .SIGMA. representing the digital sign of a public key pk of a first digital signature scheme derived by a signing algorithm S of a second digital signature scheme, each of the cards further including means for computing a signature .sigma. of a transaction data message using a signing algorithm s of the first digital signature scheme and means for storing a data string (.SIGMA.,.sigma.); and

at least one transaction terminal having means for receiving a card inserted into the transaction terminal, means for communicating with the card inserted into the terminal and means for receiving the signature .sigma. of the message m computed by the card.

32. A terminal for loading data into transaction cards to be used with at least one transaction terminal, each card having a memory therein, comprising:

means for computing a data string x pre-computed from a pair of matching public and secret keys of a digital signature scheme such that, for any message m later selected to be signed, a signature of the message m derived from x can be computed substantially faster than the signature of the message m derived from the matching public and secret keys; and

means for storing the data string x in the memory of an transaction card.

33. A terminal for loading data into transaction cards to be used with at least one transaction terminal, each card having a memory therein, comprising:

means for computing a signature .SIGMA. of the public key pk of a first digital signature scheme using the signing algorithm S of a second digital signature scheme; and

means for storing the signature .SIGMA. in the memory of an transaction card.

Description Submit all comments and votes

TECHNICAL FIELD

The present invention relates generally to message encoding techniques and more Particularly to a new technique for generating digital signatures which enhances the security and the efficiency of known signature schemes

BACKGROUND OF THE INVENTION

Digital signature schemes are well-known in the prior art. In a conventional signature scheme, each user Publishes a public key while keeping a secret key. The user's signature for a message m is a value o which can be efficiently computed with knowledge of the secret key and then verified by anyone using only the known public key. It is hard to forge the user's signature, however, without knowledge of the secret key. One such digital signature scheme is the so-called Rabin scheme wherein a user U publishes a composite number n.sub.U, a product of 2 primes, as his public key, and keeps n.sub.u 's prime factorization as his secret key. The signature of a message (an integer between 1 and n.sub.U and relatively prime with n.sub.U) is then computed. If m is a square modulo n.sub.U, then its signature is .sigma.=.sqroot.m mod n.sub.U. If m is not a square, its signature is a pair (r, s) where .sigma.=.sqroot.m.multidot.r mod n.sub.U and r is a few-bit random number, so that m.multidot.r is a square mod n.sub.U. In Rabin's scheme, as in all currently known digital signature schemes, signing is feasible, though not always efficient, when the length of the public and secret keys are large.

It is also known in the prior art that of the various kinds of attacks that can be mounted by a forger against a signature scheme, the most general is an adaptive chosen plaintext attack. In this type of attack, the forger uses the signer to obtain sample signatures of messages of the forger's choice. The forger's choices are made dependent on the public key and on signatures returned by the user in response to the forger's previous requests. The knowledge gained by the forger can then be used to forge a signature of a message not previously signed or, at worst, to determine the secret key itself. Rabin's scheme, described above, is totally unsecure against an adaptive chosen plaintext attack.

In many applications; e.g., using an so-called "smart.revreaction. or intelligent card to effect commercial transactions, it would be desirable and necessary to be able to generate a digital signature immediately after a message has been chosen. However, because all currently-available signature schemes only compute the signature after selection of the message, digital signing techniques are not presently useful for such real-time applications. One method to overcome this problem would be to use more efficient computational techniques, however, such techniques are prohibitively expensive. Alternatively, the signer must be willing to compute and store the signature of all possible messages before the signing of individual messages takes place. This approach is also impractical.

It would therefore be desirable to have a new approach to digital signing which overcomes these and other problems associated with prior art techniques.

BRIEF SUMMARY OF THE INVENTION

It is an object of the present invention to describe a novel digital signature technique wherein some portion of the message signing routine is carried out "off-line," namely, before the message itself has been chosen.

It is a further object of the invention to provide a method that transforms any ordinary digital signature scheme to one that exploits off-line pre-processing to thereby strengthen the scheme against a chosen plaintext attack.

It is yet another object of the present invention to provide a digital signature schemes in which the signing of a message is broken into two phases. The first or "off-line" phase requires a moderate amount of computation but it presents the advantage that it can be performed leisurely, before the message to be signed is known. Because the message to be signed is not yet chosen, such a computation is, in effect, a "generic" one. The second phase is the so-called "on-line" phase which starts after the message is known and, by cleverly utilizing the "generic computation" of the off-line phase, is much faster than prior art approaches.

It is still a further object of the invention to provide a method for transforming a known digital signature scheme in such a manner that the transformed scheme is invulnerable to chosen plaintext attack even if the underlying scheme is not.

These and other objects of the invention are provided in a method for enabling a single signer to generate a digital signature of a message using first and second digital signature schemes, each of the digital signature schemes having a key generation algorithm for generating a pair of matching public and secret keys, a signing algorithm which uses the pair of matching public and secret keys to produce a signature with respect to the public key, and a verification algorithm for determining whether the signature produced by the signing algorithm is valid with respect to the public key. Generally, the method comprises two (2) basic steps: (a) computing a signature .SIGMA. of the public key pk of the first digital signature scheme using the signing algorithm S of the second digital signature scheme, and (b) computing a signature .sigma. of the message using the signing algorithm s of the first digital signature scheme to generate a digital signature of the message "m", the digital signature comprising a data string .SIGMA.,.sigma.).

Preferably, the first digital signature scheme is a so-called "one-time" scheme which is essentially guaranteed to be secure as long as it is used to sign substantially no more than one message. Therefore, as each new message is selected for signing, preferably a new one-time digital signature scheme is used. Moreover, if desired the signer may enrich (i.e., add to) and/or hash (i.e., decrease the length of) the public key pk and/or the message to create an "enriched" and/or "hashed" public key or message in connection with performing the signature computations. For example, the signer can enrich the message with a data string (comprising the public key pk, a hashed version of the public key pk, a hashed version of the public key pk enriched with a data string, the signature .SIGMA., data identifying the signer, data identifying the date of signing, other data or no data) to create an enriched message. Thereafter, the signer may also apply a predetermined differentiating function H to the enriched message prior to computing the signature .sigma.. Likewise, the signer may enrich the public key with a data string to create an enriched public key prior to computing the signature .SIGMA..

In another method of the invention, a signer runs the key generation algorithm g of a preferably one-time digital signature scheme to generate a plurality of public keys and their associated secret keys. The signer then computes a signature .SIGMA. of the plurality of public keys of the first digital signature scheme using the signing algorithm S of the second digital signature scheme. A data string, comprising a pre-computed signature which includes the signature .SIGMA. of the plurality of public keys of the first digital signature scheme, is then stored to complete an "off-line" phase. After a message m is selected to be signed, the signer uses a predetermined differentiating function H to map the message into a data string H(m) and then computes a signature .sigma. of the data string H(m) with respect to one of the public keys pk of the first digital signature scheme using the signing algorithm s of the first digital signature scheme. The "on-line" phase is completed by compiling a data string (.SIGMA.,.sigma.) representing a signature of the message m. To increase the speed of the off-line phase, the signer may hash the plurality of public keys prior to computing the signature .SIGMA.. If so, the data string representing the signature of the message will include the plurality of public keys or other data to enable verification.

In accordance with yet a further feature of the invention, a method is described for enhancing the security of a known digital signature scheme which may be subject to an adaptive chosen plaintext attack, the known digital signature scheme having a key generation algorithm G for generating a pair of matching public and secret keys (PK,SK), a signing algorithm S which uses the pair of matching public and secret keys to produce a signature with respect to the public key PK, and a verification algorithm V for determining whether the signature produced by the signing algorithm is valid with respect to the public key PK. According to this method, a key generation algorithm g of a one-time digital signature scheme is run to generate a one-time public key pk and its associated one-time secret key sk. This step is equivalent to the signer selecting a one-time secret key and then computing the matching one-time public key therefrom. Thereafter, the method computes a signature .SIGMA. of the public key pk of the one-time digital signature scheme using the signing algorithm S of the known digital signature scheme. A pre-computed signature, which includes at least the signature .SIGMA. of the public key pk of the one-time digital signature scheme, or sufficient data to quickly compute it, is then compiled and stored. This completes a so-called "off-line" phase of the method. In the "on-line" phase, a message m to be signed is selected. Then, a predetermined differentiating function H is used to map the message into an enriched message, and a signature .sigma. of the enriched message is computed using the signing algorithm s of the one-time digital signature scheme. To complete the on-line phase, the signer compiles a data string (.SIGMA.,.sigma.) representing a signature of the message m.

In another embodiment of the invention, a method for on-line/off-line digital signing begins by pre-computing a data string x from a pair of matching public and secret keys of a digital signature scheme such that, for any message m later selected to be signed, a signature of m derived from x can be computed substantially faster than the signature of m derived from the matching public and secret keys. After a message is selected to be signed, the method computes a signature .sigma. of the message using the data string x. The Pre-computation and signature computation steps may be carried out by the same signer or by different signers.

Because the on-line phase preferably uses a "one-time" digital signature scheme, a further feature of the invention is the provision of a unique method for generating a one-time digital signature of a message ready to be signed. This method begins by selecting a predetermined one-way function f and generating k randomly-selected input strings as a one-time secret key, where the number of input strings k is less than the length n of the message m. Thereafter, the signer applies the one-way function f to the input strings of the one-time secret key to generate a one-time public key corresponding to the one-time secret key. To complete the scheme, the signer then applies the one-way function f to the input strings of the secret key a predetermined number of times x, where x is polynomial in n, to generate a one-time signature of the message relative to the one-time public key.

The on-line/off-line digital signature scheme is useful for a number of practical applications. One such application is transaction processing using an "intelligent" credit card or the like. In accordance with a further feature of the invention, a system for allowing authorized users of intelligent cards to effect transactions via at least one transaction terminal is also described. This system includes a plurality of intelligent cards, a loading terminal, and at least one transaction terminal. Each of the cards has a memory for storing a data string x pre-computed (by the loading terminal) from a pair of matching public and secret keys of a digital signature scheme such that, for any message m later selected to be signed, a signature of m derived from x can be computed substantially faster than the signature of m derived from the matching public and secret keys. Each card further includes means for computing a signature .sigma. of the message m using the data string x. The transaction terminal preferably includes means for receiving a card inserted into the transaction terminal, means for communicating with the card inserted into the terminal and means for receiving the signature .sigma. of the message m computed by the card. Alternatively, the transaction terminal may communicate with the card over a communications channel such as a telephone line which may be made cryptographically secure if desired.

The foregoing has outlined some of the more pertinent objects of the present invention. These objects should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial results can be attained by applying the disclosed invention in a different manner of modifying the invention as will be described. Accordingly, other objects and a fuller understanding of the invention may be had by referring to the following Detailed Description of the preferred embodiment.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention and the advantages thereof, reference should be made to the following Detailed Description taken in connection with the accompanying drawings in which:

FIG. 1 is a flowchart of an on-line/off-line digital signature scheme according to the present invention;

FIG. 2 is a detailed flowchart diagram showing the preferred embodiment of the on-line/off-line scheme of FIG. 1 in accordance with the present invention;

FIG. 3 is a schematic diagram of a transaction processing system according to the invention for use in effecting transactions by exploting the on-line/off-line digital signing techniques of FIG. 1; and

FIG. 4 is a flowchart diagram showing a preferred one-time signature scheme according to the teachings of the invention;

Similar reference characters refer to similar steps throughout the several methods shown in the drawings.

DETAILED DESCRIPTION

A prior art digital signature scheme generally has the following components:

* An efficient key generation algorithm G which can be used by any user U to produce a pair (PK, SK) of matching public and secret keys; stated differently, a method for selecting a secret key and computing a matching public key therefrom.

* An efficient signing algorithm S which, given a message m and a pair (PK,SK) of matching public and secret keys, produces a signature s of m with respect to PK.

* An efficient verification algorithm V which, given s, m, and PK, tests whether s is a valid signature for the message m with respect to the public key PK.

Such prior art schemes are enhanced according to the invention by preprocessing in a so-called on-line/off-line manner. In particular, an on-line/off-line digital signature scheme is one in which the signing of a message is broken into two phases. The first phase is "off-line". While the off-line phase requires a reasonable amount of computation, it presents the advantage that it can be performed leisurely, before the message to be signed is known. As the message to be signed is not yet chosen, such a computation is in effect a "generic" one. The second phase is "on-line". It starts after the message is known and, by cleverly utilizing the "generic computation" of the off-line phase, is much faster than prior art approaches.

In the preferred embodiment of the invention, efficient on-line/off-line signature schemes generally combine three main ingredients: an efficient (conventional) signature scheme, an efficient differentiating function, and an efficient one-time signature scheme. The first ingredient has been described above. Regarding the second ingredient, preferably the differentiating function is a hashing function H. A function is differentiating if it is essentially impossible to find two messages that are mapped to the same value. A one-time signature scheme is a signature scheme which is essentially guaranteed to be secure as long as it is used only once; i.e., to sign one message only. This means that an adversary (who does not know the secret key) cannot forge the signature of a message by just looking at the public key and one previously-signed message.

Referring now to FIG. 1, a method for digital signing begins at step 10 wherein the signer selects an agreed-upon underlying signature scheme having a key-generation algorithm G, a signing algorithm S, and a verification algorithm V. The underlying digital signature scheme can be any of a plurality of known signature schemes such as the Rivest, Shamir and Adleman (RSA) scheme. At step 12, the signer runs G to signer keeps the matching secret key, SK, for itself. At step 14, the signer selects H as an agreed upon differentiating function which maps arbitrarily long messages to n-bit long strings. For example, but not by way of limitation, H can be a differentiating hashing function or the identity function. At step 16, the signer selects an agreed-upon one-time signature scheme having an agreed-upon one-time key-generation algorithm g, a one-time signing algorithm s, and a one-time verification algorithm v. The order of steps 10-16 can, of course, be modified by the signer in any convenient manner. Likewise, the signer may group one or more steps into a single step.

Before any message m has been chosen, the signer runs algorithm g at step 18 to randomly select a one-time public key pk and its associated secret key sk for one-time signing a n-bit string. At step 20, the signer computes the underlying signature of pk using the signing algorithm S:

.SIGMA.=S(pk,PK,SK).

Alternatively, the signer may use a predetermined differentiating function to "enrich" (i.e., add to) and/or "hash" (i.e., decrease the length of) the public key pk to create an enriched and/or hashed public key prior to computing the signature .SIGMA. at step 20. At step 22, the signer stores a "pre-computed signature" (.SIGMA.,pk,sk) in a suitable storage area. The pre-computed signature represents a data string having a special property. In particular, for any message "m" later selected to be signed, the signature of the data string can be computed substantially faster than the signature of m derived from the matching public and secret keys. Steps 10-22 represent a so-called "off-line" phase of the method. Thereafter, an "on-line" phase is initiated whenever a message m to be signed is selected at step 24.

At step 26, the signer proceeds to retrieve the precomputed signature from memory. At step 28, the signer may use a predetermined differentiating function to either "enrich" and/or "hash" the message to create an "enriched" and/or "hashed" message. For example, if this function is the identity function, step 28 leaves the message intact. If the signer desires to modify the message, however, it can hash the message to reduce its size and/or it can enrich the message with a data string (e.g., the public key pk, a hashed version of the public key pk, a hashed version of an enriched public key pk, the signature .SIGMA., data identifying the signer, data identifying the date of signing, other data or no data) to create the hashed and/or enriched message.

To complete the on-line phase, the signer continues at step 30 by computing a one-time signature o of the hashed and/or enriched message H(m) using the signing algorithm s:

.sigma.=s(H(m),pk,sk).

The signature of m is then compiled at step 32 as the data string (.SIGMA.,.sigma.). If the signature of m cannot be derived from .sigma., the data string compiled at step 32 must include the public key pk as well.

To verify the signature, t