Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme

The focus of this note is the Goldwasser-Micali-Rivest Signature Scheme (presented in the 25th FOCS, 1984). The GMR scheme has the salient property that, unless factoring is easy, it is infeasible to forge any signature even through an adaptive chosen message attack. We present two technical contributions with respect to the GMR scheme: 1)The GMR scheme can be made totally “memoryless’: That is, the signature generated by the signer on message M does not depend on the previous signed messages. (In the original scheme, the signature to a message depends on the number of messages signed before.2)The GMR scheme can be implemented almost as efficiently as the RSA: The original implementation of the GMR scheme based on factoring, can be speeded-up by a factor of |N|. Thus, both signing and verifying take time O(|N|3log2|N|). (Here N is the moduli.)