The Pintsov-Vanstone signature scheme with partial message recovery (PVSSR) is a signature scheme with low message expansion (overhead) and variable length recoverable and non-recoverable message parts. The scheme uses three cryptographic primitives: a symmetric cipher, hash function and an elliptic curve group. We give three security proofs for PVSSR in this paper. Each proof makes a concrete and necessary assumption about one primitive, and models the other two primitives by idealizations. Thus, PVSSR with a strong cipher may offer greater security than other common variants of ElGamal signatures.