Guessing probability in Quantum Key Distribution

Flow chart of our method of bounding the guessing probability.

The first Quantum Key Distribution (QKD) protocol has been proposed by Bennett and Brassard in 1984. Since then, the security of QKD has always been the central issue in the quantum cryptographic field. Trace distance is a very important security criterion. It provides the universal composable security, which can guarantee the security of key regardless of its application such as one-time pad (OTP). This is why many studies choose trace distance for the security criterion.

In a classical practical cryptosystem, the impact of guessing probability on security is very important. Specifically, the key generated by the QKD protocol is not based on the presumed hardness of mathematical problems; thus, the eavesdropper Eve can only guess the final key via the measurement result of her probe. The guessing probability intuitively describes the probability that Eve can correctly guess the final key, which can reflect the number of guesses that Eve requires to obtain the final key.

They have been few studies on the guessing probability of QKD. Because there are more rigorous security criterions, such as the trace distance, which gives the composable security. This makes the theoretical foundation for security of QKD crucially important. However, in the real application of QKD projects, customers often ask the question of guessing probability. The existing prior art results cannot give them a satisfactory upper bound. Consequently, some people questioned the security of QKD by relying on the prior art results of guessing probability. For example, according to the existing result, the guessing probability of the ε-secure key is approximately 10−9 if ε is approximately 10−9. From the perspective of guessing probability, the security of the value 10−9 is equivalent to that of a 30 perfect bits. The existing classical computer systems can easily crack such key. In practice, it is not unusual to request a much smaller guessing probability such as 10−100 or 10−1000. Therefore, it is beneficial to find a more tightened upper bound of guessing probability.

On the basis of the existing trace distance result, the researchers have presented a simple and efficient method to tighten the upper bound of the guessing probability. The guessing probability of the final key k can be upper bounded by the guessing probability of another key 𝐤′, if 𝐤′ can be mapped from the final key k. Compared with the known methods, their result is more tightened by thousands of orders of magnitude. For example, given a 10−9-secure key from the sifted key, the upper bound of the guessing probability obtained using our method is 2 × 10−3277. This value is smaller than the existing result 10−9 by more than 3000 orders of magnitude.

Their result shows that from the perspective of guessing probability, the performance of the existing trace distance security is actually much better than what was assumed in the past.

The study has been published in Nature npj.