Provisional signature schemes

1. A method comprising:

computing, by a computer system, a signature based on a first secret seed and a second secret seed, where computing the signature comprises

generating a first value x i using the first secret seed,

generating a second value c i using the second secret seed, and

computing the signature Sig i =Sig((g x i h i c i ,h i )), where g is a generator point, h i is a value derived from g x i , and

providing the signature Sig i and h i to a server;

subsequent to computing the signature Sig i , creating, by the computer system, a provisional signature by performing an operation on a message, wherein creating the provisional signature comprises

identifying a third value r i that satisfies the following

g m i h i r i =g x i h i c i ,

where m i is the message; and

outputting, by the computer system, the third value r i as the provisional signature to cause the server to complete the provisional signature and to thereby create a final signature (Sig i , h i , m i , r i ) on the message.

2. The method defined in claim 1 wherein completing the provisional signature comprises:

receiving an index i of the provisional signature;

obtaining corresponding values Sig i =Sig((g x i h i c i ,h i )) and h i in response to the index i; and

outputting the final signature (Sig((g x i h i c i ,h i )),h i ,m i ,r i ), where m i is the message and r i is the provisional signature.

3. The method defined in claim 1 further comprising verifying the final signature.

4. The method defined in claim 3 wherein verifying the final signature comprises;

computing g m i h i r i ;

checking VPK(Sig(g x i h i c i ,h i ))=1; and

accepting the final signature in responsive to checking VPK(Sig(g x i h i c i ,h i ))=1 occurs.

5. An apparatus comprising:

a processor to compute a signature by

generating a first value x i using a first secret seed

generating a second value c i using a second secret seed, and

computing the signature Sig i =Sig((g x i h i c i ,h i )), where g is a generator point, h i is a value derived from g x i , and

providing the signature Sig i and h i to a server;

the processor to subsequently generate a provisional signature by

identifying a third value r i that satisfies the following g m i h i r i =g x i h i c i , where m i is the message, and

outputting the third value r i as the provisional signature; and

a network interface coupled to the processor to transmit the provisional signature to a server via a network to cause the server to complete the provisional signature and to thereby create a final signature (Sig i , h i , m i , r i ) on the message.

6. A method comprising:

receiving and storing, by a processor, a signature Sig i and h i associated with an index i, where Sig i =Sig((g x i h i c i ,h i )), g is a generator point, h i is a value derived from g x i , x i and c i , are generated by a pseudo random number generator (PRG) using two different seeds;

subsequently receiving, by the processor, a provisional signature r i on a message m i ;

converting the provisional signature into a final signature by

receiving the index i of the provisional signature,

using the index ito look up corresponding values Sig i and h i , and

outputting the final signature (Sig i , h i , m i , r i ); and

sending, by the processor, the final signature to a network location.

7. An apparatus comprising:

data storage to store a signature Sig i and h i associated with an index i, where Sig i =Sig((g x i h i c i ,h i )), g is a generator point, h i is a value derived from g x i , and c i , are generated by a pseudo random number generator (PRG) using two different seeds;

a network interface to receive the signature Sig i and h i for storage and subsequently receive a provisional signature r i on a message m i ; and

a processor to convert the provisional signature into a final signature by

receiving the index i of the provisional signature;

using the index i to look up corresponding values Sig i and h i ; and

outputting the final signature (Sig i , h i , m i , r i ), wherein the network interface sends the final signature to a network location.