Multi-proxy signature schemes allow the original signer to delegate his/her signing power to n proxy signers such that all proxy signers must corporately generate a valid proxy signature on behalf of the original signer. We first propose a multi-proxy signature scheme based on discrete logarithms and then adapt it to the elliptic curve cryptosystem. With the integration of self-certified public-key systems and the message recovery signature schemes,our proposed schemes have the following advan-tages:(1) They do not require the signing message to be transmitted,since the verifier can recover it from the signature;(2) The authentication of the public keys,verification of the signature,and recovery of the message can be simultaneously carried out in a single logical step;(3) No certificate is needed for validating the public keys. Further,the elliptic curve variant with short key lengths especially suits the cryptographic applications with limited computing power and storage space,e.g.,smart cards. As compared with the previous work that was implemented with the certificate-based public-key systems,the proposed schemes give better performance in terms of communication bandwidth and computation efforts. Multi-proxy signature schemes allow the original signer to delegate his / her signing power to n proxy signers such that all proxy signers must corporately generate a valid proxy signature on behalf of the original signer. We first propose a multi-proxy signature scheme based on discrete logarithms and then adapt it to the elliptic curve cryptosystem. With the integration of self-certified public-key systems and the message recovery signature schemes, Our proposed schemes have the following advan-tages: (1) They do not require the signing message (2) The authentication of the public keys, verification of the signature, and recovery of the message can be simultaneously carried out in a single logical step; (3) No certificate is needed for validating the public keys. Further, the elliptic curve variant with short key length especially suits the cryptographic applications with limited computing power and storage space, eg, sm art cards. As compared with the previous work that was implemented with the certificate-based public-key systems, the proposed schemes give better performance in terms of communication bandwidth and computation efforts.