Cryptanalyzing the efficient identity-based RSA and GQ multisignature schemes

The Harn-Ren and Harn-Ren-Lin identity-based multisignature (IBMS) schemes are schemes derived from the RSA and GQ identity-based signature (IBS) schemes respectively. These IBMS schemes were claimed to be efficient based on two metrics - fixed length and constant verification time. This paper shows that both schemes suffer from similar flaws that allow adversaries to manipulate the list of signatories in a signature, with some of the attacks not requiring the adversaries to even possess valid signer keys. Such flaws render the schemes impractical for use in real-life where it can be safely assumed that they will be used non-atomically. Techniques to address the flaws are also discussed and a solution based on cryptography presented.