Quantum Key Distribution (QKD) is a revolutionary security technology that exploits the laws of quantum mechanics to achieve information-theoretic secure key exchange. QKD enables two parties to “grow” a shared secret key without placing any limits on an adversary’s computational power. Error reconciliation protocols have been developed that preserve security while allowing a sender and receiver to reconcile the errors in their respective keys. The most famous of these is the Cascade protocol, which is effective but suffers from a high communication complexity and low throughput. The Winnow protocol reduces the communication complexity over Cascade, but has the disadvantage of introducing errors. Finally, Low Density Parity Check (LDPC) codes have been shown to reconcile errors at rates higher than those of Cascade and Winnow, but with greater computational complexity. In this paper we evaluate the effectiveness of LDPC codes by comparing the runtime, throughput and communication complexity empirically with the Cascade and Winnow algorithms. The effects of inaccurate error estimation, non-uniform error distribution and varying key length on all three protocols are evaluated for identical input key strings. Analyses are performed on the results in order to characterize the strengths and weaknesses of each protocol.
Quantum Key Distribution (QKD) is a revolutionary security technology that exploits the laws of quantum mechanics to achieve information-theoretic secure key exchange. QKD enables two parties to “grow” a shared secret key without placing any limits on an adversary’s computational power. Error reconciliation protocols have been developed that preserve security while allowing a sender and receiver to reconcile the errors in their respective keys. The most famous of these is the Cascade protocol, which is effective but suffers from a high communication complexity and low throughput. The Winnow protocol reduces the communication complexity over Cascade, but has the disadvantage of introducing errors. Finally, Low Density Parity Check (LDPC) codes have been shown to reconcile errors at rates higher than those of Cascade and Winnow, but with greater computational complexity. In this paper we evaluate the effectiveness of LDPC codes by comparing the runtime, throughput and communication complexity empirically with the Cascade and Winnow algorithms. The effects of inaccurate error estimation, non-uniform error distribution and varying key length on all three protocols are evaluated for identical input key strings. Analyses are performed on the results in order to characterize the strengths and weaknesses of each protocol.
Abstract : Quantum Key Distribution (QKD) is a method for transmitting a cryptographic key between a sender and receiver in a theoretically unconditionally secure way. Unfortunately, the present state of technology prohibits the flawless quantum transmission required to make QKD a reality. For this reason, error reconciliation protocols have been developed which preserve security while allowing a sender and receiver to reconcile the errors in their respective keys. The most famous of these protocols is Brassard and Salvail's Cascade, which is effective, but suffers from a high communication complexity and therefore results in low throughput. Another popular option is Buttler's Winnow protocol, which reduces the communication complexity over Cascade, but has the added detriment of introducing errors, and has been shown to be less effective than Cascade. Finally, Gallager's Low Density Parity Check (LDPC) codes have recently been shown to reconcile errors at rates higher than those of Cascade and Winnow with a large reduction in communication, but with greater computational complexity. This research seeks to evaluate the effectiveness of these LDPC codes in a QKD setting, while comparing real-world parameters such as runtime, throughput and communication complexity empirically with the well-known Cascade and Winnow algorithms. Additionally, the effects of inaccurate error estimation, non-uniform error distribution and varying key length on all three protocols are evaluated for identical input key strings. Analyses are performed on the results in order to characterize the performance of all three protocols and determine the strengths and weaknesses of each.
Quantum cryptography specifically called Quantum Key Distribution (QKD) provides acceptable levels of secure communications by utilising established laws of quantum mechanics. QKD protocol distributes a raw key through quantum channel between two cryptography users and then it removes errors occurred during communication from the distributed key by passing messages via public channel. Most popular error reconciliation protocols such as Binary, Cascade and Winnow are used to remove errors in a secure way. Among these three protocols, Buttler’s Winnow has the advantage of less communication complexity, however it is less effective at high error rates in a key and has the disadvantage of introducing errors during error reconciliation, and hence, causes reduction in reconciled key size and/or leave errors in the reconciled key. Winnow can handle quantum bit error rates a maximum up to 18 percent. However, after 13 percent error rate, Winnow becomes highly interactive and it may fail to reconcile the key. The deficiencies of high interactivity, reduction in reconciled key size, leaving errors in the reconciled key and failure of Winnow can be removed by enhancing the error reconciliation protocol by employing modified Bose, Chaudhuri, Hocquenghem (BCH) channel coding techniques. The enhanced BCH encoding algorithm is designed to handle a key at higher quantum bit error rates. BCH error detection and correction algorithms are enhanced to minimise the error percentage in the reconciled key. The modified block interleaver is introduced in the reconciliation protocol to obtain a long-size reconciled key with minimum iterations. The enhanced error reconciliation protocol can reconcile the key up to 50 percent initial bit error rate and reduces public channel communications. Finally, a long sized identical shared secret key with minimal error rate approaching zero is obtained within two iterations. The attained key can be used with secret key cipher to encrypt and decrypt information.
Abstract : Currently, private communications in public and government sectors rely on methods of cryptographic key distribution that will likely be rendered obsolete the moment a full-scale quantum computer is realized, or efficient classical methods of factoring are discovered. There are alternative methods for distributing secret key material in a post-quantum era. One example of a system capable of securely distributing cryptographic key material, known as Quantum Key Distribution (QKD), is secure against quantum factorization techniques as its security rests on generally accepted laws of quantum physics. QKD protocols typically include a phase called Error Reconciliation, a clear-text classical-channel discussion between legitimate parties of a QKD protocol by which errors introduced in the quantum channel are corrected and the legitimate parties ensure they share identical key material. This work improves one such reconciliation protocol, called Winnow, by examining block-size choices for Winnow and thus increasing QKD key rate. Block sizes are chosen to maximize the probability that each block contains exactly one error. Further analyses of Winnow are provided to characterize the effects of different error distributions on protocol operation and shed light on the time and communication complexities of the Winnow secret key reconciliation protocol.
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string -the key- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals -the raw key- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string -the key- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals -the raw key- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string —the key— known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals —the raw key— must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of theQKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secretkey agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.