Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.12075 · npj Quantum Information

Guessing probability in quantum key distribution

Xiang‐Bin Wang, Jing-Tao Wang, Ji-Qian Qin, Cong Jiang, Zong‐Wen Yu

Published May 22, 2020• 14 citations
arXivHTMLPDF

Abstract

Abstract On the basis of the existing trace distance result, we present 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 $${\bf{k}}^{\prime}$$ k ′ , if $${\bf{k}}^{\prime}$$ k ′ can be mapped from the final key k. Compared with the known methods, our 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. Our 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.

DOI
10.1038/s41534-020-0267-3

Related papers

A simple relation of guessing probability in quantum key distribution

Hong-Yi Su

Abstract Given a communication system using quantum key distribution (QKD), the receiver can be seen as one who tries to guess the sender’s information just as potential eavesdroppers do. The receiver-eavesdropper similarity thus implies a simple relation in terms of guessing probability and correctness of sifted keys, related with the distance-based, information-theoretic security. The tolerable regions of error rates determined by such a guessing-probability-based relation are shown to be close to those determined by security criteria. Thus, an alternative perspective on applying guessing probability in analyzing QKD issues is here provided. Examples of two specific protocols are illustrated. Our results contribute to evaluating an important element in communication study, and may provide useful reference for the security analysis of QKD protocols.

arXiv:2112.11783•New Journal of Physics•Aug 26, 2022•4 citations

Security of Quantum Key Distribution from Attacker's View

Takehisa Iwakoshi

In 2005, trace distance between an ideal quantum state to be distributed and an actual quantum state distributed was introduced as a valid security measure of Quantum Key Distribution (QKD) by R. Renner et al., then it has been perceived that the trace can be interpreted as a maximum failure probability of QKD. While such a perspective has been widely accepted, H. P. Yuen and O. Hirota have been warning that such an interpretation is not correct since 2009. The author of this study has been giving questions on the interpretation of the trace distance based on their criticisms since QIT30 in May 2014, and has been proposing Yuen's idea to evaluate the security of QKD by the probability for the attacker to guess the correct key. However, the author could not give the guessing probability concretely. In this study, the author explains how to derive the average guessing probability for the attacker, where its result equals to Yuen's derivation firstly seen in 2010. From this result, one will see the problems with the maximum failure probability interpretation of the trace distance clearly. This study also explains the indistinguishability advantage interpretation is also invalid.

arXiv:1711.03619•Jan 1, 2015•1 citation

Incompleteness and Limit of Quantum Key Distribution Theory

Osamu Hirota

It is claimed in the many papers that a trace distance ($d$) guarantees the universal composition security in quantum key distribution (QKD). In this introduction paper, at first, it is explicitly explained what is the main misconception in the claim of the unconditional security for QKD theory. In general terms, the cause of the misunderstanding on the security claim is the Lemma in the paper of Renner. It suggests that the generation of the perfect random key is assured by the probability $ (1-d)$, and its failure probability is $d$. Thus, it concludes that the generated key provides the perfect random key sequence when the protocol suceeds. So the QKD provides perfect secrecy to the one time pad. This is the reason for the composition claim. However, the quantity of the trace distance (or variational distance) is not the probability for such an event. If $d $ is not small enough, always the generated key sequence is not uniform. Now one needs the reconstruction of the evaluation of the trace distance if one wants to use it. One should first go back to the indistinguishability theory in the computational complexity based, and to clarify the meaning of the value of the variational distance. In addition, the same analysis for the information theoretic case is necessary. The recent serial papers by H.P.Yuen have given the answer on such questions. In this paper, we show more concise description of Yuen's theory, and clarify that the recent upper bound theories for the trace distance by Tomamichel et al and Hayashi et al are constructed based on the reasoning of Renner and it is unsuitable as the analysis for information theoretic security. Finally, we introduce a macroscopic quantum communication with different principle to replace Q-bit QKD.

arXiv:1208.2106•Aug 10, 2012•20 citations

Quantum entanglement and composite keys in quantum cryptography

S. N. Molotkov

The security of quantum cryptography protocols after a quantum key distribution (QKD) session is formulated in terms of proximity between two situations: quantum states corresponding to real and ideal situations after QKD. The measure of proximity is the trace distance. It is more reasonable to formulate security directly in terms of the smallness of probability of successive guessing of keys by an eavesdropper after an arbitrary number of QKD sessions. There is a fundamental question the answer to which is a priori very unobvious: Is the security criterion in terms of the proximity of the real and ideal situations for a single QKD session sufficient to guarantee the security of keys in terms of the smallness of probability of guessing of keys by the eavesdropper after an arbitrary number of QKD sessions? It has been shown that the answer to this question is positive.

Journal of Experimental and Theoretical Physics Letters•Jun 1, 2017•2 citations

Informed guessing of an eavesdropper's Renyi entropy

John M. Myers, Tai Tsun Wu

Users of a quantum cryptographic system face a problem of deciding on the ignorance of a maximally adroit eavesdropper concerning their key material. It is known that there can be no sure, positive, lower bound on any plausible measure of ignorance, and for this reason we characterize the problem as the making of an informed guess, meaning a guess that employs a rule that can be shown to work except in unlikely cases. As the measure of an eavesdropper's ignorance concerning n bits of sifted key material less some number k of bits found in error and discarded, we analyze Renyi entropy of arbitrary order R, for 1 ≤ R ≤ 2. We offer a rule for deciding on Renyi entropy based on a tighter bound on the relevant probability distributions than has been available. To this end, we employ a recently derived approximation to the cumulative binomial distribution which is uniformly accurate over a larger domain than previously available approximations. This results in a longer distilled key than that obtained from looser bounds, as well as generalizing the order R. Some numerical examples are presented.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 5, 2003•0 citations

Bit-error-rate guarantee for quantum key distribution and its characteristics compared to leftover hash lemma

Takehisa Iwakoshi

The trace distance criterion for security of Quantum Key Distribution (QKD) has been widely perceived that its upperbound is the maximum failure probability in distributing an ideal quantum state that the quantum system shared by legitimate users is decoupled from the quantum system the eavesdropper possesses, therefore the eavesdropper would not obtain any hints on the key shared by the legitimate users no matter how much her measurement is optimal. However, there an arbitrariness in the definition of the trace distance with the decoupled quantum system the eavesdropper possesses as the previous work pointed out, and such an arbitrariness would be confusions in guaranteeing the security of QKD. In this work, from the framework of Bit-Error-Rate (BER) Guarantee discussed also in the previous work, such an arbitrariness is removed from the definition of the trace distance criterion by discussing the similarities and differences between the security of QKD and classical information-theoretic cryptography by Leftover Hash Lemma (LHL). However, in the previous work BER Guarantee was derived under the assumption that the eavesdropper launches the weakest class of attack, so-called “Individual Attacks.” Therefore, it is still unknown whether direct upper-bounding of the term would give tighter upper-bound in general, such as “Collective Attacks” or “Coherent Attacks”, compared to the upper-bound by LHL, as well as the secure-key generation rate. This study also revisits the security proof of QKD given by P. Shor and J. Preskill in 2000.

SPIE Quantum Information Science and Technology•Oct 8, 2018•2 citations
Abstract On the basis of the existing trace distance result, we present 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 k′{\bf{k}}^{\prime}k′ k ′ , if k′{\bf{k}}^{\prime}k′ k ′ can be mapped from the final key k. Compared with the known methods, our 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. Our 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.
Abstract Given a communication system using quantum key distribution (QKD), the receiver can be seen as one who tries to guess the sender’s information just as potential eavesdroppers do. The receiver-eavesdropper similarity thus implies a simple relation in terms of guessing probability and correctness of sifted keys, related with the distance-based, information-theoretic security. The tolerable regions of error rates determined by such a guessing-probability-based relation are shown to be close to those determined by security criteria. Thus, an alternative perspective on applying guessing probability in analyzing QKD issues is here provided. Examples of two specific protocols are illustrated. Our results contribute to evaluating an important element in communication study, and may provide useful reference for the security analysis of QKD protocols.
In 2005, trace distance between an ideal quantum state to be distributed and an actual quantum state distributed was introduced as a valid security measure of Quantum Key Distribution (QKD) by R. Renner et al., then it has been perceived that the trace can be interpreted as a maximum failure probability of QKD. While such a perspective has been widely accepted, H. P. Yuen and O. Hirota have been warning that such an interpretation is not correct since 2009. The author of this study has been giving questions on the interpretation of the trace distance based on their criticisms since QIT30 in May 2014, and has been proposing Yuen's idea to evaluate the security of QKD by the probability for the attacker to guess the correct key. However, the author could not give the guessing probability concretely. In this study, the author explains how to derive the average guessing probability for the attacker, where its result equals to Yuen's derivation firstly seen in 2010. From this result, one will see the problems with the maximum failure probability interpretation of the trace distance clearly. This study also explains the indistinguishability advantage interpretation is also invalid.
It is claimed in the many papers that a trace distance (ddd) guarantees the universal composition security in quantum key distribution (QKD). In this introduction paper, at first, it is explicitly explained what is the main misconception in the claim of the unconditional security for QKD theory. In general terms, the cause of the misunderstanding on the security claim is the Lemma in the paper of Renner. It suggests that the generation of the perfect random key is assured by the probability $ (1-d)$, and its failure probability is ddd. Thus, it concludes that the generated key provides the perfect random key sequence when the protocol suceeds. So the QKD provides perfect secrecy to the one time pad. This is the reason for the composition claim. However, the quantity of the trace distance (or variational distance) is not the probability for such an event. If $d $ is not small enough, always the generated key sequence is not uniform. Now one needs the reconstruction of the evaluation of the trace distance if one wants to use it. One should first go back to the indistinguishability theory in the computational complexity based, and to clarify the meaning of the value of the variational distance. In addition, the same analysis for the information theoretic case is necessary. The recent serial papers by H.P.Yuen have given the answer on such questions. In this paper, we show more concise description of Yuen's theory, and clarify that the recent upper bound theories for the trace distance by Tomamichel et al and Hayashi et al are constructed based on the reasoning of Renner and it is unsuitable as the analysis for information theoretic security. Finally, we introduce a macroscopic quantum communication with different principle to replace Q-bit QKD.
The security of quantum cryptography protocols after a quantum key distribution (QKD) session is formulated in terms of proximity between two situations: quantum states corresponding to real and ideal situations after QKD. The measure of proximity is the trace distance. It is more reasonable to formulate security directly in terms of the smallness of probability of successive guessing of keys by an eavesdropper after an arbitrary number of QKD sessions. There is a fundamental question the answer to which is a priori very unobvious: Is the security criterion in terms of the proximity of the real and ideal situations for a single QKD session sufficient to guarantee the security of keys in terms of the smallness of probability of guessing of keys by the eavesdropper after an arbitrary number of QKD sessions? It has been shown that the answer to this question is positive.
Users of a quantum cryptographic system face a problem of deciding on the ignorance of a maximally adroit eavesdropper concerning their key material. It is known that there can be no sure, positive, lower bound on any plausible measure of ignorance, and for this reason we characterize the problem as the making of an informed guess, meaning a guess that employs a rule that can be shown to work except in unlikely cases. As the measure of an eavesdropper's ignorance concerning n bits of sifted key material less some number k of bits found in error and discarded, we analyze Renyi entropy of arbitrary order R, for 1 ≤ R ≤ 2. We offer a rule for deciding on Renyi entropy based on a tighter bound on the relevant probability distributions than has been available. To this end, we employ a recently derived approximation to the cumulative binomial distribution which is uniformly accurate over a larger domain than previously available approximations. This results in a longer distilled key than that obtained from looser bounds, as well as generalizing the order R. Some numerical examples are presented.
The trace distance criterion for security of Quantum Key Distribution (QKD) has been widely perceived that its upperbound is the maximum failure probability in distributing an ideal quantum state that the quantum system shared by legitimate users is decoupled from the quantum system the eavesdropper possesses, therefore the eavesdropper would not obtain any hints on the key shared by the legitimate users no matter how much her measurement is optimal. However, there an arbitrariness in the definition of the trace distance with the decoupled quantum system the eavesdropper possesses as the previous work pointed out, and such an arbitrariness would be confusions in guaranteeing the security of QKD. In this work, from the framework of Bit-Error-Rate (BER) Guarantee discussed also in the previous work, such an arbitrariness is removed from the definition of the trace distance criterion by discussing the similarities and differences between the security of QKD and classical information-theoretic cryptography by Leftover Hash Lemma (LHL). However, in the previous work BER Guarantee was derived under the assumption that the eavesdropper launches the weakest class of attack, so-called “Individual Attacks.” Therefore, it is still unknown whether direct upper-bounding of the term would give tighter upper-bound in general, such as “Collective Attacks” or “Coherent Attacks”, compared to the upper-bound by LHL, as well as the secure-key generation rate. This study also revisits the security proof of QKD given by P. Shor and J. Preskill in 2000.