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

Quantum key expansion from non-orthogonal codes

Zhiguo Luo, Igor Devetak

Published Aug 2, 2006• 1 citation
OpenAlex

Abstract

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.

Related papers

Efficiently implementable codes for quantum key expansion

Zhicheng Luo, Igor Devetak

The Shor-Preskill proof of the security of the Bennett-Brassard 1984 (BB84) quantum key distribution protocol relies on the theoretical existence of good classical error-correcting codes with the ``dual-containing'' property. A practical implementation of the BB84 protocol thus requires explicit and efficiently decodable constructions of such codes, which are not known. On the other hand, modern coding theory abounds with non-dual-containing codes with excellent performance and efficient decoding algorithms. We show that the dual-containing constraint can be lifted at a small price: instead of a key distribution protocol, an efficiently implementable key expansion protocol is obtained, capable of increasing the size of a preshared key by a constant factor.

arXiv:quant-ph/0608029•Physical Review A•Jan 31, 2007•20 citations

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•44 citations

Reliability of calderbank-shor-steane codes and security of quantum key distribution

M. Hamada

This paper describes the security of quantum key distribution (QKD) to share a random secret string of digits between two parties based on the principle of quantum mechanics. A Colderbank-Shor-Steane quantum code had been implicitly used in the BB84 protocol, which makes fidelity of this code to unity and the mutual information between the shared key and the data obtained approaches zero. In the BB84 protocol, the sender transmits digits from which encoded into an orthogonal basis or the conjugate basis. These CSS codes achieve a higher rate called as Shannon rate.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•11 citations

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

Ramesh Bhandari

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.

arXiv:1409.1452•Aug 30, 2014•2 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

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,136 citations
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.
The Shor-Preskill proof of the security of the Bennett-Brassard 1984 (BB84) quantum key distribution protocol relies on the theoretical existence of good classical error-correcting codes with the ``dual-containing'' property. A practical implementation of the BB84 protocol thus requires explicit and efficiently decodable constructions of such codes, which are not known. On the other hand, modern coding theory abounds with non-dual-containing codes with excellent performance and efficient decoding algorithms. We show that the dual-containing constraint can be lifted at a small price: instead of a key distribution protocol, an efficiently implementable key expansion protocol is obtained, capable of increasing the size of a preshared key by a constant factor.
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.
This paper describes the security of quantum key distribution (QKD) to share a random secret string of digits between two parties based on the principle of quantum mechanics. A Colderbank-Shor-Steane quantum code had been implicitly used in the BB84 protocol, which makes fidelity of this code to unity and the mutual information between the shared key and the data obtained approaches zero. In the BB84 protocol, the sender transmits digits from which encoded into an orthogonal basis or the conjugate basis. These CSS codes achieve a higher rate called as Shannon rate.
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.
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.
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.