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

Efficiency of Winnow Protocol in Secret Key Reconciliation

Hao Yan, Xiang Peng, Xiaxiang Lin, Wei Jiang, Tian Liu, Hong Mei Guo

Published Jan 1, 2009• 16 citations
Publisher

Abstract

Secret key reconciliation is an important step in the process of quantum key distribution. In the protocols used for reconciliation, Winnow has been proved a fast and efficient one. In this paper, we analyze the efficiency of Winnow in terms of amount of leaked information in details. We give the optimal block size in Winnow theoretically and experimentally for different error rate.

DOI
10.1109/csie.2009.383

Related papers

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, 2012•7 citations

Optimization of Block Size for Reconciliation Protocol

Lei Cao, Wei Yue Liu, Bo Zhong +3 more

Reconciliation protocol is used in quantum cryptography to correct errors in qubits by exchanging information via classical channel. Winnow is a widely used efficient reconciliation protocol. It separates qubits into blocks, then utilizes Hamming coding to remove bit errors in each block. Performance of Winnow protocol relies deeply on the size of the blocks. In this paper, implementation of winnow protocol is introduced and optimization of block size for the protocol is analyzed. It is shown through experiment results that the optimized value of block size is 0.4/BER, where BER is bit error rate of qubits.

Applied Mechanics and Materials•Oct 1, 2014•0 citations

Fast, efficient error reconciliation for quantum cryptography

W. T. Buttler, S. K. Lamoreaux, Justin R. Torgerson +3 more

We describe an error-reconciliation protocol, which we call Winnow, based on the exchange of parity and Hamming's ``syndrome'' for N-bit subunits of a large dataset. The Winnow protocol was developed in the context of quantum-key distribution and offers significant advantages and net higher efficiency compared to other widely used protocols within the quantum cryptography community. A detailed mathematical analysis of the Winnow protocol is presented in the context of practical implementations of quantum-key distribution; in particular, the information overhead required for secure implementation is one of the most important criteria in the evaluation of a particular error-reconciliation protocol. The increase in efficiency for the Winnow protocol is largely due to the reduction in authenticated public communication required for its implementation.

arXiv:quant-ph/0203096•Physical Review A•May 15, 2003•201 citations

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

Riaz Ahmad Qamar

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.

•Aug 1, 2013•0 citations

Performance of ½-rate convolutional code on Winnow protocol for quantum key reconciliation

Patcharapong Treeviriyanupab, Paramin Sangwongngam, Keattisak Sripimanwat +1 more

The quantum key reconciliation is an essential step of Quantum Key Distribution (QKD) systems for correcting error in the raw keys which happens after the transmission over a quantum channel, where two legitimate parties make their correlated bits identical by exchanging messages over the public channel. This paper presents an alternative method for error correction of quantum key reconciliation by using ½-rate convolutional code, a class of forward error correcting (FEC) on Winnow for discrete-variable QKD protocol. The convolutional code can be applied to source coding with a side information problem which uses to describe quantum key reconciliation process. In the proposed scheme, it focuses on the performance evaluation of ½-rate convolutional code in quantum key reconciliation. In order to reduce an amount of interactive communication via error-free public channel for high-speed QKD applications, this proposed method is that the suitable solution.

International Symposium on Communications and Information Technologies•Oct 1, 2010•2 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 Technology•Sep 11, 2013•27 citations
Secret key reconciliation is an important step in the process of quantum key distribution. In the protocols used for reconciliation, Winnow has been proved a fast and efficient one. In this paper, we analyze the efficiency of Winnow in terms of amount of leaked information in details. We give the optimal block size in Winnow theoretically and experimentally for different error rate.
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.
Reconciliation protocol is used in quantum cryptography to correct errors in qubits by exchanging information via classical channel. Winnow is a widely used efficient reconciliation protocol. It separates qubits into blocks, then utilizes Hamming coding to remove bit errors in each block. Performance of Winnow protocol relies deeply on the size of the blocks. In this paper, implementation of winnow protocol is introduced and optimization of block size for the protocol is analyzed. It is shown through experiment results that the optimized value of block size is 0.4/BER, where BER is bit error rate of qubits.
We describe an error-reconciliation protocol, which we call Winnow, based on the exchange of parity and Hamming's ``syndrome'' for N-bit subunits of a large dataset. The Winnow protocol was developed in the context of quantum-key distribution and offers significant advantages and net higher efficiency compared to other widely used protocols within the quantum cryptography community. A detailed mathematical analysis of the Winnow protocol is presented in the context of practical implementations of quantum-key distribution; in particular, the information overhead required for secure implementation is one of the most important criteria in the evaluation of a particular error-reconciliation protocol. The increase in efficiency for the Winnow protocol is largely due to the reduction in authenticated public communication required for its implementation.
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.
The quantum key reconciliation is an essential step of Quantum Key Distribution (QKD) systems for correcting error in the raw keys which happens after the transmission over a quantum channel, where two legitimate parties make their correlated bits identical by exchanging messages over the public channel. This paper presents an alternative method for error correction of quantum key reconciliation by using ½-rate convolutional code, a class of forward error correcting (FEC) on Winnow for discrete-variable QKD protocol. The convolutional code can be applied to source coding with a side information problem which uses to describe quantum key reconciliation process. In the proposed scheme, it focuses on the performance evaluation of ½-rate convolutional code in quantum key reconciliation. In order to reduce an amount of interactive communication via error-free public channel for high-speed QKD applications, this proposed method is that the suitable solution.
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.