  Digital signatures can guarantee the unforgeability and transferability of
the message. Different from classical digital signatures, whose security
depends on computational complexity, quantum digital signatures (QDS) can
provide information-theoretic security. We propose a general method of random
pairing QDS (RP-QDS), which can drastically improve QDS efficiency. In a way,
our random pairing method provide a tightened result of security level of QDS.
In the method, the parity value of each pair is used for the outcome bit value.
We present general formulas for fraction of untagged bits and error rates of
the outcome bits. Random pairing can be applied as a fundamental method to
improve the QDS efficiency for all existing quantum key distribution (QKD)
protocols. We take sending-or-not-sending (SNS) QDS and side-channel-free (SCF)
QDS as examples to demonstrate the advantage of random pairing through
numerical simulation. Similar advantage with random pairing is also founded
with decoy-state MDIQKD and also decoy-state BB84 protocol. We study the
RP-SNS-QDS with finite data size through novel optimization. The numerical
simulation results show that the signature rate can be increased by more than
100% under noisy channel using our random pairing method.
