© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1409.1452

Quantum Error Correcting Codes and the Security Proof of the BB84 Protocol

Ramesh Bhandari

Published Aug 30, 2014• 1 citation

Abstract

We describe the popular BB84 protocol and critically examine its security proof as presented by Shor and Preskill. The proof requires the use of quantum error correcting codes called the Calderbank-Shor-Steanne (CSS) quantum codes. These quantum codes are constructed in the quantum domain from two suitable classical linear codes, one used to correct for bit-flip errors and the other for phase-flip errors. Consequently, as a prelude to the security proof, the report reviews the essential properties of linear codes, especially the concept of cosets, before building the quantum codes that are utilized in the proof. The proof considers a security entanglement-based protocol, which is subsequently reduced to a "Prepare and Measure" protocol similar in structure to the BB84 protocol, thus establishing the security of the BB84 protocol. The proof, however, is not without assumptions, which are also enumerated. The treatment throughout is pedagogical, and this report, therefore, serves a useful tutorial for researchers, practitioners, and students, new to the field of quantum information science, in particular, quantum cryptography, as it develops the proof in a systematic manner, starting from the properties of linear codes, and then advancing to the quantum error correcting codes, which are critical to the understanding of the security proof.

DOI: 10.48550/arxiv.1409.1452

Related papers

Reliability of Calderbank–Shor–Steane codes and security of quantum key distribution

Mitsuru Hamada

After Mayers (1996, 2001) gave a proof of the security of the Bennett-Brassard 1984 (BB84) quantum key distribution protocol, Shor and Preskill (2000) made a remarkable observation that a Calderbank-Shor-Steane (CSS) code had been implicitly used in the BB84 protocol, and suggested its security could be proven by bounding the fidelity, say F(n), of the incorporated CSS code of length n in the form 1-F(n) <= exp[-n E+o(n)] for some positive number E. This work presents such a number E=E(R) as a function of the rate of a code R, and a threshold R' such that E(R)>0 whenever R < R', which is larger than the achievable rate based on the Gilbert-Varshamov bound that is essentially due to Shor and Preskill (2000). The codes in the present work are robust against fluctuations of channel parameters, which fact is needed to establish the security rigorously and was not proved for rates above the Gilbert-Varshamov rate before in the literature. As a byproduct, the security of a modified BB84 protocol against any joint (coherent) attacks is proved quantitatively.

arXiv:quant-ph/0308029•Journal of Physics A Mathematical and General•Aug 12, 2004•42 citations

The security analysis of the BB84 protocol in the case of Calderbank–Shor–Steane code leakage

Ming Fang, Yaping Li, Li Fei

Quantum key distribution (QKD) allows authenticated parties to share secure keys. Its security comes from quantum physics rather than computational complexity. The previous work has been able to demonstrate the security of the BB84 protocol based on the uncertainty principle, entanglement purification and information theory. In the security proof method based on entanglement purification, it is assumed that the information of Calderbank–Shor–Steane (CSS) error correction code cannot be leaked, otherwise, it is insecure. However, there is no quantitative analysis of the relationship between the parameter of CSS code and the amount of information leaked. In the attack and defense strategy of the actual quantum key distribution system, especially in the application of the device that is easy to lose or out of control, it is necessary to assess the impact of the parameter leakage. In this paper, we derive the relationship between the leaked parameter of CSS code and the amount of the final key leakage based on the BB84 protocol. Based on this formula, we simulated the impact of different CSS code parameter leaks on the final key amount. Through the analysis of simulation results, the security of the BB84 protocol is inversely proportional to the value of [Formula: see text] and [Formula: see text] in the case of the CSS code leak.

International Journal of Quantum Information•Jan 6, 2022•0 citations

Application Analysis of Quantum Error Correcting-Codes in Security Proving

Hongxi Li

Based on BB84 protocols,three classes of security proving for quantum cryptography are briefly introduced,and a deep research on security proving methods is provided based upon entanglement purification and quantum CSS code. The research mainly analyzes the application of quantum error correcting-codes in two representative schemes called Lo-Chau and Shor-Preskill protocol.Meanwhile,it investigates two classes of equivalence,one is the one-way entanglement purification and quantum error correction,the other is the phase error correction and removing of listener-in entanglement. Through concrete examples,it analyzes and implements the function of quantum error correcting-codes in security proving,validates the equivalence between quantum key distribution protocols based on entanglement and standard BB84 protocols,and testifies the separability between bit error correction and phase error correction,which shows the great importance of quantum error correcting-codes in security proving.

Journal of Information Engineering University•Jan 1, 2015•0 citations

On the security of the BB84 quantum key distribution protocol

Cannings, Richard

The BB84 quantum key distribution (QKD) protocol enables two authenticated parties to generate a secret key over an insecure quantum channel. Using a standardized security definition, we prove that BB84 is secure and include explicit bounds on its security. Furthermore, our use of quantum circuit diagrams simplify the Shor-Preskill proof. Namely, we can reduce the Modified Lo-Chau QKD to a practical version of BB84 using the observation from Shor and Preskill that one may ignore a correctable number of phase errors, and the fact that computational basis measurements commute with controls of CNOT operations. The first four chapters provide the required background material on quantum computing, information theory, cryptography, coding theory, and quantum error correcting codes. Chapter 5 presents protocols for entanglement purification. Chapter 6 reduces an entanglement purification protocol to the Modified Lo-Chau QKD, and proves that it is secure. Finally, a reduction from the Modified Lo-Chau QKD to BB84 establishes the security of the latter.

•Jan 1, 2004•0 citations

Quantum key expansion from non-orthogonal codes

Zhiguo Luo, Igor Devetak

The secure prepare-and-measure BB84 quantum key distribution (QKD) protocol implicit in the Shor-Preskill security proof is based on Calderbank-Shor-Steane (CSS) codes. The latter rely on the existence of pairs of good codes with mutually orthogonal parity check matices, which are hard to construct. Here we show that the orthogonality requirement can be lifted at a small price: instead of a QKD protocol we obtain a quantum key expansion (QKE) protocol, capable of increasing the size of a pre-shared key by a constant factor. Our construction is based on the recently discovered entanglement-assisted quantum codes of Brun, Devetak and Hsieh.

•Aug 2, 2006•1 citation

Simple Proof of Security of the BB84 Quantum Key Distribution Protocol

Peter W. Shor, John P. Preskill

We prove that the 1984 protocol of Bennett and Brassard (BB84) for quantum key distribution is secure. We first give a key distribution protocol based on entanglement purification, which can be proven secure using methods from Lo and Chau's proof of security for a similar protocol. We then show that the security of this protocol implies the security of BB84. The entanglement purification based protocol uses Calderbank-Shor-Steane codes, and properties of these codes are used to remove the use of quantum computation from the Lo-Chau protocol.

arXiv:quant-ph/0003004•Physical Review Letters•Jul 10, 2000•3,049 citations

We describe the popular BB84 protocol and critically examine its security proof as presented by Shor and Preskill. The proof requires the use of quantum error correcting codes called the Calderbank-Shor-Steanne (CSS) quantum codes. These quantum codes are constructed in the quantum domain from two suitable classical linear codes, one used to correct for bit-flip errors and the other for phase-flip errors. Consequently, as a prelude to the security proof, the report reviews the essential properties of linear codes, especially the concept of cosets, before building the quantum codes that are utilized in the proof. The proof considers a security entanglement-based protocol, which is subsequently reduced to a "Prepare and Measure" protocol similar in structure to the BB84 protocol, thus establishing the security of the BB84 protocol. The proof, however, is not without assumptions, which are also enumerated. The treatment throughout is pedagogical, and this report, therefore, serves a useful tutorial for researchers, practitioners, and students, new to the field of quantum information science, in particular, quantum cryptography, as it develops the proof in a systematic manner, starting from the properties of linear codes, and then advancing to the quantum error correcting codes, which are critical to the understanding of the security proof.

After Mayers (1996, 2001) gave a proof of the security of the Bennett-Brassard 1984 (BB84) quantum key distribution protocol, Shor and Preskill (2000) made a remarkable observation that a Calderbank-Shor-Steane (CSS) code had been implicitly used in the BB84 protocol, and suggested its security could be proven by bounding the fidelity, say F(n), of the incorporated CSS code of length n in the form 1-F(n) <= exp[-n E+o(n)] for some positive number E. This work presents such a number E=E(R) as a function of the rate of a code R, and a threshold R' such that E(R)>0 whenever R < R', which is larger than the achievable rate based on the Gilbert-Varshamov bound that is essentially due to Shor and Preskill (2000). The codes in the present work are robust against fluctuations of channel parameters, which fact is needed to establish the security rigorously and was not proved for rates above the Gilbert-Varshamov rate before in the literature. As a byproduct, the security of a modified BB84 protocol against any joint (coherent) attacks is proved quantitatively.

Quantum key distribution (QKD) allows authenticated parties to share secure keys. Its security comes from quantum physics rather than computational complexity. The previous work has been able to demonstrate the security of the BB84 protocol based on the uncertainty principle, entanglement purification and information theory. In the security proof method based on entanglement purification, it is assumed that the information of Calderbank–Shor–Steane (CSS) error correction code cannot be leaked, otherwise, it is insecure. However, there is no quantitative analysis of the relationship between the parameter of CSS code and the amount of information leaked. In the attack and defense strategy of the actual quantum key distribution system, especially in the application of the device that is easy to lose or out of control, it is necessary to assess the impact of the parameter leakage. In this paper, we derive the relationship between the leaked parameter of CSS code and the amount of the final key leakage based on the BB84 protocol. Based on this formula, we simulated the impact of different CSS code parameter leaks on the final key amount. Through the analysis of simulation results, the security of the BB84 protocol is inversely proportional to the value of [Formula: see text] and [Formula: see text] in the case of the CSS code leak.

Based on BB84 protocols,three classes of security proving for quantum cryptography are briefly introduced,and a deep research on security proving methods is provided based upon entanglement purification and quantum CSS code. The research mainly analyzes the application of quantum error correcting-codes in two representative schemes called Lo-Chau and Shor-Preskill protocol.Meanwhile,it investigates two classes of equivalence,one is the one-way entanglement purification and quantum error correction,the other is the phase error correction and removing of listener-in entanglement. Through concrete examples,it analyzes and implements the function of quantum error correcting-codes in security proving,validates the equivalence between quantum key distribution protocols based on entanglement and standard BB84 protocols,and testifies the separability between bit error correction and phase error correction,which shows the great importance of quantum error correcting-codes in security proving.

The BB84 quantum key distribution (QKD) protocol enables two authenticated parties to generate a secret key over an insecure quantum channel. Using a standardized security definition, we prove that BB84 is secure and include explicit bounds on its security. Furthermore, our use of quantum circuit diagrams simplify the Shor-Preskill proof. Namely, we can reduce the Modified Lo-Chau QKD to a practical version of BB84 using the observation from Shor and Preskill that one may ignore a correctable number of phase errors, and the fact that computational basis measurements commute with controls of CNOT operations. The first four chapters provide the required background material on quantum computing, information theory, cryptography, coding theory, and quantum error correcting codes. Chapter 5 presents protocols for entanglement purification. Chapter 6 reduces an entanglement purification protocol to the Modified Lo-Chau QKD, and proves that it is secure. Finally, a reduction from the Modified Lo-Chau QKD to BB84 establishes the security of the latter.

The secure prepare-and-measure BB84 quantum key distribution (QKD) protocol implicit in the Shor-Preskill security proof is based on Calderbank-Shor-Steane (CSS) codes. The latter rely on the existence of pairs of good codes with mutually orthogonal parity check matices, which are hard to construct. Here we show that the orthogonality requirement can be lifted at a small price: instead of a QKD protocol we obtain a quantum key expansion (QKE) protocol, capable of increasing the size of a pre-shared key by a constant factor. Our construction is based on the recently discovered entanglement-assisted quantum codes of Brun, Devetak and Hsieh.

We prove that the 1984 protocol of Bennett and Brassard (BB84) for quantum key distribution is secure. We first give a key distribution protocol based on entanglement purification, which can be proven secure using methods from Lo and Chau's proof of security for a similar protocol. We then show that the security of this protocol implies the security of BB84. The entanglement purification based protocol uses Calderbank-Shor-Steane codes, and properties of these codes are used to remove the use of quantum computation from the Lo-Chau protocol.