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 Letters

On the complexity of search for keys in quantum cryptography

S. N. Molotkov

Published Mar 1, 2016• 7 citations
Publisher

Abstract

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.

DOI
10.1134/s002136401605009x

Related papers

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

Distinguishability of quantum states and shannon complexity in quantum cryptography

Igor M. Arbekov, S. N. Molotkov

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.

Journal of Experimental and Theoretical Physics•Jul 1, 2017•22 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

Shannon unicity distance, ε -secrecy criterion and Holevo information in quantum cryptography

Igor M. Arbekov, S. N. Molotkov

Abstract In this paper, we consider the relationship between C Shannon’s unicity distance, which is determined by the number of symbols of the encrypted message required to uniquely find the encryption key of the cryptosystem in information-theoretical sense, ε -secrecy criterion in quantum cryptography and Holevo information. A lower bound for the unicity distance for ε -secret keys in quantum cryptography is obtained. The relationship between unicity distance, ε -secrecy criterion in quantum cryptography and Holevo information is demonstrated.

Laser Physics Letters•Dec 21, 2020•0 citations

On the multiple use of quantum keys

С. Н. Молотков, Ivan S. Sushchev

Abstract In practice today, quantum keys are often reused because of practical limitations. It is clear that reusing a key weakens security compared to one-time-pad encryption, where perfect secrecy is achieved. For this reason, it is important to understand how the effort needed to find the key changes when the key is reused. We use the trace distance between two quantum states as a measure of closeness. Its maximum value is one, which means the two states are as different as possible. With simple arguments, we show that the trace distance is bounded above by several terms that capture (i) non-ideal quantum keys, (ii) plaintext redundancy, (iii) the number of key reuses, and (iv) the number of collisions of the block cipher. The trace distance approaches one exponentially fast with plaintext redundancy and with the number of key reuses; this means brute-force search becomes as easy as possible. For a random block cipher, the expected trace distance grows linearly with the number of key uses, with coefficient e −1 ( e is Euler’s constant). The result is information-theoretic in nature.

Laser Physics Letters•Mar 1, 2026•0 citations

Security of Quantum Key Distribution

Horace P. Yuen

The security issues facing quantum key distribution (QKD) are explained, herein focusing on those issues that are cryptographic and information theoretic in nature and not those based on physics. The problem of security criteria is addressed. It is demonstrated that an attacker's success probabilities are the fundamental criteria of security that any theoretic security criterion must relate to in order to have operational significance. The errors committed in the prevalent interpretation of the trace distance criterion are analyzed. The security proofs of QKD protocols are discussed and assessed in regard to three main features: their validity, completeness, and adequacy of the achieved numerical security level. Problems are identified in all these features. It appears that the QKD security situation is quite different from the common perception that a QKD-generated key is nearly perfectly secure. Built into our discussion is a simple but complete quantitative description of the information theoretic security of classical key distribution that is also applicable to the quantum situation. In the appendices, we provide a brief outline of the history of some major QKD security proofs, a rather unfavorable comparison of current QKD proven security with that of conventional symmetric key ciphers, and a list of objections and answers concerning some major points of the paper.

arXiv:1602.07602•Feb 24, 2016•0 citations
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 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 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.
Abstract In this paper, we consider the relationship between C Shannon’s unicity distance, which is determined by the number of symbols of the encrypted message required to uniquely find the encryption key of the cryptosystem in information-theoretical sense, ε -secrecy criterion in quantum cryptography and Holevo information. A lower bound for the unicity distance for ε -secret keys in quantum cryptography is obtained. The relationship between unicity distance, ε -secrecy criterion in quantum cryptography and Holevo information is demonstrated.
Abstract In practice today, quantum keys are often reused because of practical limitations. It is clear that reusing a key weakens security compared to one-time-pad encryption, where perfect secrecy is achieved. For this reason, it is important to understand how the effort needed to find the key changes when the key is reused. We use the trace distance between two quantum states as a measure of closeness. Its maximum value is one, which means the two states are as different as possible. With simple arguments, we show that the trace distance is bounded above by several terms that capture (i) non-ideal quantum keys, (ii) plaintext redundancy, (iii) the number of key reuses, and (iv) the number of collisions of the block cipher. The trace distance approaches one exponentially fast with plaintext redundancy and with the number of key reuses; this means brute-force search becomes as easy as possible. For a random block cipher, the expected trace distance grows linearly with the number of key uses, with coefficient e −1 ( e is Euler’s constant). The result is information-theoretic in nature.
The security issues facing quantum key distribution (QKD) are explained, herein focusing on those issues that are cryptographic and information theoretic in nature and not those based on physics. The problem of security criteria is addressed. It is demonstrated that an attacker's success probabilities are the fundamental criteria of security that any theoretic security criterion must relate to in order to have operational significance. The errors committed in the prevalent interpretation of the trace distance criterion are analyzed. The security proofs of QKD protocols are discussed and assessed in regard to three main features: their validity, completeness, and adequacy of the achieved numerical security level. Problems are identified in all these features. It appears that the QKD security situation is quite different from the common perception that a QKD-generated key is nearly perfectly secure. Built into our discussion is a simple but complete quantitative description of the information theoretic security of classical key distribution that is also applicable to the quantum situation. In the appendices, we provide a brief outline of the history of some major QKD security proofs, a rather unfavorable comparison of current QKD proven security with that of conventional symmetric key ciphers, and a list of objections and answers concerning some major points of the paper.