Method of identifying invalid digital signatures involving batch verification

A method of identifying invalid sub-batches of digital signatures, where each invalid sub-batch contains at least one invalid digital signature, comprising the steps of:

• a) receiving on an electrical computer a plurality of corresponding digital messages, digital signatures, and signer identifiers;
• b) computing on the electrical computer a value Z0 as a function of the digital messages, the digital signatures, and signer the signer identifiers, where Z0 is an element of a group, and where the group has an identity element;
• c) determining on the electrical computer if the digital signatures, as a batch, are valid for their corresponding digital messages and signer identifiers;
• d) if the digital signatures, as a batch, are valid, then stopping, otherwise proceeding to the next step;
• e) dividing on the electrical computer the received digital signatures into a plurality of user-definable sub-batches of digital signatures;
• f) assigning on the electrical computer a sub-batch identifier to each sub-batch;
• g) setting on the electrical computer w equal to 1;
• h) computing on the electrical computer Zw as a function of the digital messages, the digital signatures, the signer identifiers, and the sub-batch identifiers;
• i) searching on the electrical computer for a multiplicative relationship amongst Z0, Z1, . . . , Zw;
• and
• j) if the multiplicative relationship is found in step (h) then determining on the electrical computer the invalid sub-batches and stopping, otherwise incrementing w and returning to step (h) for additional processing.

A method of identifying invalid digital signatures involving batch verification, comprising the steps of:

• a) receiving on an electrical computer a plurality of corresponding digital messages, digital signatures, and signer identifiers;
• b) computing on the electrical computer a value Z1 as a function of the received digital messages, the digital signatures, and the signer identifiers, where Z1 is an element of a group, and where the group has an identity element;
• c) if Z1 is equivalent to the identity element then determining on the electrical computer that the digital signatures, as a batch, are valid and stopping, otherwise proceeding to step (d);
• d) dividing once electrical computer the digital signatures into a first sub-batch and a second sub-batch;
• e) selecting on the electrical computer the first and second sub-batches;
• f) associating on the electrical computer Z1 with the selected first and second sub-batches;
• g) computing on the electrical computer a value Z2 as a function of the digital messages, the digital signatures, and the signer identifier in the first selected sub-batch;
• h) associating on the electrical computer Z2 with the selected first and second sub-batches, where Z2 is an element of a group, and where the group has an identity element;
• i) if Z2 is equivalent to the identity element of the corresponding group then determining on the electrical computer that the selected first sub-batch is valid and the selected second sub-batch is invalid;
• j) if Z2 is not equivalent to the identity element of the corresponding group but is equivalent to Z1 associated with the selected first and second sub-batches then determining on the electrical computer that the selected first sub-batch is invalid and the selected second sub-batch is valid;
• k) if Z2 is not equivalent to the identity element of the corresponding group and is not equivalent to Z1 associated with the selected first and second sub-batches then determining on the electrical computer that the selected first and second sub-batch are invalid;
• l) if a selected sub-batch is determined to be invalid and the selected sub-batch contains only one digital signature then identifying on the electrical computer the digital signature as invalid;
• m) if the selected first sub-batch is determined to be invalid and contains more than one digital signature then
• (i) dividing on the electrical computer the selected first sub-batch into a third sub-batch of digital messages, digital signatures, and signer identifiers and an associated fourth sub-batch of digital messages, digital signatures, and signer identifiers;
• (ii) associating on the electrical computer, the third and fourth sub-batches resulting from step (i) with Z2;
• and
• (iii) renaming on the electrical computer Z2 as Z1;
• n) if the selected second sub-batch is determined to be invalid and contains more than one digital signature then
• (i) dividing on the electrical computer the selected second sub-batch into a fifth sub-batch sub-batch of digital messages, digital signatures, and signer identifiers and a sixth sub-batch of digital messages, digital signatures, and signer identifiers;
• (ii) computing on the electrical computer a value Z3 as the product of Z1 and the inverse of Z2;
• (iii) associating on the electrical computer the fifth and sixth sub-batches resulting from step (i) with Z3;
• and
• (iv) renaming on the electrical computer Z3 as Z1;
• and
• o) if there is at least one pair of associated first and second sub-batches that have not been selected then selecting on the electrical computer one of such first and second sub-batches, and returning to step (g).