Digital signatures are often used to authenticate digital data such as documents, messages, financial information, and other data. When a piece of data is digitally signed, a recipient of the data can verify that the data is from a particular sender, known as a signer, and that the data has not been altered since it was signed. A digital signature may also certify when data was created or when the data was sent. Existing digital signature schemes utilize public-key cryptography in which a signer uses a private key to create a digital signature, and a public key that is paired with the private key is used to verify the digital signature. The public key is bound to the identity of the signer using public key certificates that are issued by a trusted Certificate Authority in this public-key infrastructure scheme. A recipient uses the public key certificate to verify the digital signature.
However, there are drawbacks to these existing digital signature schemes. A signer can produce an unlimited number of digital signatures using the private key once it is issued. More importantly, if the private key is stolen, an unauthorized entity can appear as the signer to generate and distribute legitimate digital signatures. In such a case, the legitimate signer can attempt to revoke the private key, but it becomes difficult to determine if any forged signatures were created in the time between the loss of the private key and when the private key was revoked. It also becomes more complicated to verify whether previously created signatures are valid because the private key associated with those signatures has been revoked. Furthermore, existing digital signature schemes rely on the trustworthiness of the Certificate Authority because the creation of the private key is out of the control of the signer. If the Certificate Authority is compromised, the digital signatures that have been created based on the private keys the Certificate Authority has issued would come under suspicion. Accordingly, the signer must place unconditional trust in the Certificate Authority.
Other digital signature schemes attempt to reduce the risk of an unauthorized entity producing digital signatures if the private key is stolen by sharing the private key between the legitimate signer and a server. However, public-key cryptography is still involved in such server-supported digital signature schemes and the private key can still be compromised by an unauthorized entity. Still other digital signature schemes utilize a time-stamping service that attempts to mitigate risk in the time between the loss of a private key and when the private key is revoked. However, this type of scheme only supports public-key infrastructure and its associated risks detailed above. Also, because it may not be known when the private key was lost or stolen, forged signatures may still have been generated before the private key is revoked.
Furthermore, some existing digital signature schemes do not rely on public and/or private keys but utilize signature generation servers that are able to support a single signature request at a time from a client computer. In one scheme, a keyless digital signature service provider operates a top-level signature generation server that is in communication with lower level servers that may be operated by other entities, such as customers of the service provider. The service provider may want to charge the operators of the lower level servers for the signatures generated at the top-level signature generation server. The number of keyless signatures generated at one time may not be easily tracked or limited in this scheme. Checking the total length of a hash chain when verifying a generated signature could be performed to track the number of generated signatures, but would require all customers to have the same maximum limit on the number of generated signatures. The needs of different customers could not be accommodated in this scenario.
Another way to limit the number of signatures generated by the top-level generation server is to include a numerical tag at each step in the hash chain when verifying a generated signature. The limit on the number of generated signatures could be set differently for each customer so that not all customers must have the same maximum limit. When a signature is verified in this scheme, the numerical tags would be checked to ensure that they are in strongly increasing order, i.e., each numerical tag must be greater than the numerical tag from the previous step in the hash chain, in order to verify the signature successfully. However, the customer server may bypass checking the numerical tags in this method to avoid the limitation on the number of generated signatures, while the remainder of the signature would still verify successfully.
The present invention is provided to generate a keyless digital multi-signature based on receiving a plurality of signature generation requests from one or more client computers. By handling multiple signature requests simultaneously, the present invention allows for more efficient and quicker generation of keyless digital signatures. Moreover, the present invention allows limits on the number of signatures that can be generated at a time as a way to track and/or cap the signatures a client computer requests for billing or other purposes. In one embodiment of the present invention, a system and method for generating a keyless digital multi-signature is disclosed in which a plurality of signature generation requests is received at a service provider computer from a client computer. A search tree including a subtree from each of the client computers is constructed. The leaf nodes of the search tree correspond to each of the signature generation requests. The search tree is balanced by assigning explicit length tags to leaf nodes of the search tree as needed. A hash value is computed for each of the nodes in the search tree by applying a hash function to the nodes. The hash value of the root node of the search tree and a search tree height tag make up an aggregate signature request. The aggregate signature request causes an aggregate signature to be created and received at the service provider computer. The aggregate signature is only created if the search tree height tag does not exceed a height limitation. The keyless digital multi-signature for the signature generation requests is generated based on the aggregate signature. An implicit length tag that is empty in the aggregate signature is filled when the keyless digital multi-signature is generated and verified so that the number of signature generation requests is limited. Other features and advantages are provided by the following description and drawings.