Quantum digital signature (QDS) is based on the laws of quantum physics, and can provide unconditional security for signing messages between remote multi-party users. To date, different QDS protocols have been proposed and corresponding security analysis has been done. Just most security analyses are directed against signing single-bit messages, and the security cannot be ensured when signing multi-bit messages if one simply puts blocks together. Recently, T.Y. Wang et al. analyzed the security under this situation and gave a solution for eliminating potential eavesdropping attacks. However, its efficiency is relatively low since they need to consume more than 2n-bit signatures to sign a classical n-bit message. In this paper, we propose a high efficient approach for signing multi-bit messages. As a result, the efficiency can be improved with 36.92% when signing a 128-bit message compared with using T.Y. Wang et al.’s method. And the improvement is even larger when signing longer messages.