A number of asymmetrical payment methods have been developed to enable mobile users to buy goods online by charging them to their mobile phone bills by their network operators. It has been recognised that these methods must be used in conjunction with the security services of authentication and non-repudiation of the origin of the request(s) sent from the mobile user so as to prevent fraudulent actions by the network operator or any other entities. This paper presents a novel joint-signature scheme that can be used as one of the security primitives to address the above security services. The scheme will enable mobile users to securely and efficiently instruct their network operators for m-payment related actions. It is based on the use of one-way hash functions and the traditional digital signature method, but in a collaborative manner with the network operator. The joint-signature scheme achieves the same security services as those by a traditional digital signature scheme, i.e. message origin authentication, message integrity and non-repudiation of origin. In comparison with traditional digital signatures our scheme is more efficient at the mobile side in terms of computational cost and in comparison with proxy/server-aided signature schemes it is more efficient in terms of communication cost.