Several key-evolving protocols for the Guillou-Quisquater (GQ) signature have been proposed. However, the computational loads are still high, which require the multiplication of several modular exponentiations of at least 1024-bit length. In this paper, we present a low-complexity key-evolving protocol with two additional benefits. First, it ensures the secrecy of other signing keys, even when the signing keys in some periods are compromised. Second, it provides the basic time-stamping service, which is important for legal or notary applications. Related schemes are also compared with our scheme.