Based on both ECDLP and quadratic residue problem,in this paper,we present a new signature scheme with message recovery.We also analyze the security of the new scheme and conclude that the scheme satisfies forward security.In a case of dispute,both the sender and the receiver can convince arbiters whether the signature is valid or not without revealing their secret keys.