Enhanced winnow key reconciliation for bennett-brassard 84 quantum key distribution protocol

Riaz Ahmad Qamar

Published Aug 1, 2013• 0 citations

Abstract

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.

Related papers

An Efficient Reconciliation in Removing Errors Using Bose, Chaudhuri, Hocquenghem Code for Quantum Key Distribution

Riaz Ahmad Qamar, Mohd Aizaini Maarof, Subariah Ibrahim

A quantum key distribution protocol(QKD), known as BB84, was developed in 1984 by Charles Bennett and Gilles Brassard. The protocol works in two phases which are quantum state transmission and conventional post processing. In the first phase of BB84, raw key elements are distributed between two legitimate users by sending encoded photons through quantum channel whilst in the second phase, a common secret-key is obtained from correlated raw key elements by exchanging messages through a public channel e.g.; network or internet. The secret-key so obtained is used for cryptography purpose. Reconciliation is a compulsory part of post processing and hence of quantum key distribution protocol. The performance of a reconciliation protocol depends on the generation rate of common secret-key, number of bits disclosed and the error probability in common secrete-key. These characteristics of a protocol can be achieved by using a less interactive reconciliation protocol which can handle a higher initial quantum bit error rate (QBER). In this paper, we use a simple Bose, Chaudhuri, Hocquenghem (BCH) error correction algorithm with simplified syndrome table to achieve an efficient reconciliation protocol which can handle a higher quantum bit error rate and outputs a common key with zero error probability. The proposed protocol efficient in removing errors such that it can remove all errors even if QBER is 60%. Assuming the post processing channel is an authenticated binary symmetric channel (BSC).

Jurnal TeknologiNov 2, 20121 citation

An Analysis of Error Reconciliation Protocols for use in Quantum Key Distribution

James Samuel Johnson

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.

Feb 1, 20128 citations

An analysis of error reconciliation protocols used in Quantum Key Distribution systems

James Samuel Johnson, Michael R. Grimaila, Jeffrey W. Humphries +1 more

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.

The Journal of Defense Modeling and Simulation Applications Methodology TechnologySep 11, 201327 citations

Performance Analysis and Optimization of the Winnow Secret Key Reconciliation Protocol

Kevin C. Lustic

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.

Nov 21, 20127 citations

A Novel Error Correction Scheme in Quantum Key Distribution (QKD) Protocol

Siao Ping Lee, Chee Kyun Ng, Makhfudzah Binti Mokhtar

Ideally, in any quantum key distribution (QKD) communication system, each sifted key is expected to be received without error. However in practice, due to infeasibility of generating pure single photon and device impairment problem, some of the sifted key may experience errors. This results to the increment of quantum bit error rate (QBER) that requires error reconciliation for correcting error. The main concept in error reconciliation is very much related to the capability of correcting all errors while minimizing eavesdrop information. The quantum error correcting code such as Hamming code which used in Winnow protocol is found to be more attractive. However the Winnow protocol can only correct one error out of seven bits. In this paper, a modified Hamming encoder/decoder to improve Winnow protocol by correcting two errors out of seven bits which leads to reducing the QBER is presented. This design utilizes a pair of forward and reverse order syndromes for error pattern recognition. A new reconciliation protocol has been developed to enhance the error correcting capability in BB84 protocol. It is carried out in a simple structure which can correct up to double erroneous bits and detect four erroneous bits for each seven bits.

Proceedings of the Asia-Pacific Advanced NetworkOct 21, 20150 citations

Improvement of reconciliation for quantum key distribution

Keath Chen

Quantum Key Distribution is meant to be an ultimate computer security system that will not need upgrade/overhaul from time to time. QKD allows the generation of long key length on demand. QKD, coupled with the unconditional secure "one-time pad" encryption system, will be unbreakable for eavesdropper with infinite resources. Numerous experimental QKD prototypes have demonstrated that QKD is likely to be a reality before quantum computer. One of the steps in a Quantum Key Distribution protocol is to remove the transmission errors from quantum communication, which typically has a high error rate (one percent or higher). An interactive error control method is utilized in the reconciliation of QKD. This procedure divides transmitted bits into blocks. The size of the block is chosen so that the chance of having multiple error bits in one block is small. By checking parity and doing interactive BINARY search when a parity error is found, error bits can be located and removed. Some error bits escape the detection from the first pass. By repeating this procedure several times, each time randomly dividing bits into blocks, most error bits can be detected and removed. Each parity check means loss of one bit. The goal is to minimize the number of parity checks to locate all (or most) errors and to have a high reliability that the remaining bits have very small residue error rate. Brassard and Salvail devised a better error control procedure in 1993. By keeping track of block parity information from pass to pass, which they called CASCADE, the number of parity checks per error bit is reduced. They observed no errors left after four passes from 10 simulation runs. However, they offered upper bound of residue error rate that was much higher than observed from simulation. Therefore, there is a need to find the optimal block size and to improve the residue error rate analysis of this procedure. In this work, improvement in reconciliation procedure is obtained in throughput (i.e. the number of input bits minus the number of parity checks) and in lower residue error rate. Throughput is doubled at high input error rate and less throughput gain at low input error rate. Three most important factors that enhance the system throughput are: 1) Using larger block size to fully utilize the power of CASCADE method. 2) Avoiding any pair of bits to stay in the same block of any later pass, which allows the use of three passes only (instead of four passes in the BS procedure). 3) Some bits are already known to be lost from the current pass, so I avoid carrying these bits to the later pass. The residue error rate at the end of the second pass (and the third pass) for small initial block size is derived. The residue error rate at the end of the third pass is found much lower than the upper bound given by the previous workers. This residue error rate is found to be a function of input size and the block size. This error control method has many similar features and difficulties to the recent development of "turbo-code" in the error control-coding field.

Jan 1, 20009 citations