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

Journal of Experimental and Theoretical Physics

Distinguishability of quantum states and shannon complexity in quantum cryptography

Igor M. Arbekov, S. N. Molotkov

Published Jul 1, 2017• 22 citations
Publisher

Abstract

The proof of the security of quantum key distribution is a rather complex problem. Security is defined in terms different from the requirements imposed on keys in classical cryptography. In quantum cryptography, the security of keys is expressed in terms of the closeness of the quantum state of an eavesdropper after key distribution to an ideal quantum state that is uncorrelated to the key of legitimate users. A metric of closeness between two quantum states is given by the trace metric. In classical cryptography, the security of keys is understood in terms of, say, the complexity of key search in the presence of side information. In quantum cryptography, side information for the eavesdropper is given by the whole volume of information on keys obtained from both quantum and classical channels. The fact that the mathematical apparatuses used in the proof of key security in classical and quantum cryptography are essentially different leads to misunderstanding and emotional discussions [1]. Therefore, one should be able to answer the question of how different cryptographic robustness criteria are related to each other. In the present study, it is shown that there is a direct relationship between the security criterion in quantum cryptography, which is based on the trace distance determining the distinguishability of quantum states, and the criterion in classical cryptography, which uses guesswork on the determination of a key in the presence of side information.

DOI
10.1134/s1063776117060085

Related papers

On the complexity of search for keys in quantum cryptography

S. N. Molotkov

The trace distance is used as a security criterion in proofs of security of keys in quantum cryptography. Some authors doubted that this criterion can be reduced to criteria used in classical cryptography. The following question has been answered in this work. Let a quantum cryptography system provide an ε-secure key such that ½‖ρ XE − ρ U ⊗ ρ E ‖1 < ε, which will be repeatedly used in classical encryption algorithms. To what extent does the ε-secure key reduce the number of search steps (guesswork) as compared to the use of ideal keys? A direct relation has been demonstrated between the complexity of the complete consideration of keys, which is one of the main security criteria in classical systems, and the trace distance used in quantum cryptography. Bounds for the minimum and maximum numbers of search steps for the determination of the actual key have been presented.

Journal of Experimental and Theoretical Physics Letters•Mar 1, 2016•7 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

Towards a formal definition of security for quantum protocols

Claude Crépeau, Jeroen van de Graaf

This thesis presents a formal model for quantum protocols, that is, cryptographic protocols based on quantum mechanics. It also develops a definition of security (which includes notions such as privacy and correctness) for quantum protocols. First, existing classical (non-quantum) definitions of security are studied. There are essentially two approaches: one based on Turing Machines and simulation, the other using information theory. Both approaches are explored in detail and compared, then a particular variation of the first approach is chosen. Security is defined by introducing an interface (also called a simulator) which is capable of translating an attack on protocol 1 into an attack on protocol 2. The profile of a protocol is a stochastic variable, defined as the output of the participants and the view of the adversary who performs the attack. If an interface exists such that the profile of protocol 1 is indistinguishable from the profile of protocol 2 with the help of this interface, then protocol 1 is at least as secure as protocol 2. An absolute notion of security is obtained by comparing the protocol implementation with its 'ideal' equivalent. In this approach, and in classical cryptography in general, indistinguishability of probability distributions is a crucial tool. The meaning of this notion is explored in the context of density matrices, the mathematical formalism which is used to describe the state of a quantum system. Various measures of distinguishability of quantum states relevant from a cryptographic point of view are investigated: probability of error, trace norm (related to the Kolmogorov distance), overlap (related to the Bhattacharyya coefficient) and Shannon distinguishability (defined through the mutual information). It is shown that if we require that the distinguishability between two families of quantum states vanish exponentially fast, these four distinguishability measures are equivalent. Along the way upper and lower bounds for the Shannon distinguishability are obtained. This is a very useful result, because explicit computation of the Shannon distinguishability between two quantum states is often difficult (it requires solving a transcendental equation), whereas the other distinguishability measures, in particular the trace norm, are usually much easier to compute. In the last chapter the two previous topics are combined. A formal model for quantum protocols is formulated. It uses Quantum Turing Machines to represent the participants, who communicate through a quantum channel. The different nature of quantum information as opposed to classical information is explored in detail, including the implications this has for the definition. As in the classical case, we introduce an interface to compare the security of two protocols for the same task. Subsequently some consequences of the proposed definition are investigated. In particular, strong evidence is given that one classical technique often used in proofs of security for classical protocols, called rewinding, is impossible in the quantum setting.

•Jan 1, 1998•47 citations

One-time pad, complexity of verification of keys, and practical security of quantum cryptography

S. N. Molotkov

A direct relation between the complexity of the complete verification of keys, which is one of the main criteria of security in classical systems, and a trace distance used in quantum cryptography is demonstrated. Bounds for the minimum and maximum numbers of verification steps required to determine the actual key are obtained.

Journal of Experimental and Theoretical Physics•Nov 1, 2016•10 citations

On the Key Search Complexity in Quantum Cryptography with Strong Information-Theoretic Authentication

S. P. Kulik, S. N. Molotkov

The stability of quantum key distribution systems is based not only on the detection of attacks on quantum states, which is guaranteed by the fundamental quantum theory laws, but also on ensuring the integrity of classical messages transmitted through an auxiliary classical communication channel. To detect attacks on the classic communication channel, the authentication procedure is used. Information-theoretic authentication guarantees the detection of attacks on the classical communication channel regardless of the computational and technical capabilities of an eavesdropper, including the quantum computer. The fundamental quantum cryptographic relationship between the abstract criterion of the robustness of quantum key distribution systems with theoretical-information authentication and the quantum key search complexity has been determined for the first time using simple means.

Journal of Experimental and Theoretical Physics Letters•Mar 1, 2025•0 citations

Robustness bounds and practical limitations of quantum key distribution

Aeysha Khalique

Quantum information theory is a modern branch of theoretical physics. One of its main goals is to interpret concepts of quantum physics. This leads to a deeper understanding of quantum theory. The most common examples of practical applications of basic quantum theory are quantum computation and quantum cryptography. Quantum cryptography provides secure communication between legitimate users even in the presence of an adversary by making possible the distribution of a secret key. It then allows error correction and privacy amplification, which is elimination of adversary information, through classical communication. In this thesis two important aspects of quantum key distribution are covered, namely robustness bounds with respect to provable entanglement for ideal protocols and practical quantum key distribution using two-way classical communication. In part one of the thesis, ideal quantum key distribution protocols and their robustness in terms of provable entanglement are discussed. The robustness bounds are proved for most general coherent attacks. These bounds for provable entanglement are already known to be 25% for the four-state protocol and 33% for the six-state protocol. We anticipate to provide a region in which the legitimate users share entanglement. This region is large for the four-state protocol and is reduced to a smaller region for the six-state protocol because of additional constraint on it. We also investigate the information cost which the adversary has to pay in order to reach these bounds. In part two we adopt a more practical approach. We investigate the limitation on distance of secure communication because of practical restrictions. In particular we investigate the restrictions due to the lack of single photon sources, the lossy channel and faulty detectors. These practical limitations have already been observed using one-way classical communication between legitimate users. It has been observed that it is actually the dark count rate that limit the distance up to which legitimate users can share a secret key. We have used two-way classical communication to postpone the effect of dark counts and increase the distance to considerable amount. For the purpose we have considered an optimal attack with respect to the disturbance that an eavesdropper creates while attacking. Any other format of attacking will increase the disturbance. We show that using two-way classical communication for post processing we can increase the distance of secure communication considerably.

•Jan 1, 2008•0 citations
The proof of the security of quantum key distribution is a rather complex problem. Security is defined in terms different from the requirements imposed on keys in classical cryptography. In quantum cryptography, the security of keys is expressed in terms of the closeness of the quantum state of an eavesdropper after key distribution to an ideal quantum state that is uncorrelated to the key of legitimate users. A metric of closeness between two quantum states is given by the trace metric. In classical cryptography, the security of keys is understood in terms of, say, the complexity of key search in the presence of side information. In quantum cryptography, side information for the eavesdropper is given by the whole volume of information on keys obtained from both quantum and classical channels. The fact that the mathematical apparatuses used in the proof of key security in classical and quantum cryptography are essentially different leads to misunderstanding and emotional discussions [1]. Therefore, one should be able to answer the question of how different cryptographic robustness criteria are related to each other. In the present study, it is shown that there is a direct relationship between the security criterion in quantum cryptography, which is based on the trace distance determining the distinguishability of quantum states, and the criterion in classical cryptography, which uses guesswork on the determination of a key in the presence of side information.
The trace distance is used as a security criterion in proofs of security of keys in quantum cryptography. Some authors doubted that this criterion can be reduced to criteria used in classical cryptography. The following question has been answered in this work. Let a quantum cryptography system provide an ε-secure key such that ½‖ρ XE − ρ U ⊗ ρ E ‖1 < ε, which will be repeatedly used in classical encryption algorithms. To what extent does the ε-secure key reduce the number of search steps (guesswork) as compared to the use of ideal keys? A direct relation has been demonstrated between the complexity of the complete consideration of keys, which is one of the main security criteria in classical systems, and the trace distance used in quantum cryptography. Bounds for the minimum and maximum numbers of search steps for the determination of the actual key have been presented.
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.
This thesis presents a formal model for quantum protocols, that is, cryptographic protocols based on quantum mechanics. It also develops a definition of security (which includes notions such as privacy and correctness) for quantum protocols. First, existing classical (non-quantum) definitions of security are studied. There are essentially two approaches: one based on Turing Machines and simulation, the other using information theory. Both approaches are explored in detail and compared, then a particular variation of the first approach is chosen. Security is defined by introducing an interface (also called a simulator) which is capable of translating an attack on protocol 1 into an attack on protocol 2. The profile of a protocol is a stochastic variable, defined as the output of the participants and the view of the adversary who performs the attack. If an interface exists such that the profile of protocol 1 is indistinguishable from the profile of protocol 2 with the help of this interface, then protocol 1 is at least as secure as protocol 2. An absolute notion of security is obtained by comparing the protocol implementation with its 'ideal' equivalent. In this approach, and in classical cryptography in general, indistinguishability of probability distributions is a crucial tool. The meaning of this notion is explored in the context of density matrices, the mathematical formalism which is used to describe the state of a quantum system. Various measures of distinguishability of quantum states relevant from a cryptographic point of view are investigated: probability of error, trace norm (related to the Kolmogorov distance), overlap (related to the Bhattacharyya coefficient) and Shannon distinguishability (defined through the mutual information). It is shown that if we require that the distinguishability between two families of quantum states vanish exponentially fast, these four distinguishability measures are equivalent. Along the way upper and lower bounds for the Shannon distinguishability are obtained. This is a very useful result, because explicit computation of the Shannon distinguishability between two quantum states is often difficult (it requires solving a transcendental equation), whereas the other distinguishability measures, in particular the trace norm, are usually much easier to compute. In the last chapter the two previous topics are combined. A formal model for quantum protocols is formulated. It uses Quantum Turing Machines to represent the participants, who communicate through a quantum channel. The different nature of quantum information as opposed to classical information is explored in detail, including the implications this has for the definition. As in the classical case, we introduce an interface to compare the security of two protocols for the same task. Subsequently some consequences of the proposed definition are investigated. In particular, strong evidence is given that one classical technique often used in proofs of security for classical protocols, called rewinding, is impossible in the quantum setting.
The stability of quantum key distribution systems is based not only on the detection of attacks on quantum states, which is guaranteed by the fundamental quantum theory laws, but also on ensuring the integrity of classical messages transmitted through an auxiliary classical communication channel. To detect attacks on the classic communication channel, the authentication procedure is used. Information-theoretic authentication guarantees the detection of attacks on the classical communication channel regardless of the computational and technical capabilities of an eavesdropper, including the quantum computer. The fundamental quantum cryptographic relationship between the abstract criterion of the robustness of quantum key distribution systems with theoretical-information authentication and the quantum key search complexity has been determined for the first time using simple means.
Quantum information theory is a modern branch of theoretical physics. One of its main goals is to interpret concepts of quantum physics. This leads to a deeper understanding of quantum theory. The most common examples of practical applications of basic quantum theory are quantum computation and quantum cryptography. Quantum cryptography provides secure communication between legitimate users even in the presence of an adversary by making possible the distribution of a secret key. It then allows error correction and privacy amplification, which is elimination of adversary information, through classical communication. In this thesis two important aspects of quantum key distribution are covered, namely robustness bounds with respect to provable entanglement for ideal protocols and practical quantum key distribution using two-way classical communication. In part one of the thesis, ideal quantum key distribution protocols and their robustness in terms of provable entanglement are discussed. The robustness bounds are proved for most general coherent attacks. These bounds for provable entanglement are already known to be 25% for the four-state protocol and 33% for the six-state protocol. We anticipate to provide a region in which the legitimate users share entanglement. This region is large for the four-state protocol and is reduced to a smaller region for the six-state protocol because of additional constraint on it. We also investigate the information cost which the adversary has to pay in order to reach these bounds. In part two we adopt a more practical approach. We investigate the limitation on distance of secure communication because of practical restrictions. In particular we investigate the restrictions due to the lack of single photon sources, the lossy channel and faulty detectors. These practical limitations have already been observed using one-way classical communication between legitimate users. It has been observed that it is actually the dark count rate that limit the distance up to which legitimate users can share a secret key. We have used two-way classical communication to postpone the effect of dark counts and increase the distance to considerable amount. For the purpose we have considered an optimal attack with respect to the disturbance that an eavesdropper creates while attacking. Any other format of attacking will increase the disturbance. We show that using two-way classical communication for post processing we can increase the distance of secure communication considerably.