Patent ID: 8874921

Claim:
A method for digitally signing data, comprising: receiving a plurality of signature generation requests from at least one client computer, wherein each of the plurality of signature generation requests corresponds to a lowest level node of a hash tree structure and comprises a hash computation of at least a data entry and a first tree height tag, said data entry corresponding to a hash computation of a hash sub-tree subordinate to the respective lowest level node, said sub-tree having a number, zero or greater, of hash sub-tree computational levels; determining each first tree height tag as a count of the number of hash sub-tree computational levels represented in the lowest level node representing the respective signature generation request; constructing a hash tree having the plurality of signature generation requests as the lowest-level nodes, a plurality of intermediate nodes comprising successively higher order hash functions of immediately lower level nodes, and a root node corresponding to an aggregate signature request; computing the aggregate signature request as a root hash value as a highest level hash function of highest level intermediate nodes, which in turn correspond to respective computations of hash values of relatively lower level nodes of the hash tree, such that the root hash value and thus the aggregate signature request encodes a hash of all of the signature generation requests; determining an aggregate tree height as a maximum number of hash computational levels from a lowest hash sub-tree computational level to the root node, said maximum number being a function of the sum of at least one of the tree height tags and the number of hash computational levels from the respective lowest level node to the root node; for each lowest level node, computing an implicit tree height tag such that the sum of the corresponding lowest level node's first tree height tag, implicit tree height tag, and the number of hash computational levels from the lowest level node to the root node equals the aggregate tree height tag; and associating the implicit tree height tag with the corresponding lowest level node; computing a multi-signature as a function of the root hash value; for each signature generation request: computing a signature request length value as the sum of the respective tree height tag, the associated implicit tree height tag, and the number of hash computational levels from the corresponding lowest level node to the root; and if the signature request length value does not exceed a height limit, returning to the client computer(s) the multi-signature in response to the signature generation request.