Multi-signcryption scheme is an extension of signcryption scheme for multi-signers performing together the signcryption operation on messages, and it provides useful cryptographic functions such as confidentiality and authenticity for the sound circulation of messages through the Internet. In this paper, we show the weaknesses of the previous multi-signcryption schemes. And then we propose a new multi-signcryption scheme that improves the weaknesses and the efficiency of the previous schemes. Our scheme efficiently provides message flexibility, order flexibility, message verifiability, order verifiability, message confidentiality, message unforgeability, non-repudiation and robustness. Therefore, it is suitable for protecting messages and multi-signers from malicious attacks in the Internet.