Quantum Digital Signatures with Random Pairing

Digital signatures can guarantee the unforgeability and transferability of the message. Differently from classical digital signatures, whose security depends on computational complexity, quantum digital signatures (QDSs) can provide information-theoretic security. We propose a general method of random-pairing QDS, which can drastically increase QDS efficiency. In a way, our random-pairing method provides a tightened result for the 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 the fraction of untagged bits and error rates of the outcome bits. Random pairing can be applied as a fundamental method to increase the QDS efficiency for all existing quantum key distribution (QKD) protocols. We take the QDS with sending-or-not-sending protocol and the QDS with side-channel-free protocol as examples to demonstrate the advantage of random pairing through numerical simulation. A similar advantage with random pairing is also found with decoy-state measurement-device-independent QKD and also the decoy-state BB84 protocol. We study the random-pairing QDS with sending-or-not-sending protocol considering effects of finite data size through optimization. The numerical simulation results show that the signature rate can be increased by more than $100\mathrm{%}$ under a noisy channel using our random-pairing method.