Source-linked AI summary
Efficient reconciliation protocol for discrete-variable quantum key distribution
David Elkouss, Anthony Leverrier, Romain Alléaume, Joseph Boutros
TL;DR
The paper addresses efficient reconciliation of correlated binary strings in discrete-variable QKD, where imperfect correction reduces secret-key rates and interactive communication can add latency. It uses LDPC codes optimized for the BSC and reports improved reconciliation performance, secret-key-rate prospects, and lower interactivity than Cascade.
Problem
QKD requires reconciliation to correct discrepancies between correlated strings, while inefficient or highly interactive schemes reduce secret-key rates and can introduce communication latency.
Method
The paper optimizes LDPC codes for the binary symmetric channel to reconcile correlated binary variables with a single information exchange.
Results
The LDPC protocol performs better than Cascade above a 2% error rate, approaches the 11% theoretical admissible-error limit, and extends the practical secure-distribution distance.
Takeaways & Limitations
LDPC codes provide a non-interactive alternative to Cascade with similar efficiency at small crossover probabilities and significant improvement above 0.02.
Abstract
from arXiv · showhide
Reconciliation is an essential part of any secret-key agreement protocol and hence of a Quantum Key Distribution (QKD) protocol, where two legitimate parties are given correlated data and want to agree on a common string in the presence of an adversary, while revealing a minimum amount of information. In this paper, we show that for discrete-variable QKD protocols, this problem can be advantageously solved with Low Density Parity Check (LDPC) codes optimized for the BSC. In particular, we demonstrate that our method leads to a significant improvement of the achievable secret key rate, with respect to earlier interactive reconciliation methods used in QKD.
I. INTRODUCTION
QKD reconciliation corrects discrepancies between Alice’s and Bob’s correlated strings while limiting information revealed to an eavesdropper. The paper evaluates reconciliation efficiency in the BSC setting, where imperfect reconciliation reduces secret-key rates and protocol range.
- Reconciliation in QKD: QKD post-processing first reconciles Alice’s and Bob’s strings, then applies privacy amplification to obtain a secret key uncorrelated with Eve.Reconciliation uses authenticated public communication; privacy amplification compresses the reconciled string.
- Secret-key rate: The actual secret-key rate includes reconciliation inefficiency through Kreal = H(X|Z) − fH(X|Y), with f greater than 1.H(X|Y) is the minimum information Alice must send to help Bob correct his string.
- Evaluation criteria: Because imperfect reconciliation lowers secret-key rates and limits QKD range, efficiency must be balanced against complexity and rapidity, especially for interactive schemes.Communication latency can become important when protocols require many exchanges.
- BSC model: For binary QKD protocols, Alice’s and Bob’s strings are modeled as the input and output of a BSC with known crossover probability p.This setting assumes binary variables and uncorrelated, symmetric errors.
- Operating regime: Even perfect reconciliation permits secret-key distribution only below an 11% bit-error rate, while typical implementations operate between 3% and 10%.The paper focuses on this practical error-rate range when comparing reconciliation schemes.
A. The Cascade protocol
Cascade reconciles strings through repeated public interaction, combining randomized block permutations, parity checks, and binary searches. Its simplicity and reasonable efficiency come with substantial communication overhead and latency.
- Protocol structure: Cascade runs a number of passes determined by the estimated error probability, with block sizes doubling after each pass.The initial block size is critical, with an empirical optimum near 0.73/e for estimated error probability e.
- Error correction: In each block, Alice and Bob exchange parities and use binary search to locate and correct an error when the parities disagree.The search repeatedly splits the block and exchanges half-block parities.
- Iterative correction: Cascade continues correcting errors across blocks from earlier passes until the set of blocks with odd error counts is empty.Each newly corrected error can add or remove blocks from this set.
- Communication overhead: Cascade is highly interactive, and the communication time required for many exchanges can limit achievable key-generation rates.This limitation is especially relevant for satellite links, free-space QKD, and high-latency networks.
- Role as baseline: Cascade remains widely used because of its relative simplicity and reasonable efficiency, despite its communication demands.The paper uses it as the principal comparison because the proposed LDPC approach is non-interactive and aims to improve efficiency.
B. Other work on information reconciliation protocols
Prior reconciliation research explored interactive variants of Cascade and modern coding methods, with LDPC and turbo codes used mainly for continuous-variable QKD. The discrete-variable case remained comparatively underdeveloped despite forward error correction’s single-message advantage.
- Interactive alternatives: Cascade-inspired protocols have sought to reduce interactivity by optimizing block lengths or replacing binary search with Hamming-code correction, as in Winnow.Block-length optimization can reduce rounds at very low error rates.
- Continuous-variable work: Modern turbo and LDPC coding techniques were developed mainly for continuous-variable reconciliation, including methods that first convert continuous variables into binary strings.Sliced Error Correction is cited as an approach for this conversion.
- Discrete-variable gap: Less work adapted modern coding techniques to discrete-variable reconciliation, although forward error correction can approach the Shannon limit and requires only one syndrome message.The paper cites LDPC-based discrete-variable implementations but identifies limited comparative evaluation.
III. OPTIMIZATION OF LDPC CODES FOR THE BSC
The paper optimizes LDPC codes specifically for the BSC by searching constrained degree distributions and evaluating their asymptotic thresholds. The resulting thresholds approach the Shannon limit, with large finite-length codes suitable for QKD.
- LDPC codes are linear codes with sparse parity-check matrices and can be represented by bipartite graphs of variable and check nodes.
- BSC-specific LDPC optimization uses Differential Evolution to evolve constrained candidate degree-distribution parameters.The algorithm mutates and recombines candidate vectors, retaining lower-cost solutions.
- The degree distributions λ(x) and ρ(x) are normalized and constrained so codes share the same rate while their thresholds remain comparable.Fixed coefficients and a rate-setting coefficient reduce the remaining search space to D = L + R−5 parameters.
- Discretized density evolution evaluates candidate codes and provides a lower bound on the real threshold for the BSC.The threshold marks the asymptotic boundary of the error-free region as block length tends to infinity.
- For all representative rates, the optimized thresholds are very close to the Shannon limit.Finite-length experiments were similar, using code lengths of 10^6 suited to large QKD blocks.
IV. EXPERIMENTAL RESULTS
The experiments compare Cascade with optimized LDPC codes at block length 10^6 using belief-propagation decoding. Residual errors below 1.5 · 10^-6 are handled by concatenation with a high-rate BCH code.
- The experimental comparison uses block length 10^6 and decodes the LDPC codes with belief propagation.
- The remaining bit error probability is below 1.5 · 10^-6.
- Residual errors are handled by concatenating the reconciliation code with a BCH code of typically 0.998 rate.
A. Reconciliation Efficiency
Reconciliation efficiency measures the information disclosed relative to the BSC entropy limit. Optimized LDPC codes outperform Cascade above moderate error rates, with the nine-code set consistently better above 5%.
- An ideal BSC reconciliation reveals h(p), whereas a real protocol reveals f(p)h(p).
- Cascade is within 10% of the Shannon-limit efficiency at low error rates, but its efficiency decreases as crossover probability increases.
- Discrete LDPC code thresholds produce a saw-shaped efficiency curve, which becomes smoother as more codes are used.Each string is assigned the code whose threshold is the smallest one greater than its measured error probability.
- Optimized LDPC codes outperform Cascade when the error rate exceeds 2%, while the nine-code set is always better above 5%.The paper states that this gain can significantly affect achievable secret-key generation rates.
B. Secret Key Rate and Local Randomization
Reconciliation efficiency can be translated into the practical secret-key rate, the relevant performance measure for QKD. Local randomization is studied to use LDPC codes near their thresholds, and the resulting protocol approaches the theoretical error-rate limit more closely than Cascade.
- The practical secret-key rate Kreal(p) is the figure of merit obtained by translating reconciliation efficiency f(p) into achievable key rate.
- Local randomization deliberately worsens the error rate before reconciliation so LDPC codes operate closer to their thresholds, where efficiency is better.
- With the proposed LDPC protocol, the maximal admissible bit error rate becomes close to the theoretical 11% limit, compared with less than 9.5% for Cascade.
V. CONCLUSION
LDPC codes provide an effective alternative to Cascade for reconciling correlated variables, with improved efficacy above crossover probabilities of 0.02 and far less communication. Their BSC optimization uses thresholds near channel capacity and may benefit QKD and other secret-key agreement scenarios.
- LDPC codes offer similar reconciliation efficacy to Cascade at small crossover probabilities and significant improvement above 0.02.
- LDPC codes require a single information exchange, whereas Cascade consumes communication resources through high interactivity.
- LDPC codes optimized for the BSC achieve thresholds near channel capacity.
- The results may affect QKD performance and apply to secret-key agreement scenarios including wiretap and Maurer’s satellite channels.