On-line/off-line digital signing

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 Σ 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 σ 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 (Σ,σ).

Claim 2

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 Σ 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 σ 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 (Σ,σ).

Claim 8

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 Σ 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 Σ 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.

Claim 9

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 Σ 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 Σ 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.

Claim 13

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 Σ 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 σ 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 (Σ,σ) representing a signature of the message m.

Claim 14

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 Σ 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 σ 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 (Σ,σ) representing a signature of the message m.

Claim 16

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.

Claim 17

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.

Claim 19

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 σ of the message m using the data string x.

Claim 20

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 σ of the message m using the data string x.

Claim 25

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 Σ 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 σ 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 (Σ,σ) representing a signature of the message m.

Claim 26

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 Σ 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 σ 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 (Σ,σ) representing a signature of the message m.

Claim 30

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.

Claim 31

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.

Claim 33

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 1 , . . . , r 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 1 , . . . , s 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·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 1 , . . . , m k , each of the strings being an integer between 0 and 2 e ; and (f) generating a one-time signature of the message m comprising the sequence σ 1 , . . . , σ k+1 , where σ.sub.i =f.sup.-m i(S.sub.i) for i=0, . . . , k and σ.sub.k+1 =f.sup.-(k·2.spsp.e.sup.-(m.sbsp.1.sup.+. . . +m.sbsp.k.sup.)) (s.sub.k+1).

Claim 34

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 1 , . . . , r 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 1 , . . . , s 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·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 1 , . . . , m k , each of the strings being an integer between 0 and 2 e ; and (f) generating a one-time signature of the message m comprising the sequence σ 1 , . . . , σ k+1 , where σ.sub.i =f.sup.-m i(S.sub.i) for i=0, . . . , k and σ.sub.k+1 =f.sup.-(k·2.spsp.e.sup.-(m.sbsp.1.sup.+. . . +m.sbsp.k.sup.)) (s.sub.k+1).

Claim 39

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.

Claim 40

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.

Claim 42

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 Σ 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 σ of a transaction data message using a signing algorithm s of the first digital signature scheme and means for storing a data string (Σ,σ); 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 σ of the message m computed by the card.

Claim 43

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 Σ 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 σ of a transaction data message using a signing algorithm s of the first digital signature scheme and means for storing a data string (Σ,σ); 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 σ of the message m computed by the card.