Make your paper interactiveCreate

Text from the interactive explanation

A Reconciliation Strategy for Real-Time Satellite-Based QKD

Xiaoyu Ai, Robert Malaney, Soon Xin Ng

Original paper

Ai · Malaney · Ng — IEEE Communications Letters, 2020

In 2016 the Micius satellite shared quantum keys with the ground across 1,200 km — an order of magnitude farther than links on the ground. But its raw key was stored and only processed after the quantum signalling was over. To make secret keys in real time, the ground station's error-correcting decoder has to keep pace with the photons pouring in. This paper shows how to choose the code so that it can.

ARate-adaptive code

Reveals the fewest parity bits (the RRP scheme the paper compares against).

BThis paper's strategy

Meets the key-rate target with the fastest decoder, picked from a look-up table.

Two copies, a few typos

The satellite (call it Alice ) sends single photons, one bit on each. Every photon is prepared in one of two settings, and the ground station ( Bob ) measures each one in a setting of its own. Afterwards they announce which settings they used — never the bits — and keep only the rounds where the settings matched. What remains is the sifted key : two long strings of bits that ought to be identical.

They never quite are. Turbulent air, stray light and imperfect detectors flip a few bits. So would a spy: measuring a single photon disturbs it. The share of positions where Bob's bit differs from Alice's is the quantum bit error rate , or QBER . Since nobody can tell noise from spying, the protocol must treat every error as if an eavesdropper — traditionally Eve — caused it.

2 typos in 64 bits

Bob has to find and fix his typos. But the two ends can only talk over an ordinary public channel — and Eve hears every word.

Fixing typos with parity clues

Alice can't just read out her key. Instead she announces parities : for a small group of positions, whether her bits there add up to an odd or an even number. Bob works out the same parities from his own bits. Wherever his answer differs, at least one bit in that group is a typo.

Try it. The squares are Alice's announced parities, with Bob's own result written above each one; lines show which of the seven bits each parity covers. A glowing square disagrees with Bob's copy.

Bob's copy has one typo. Two of Alice's three parities disagree with his bits. Tap the bit you think is wrong.

Every parity Alice announces is a bit of information Eve hears too, so one bit must later be cut from the final key. The share of the block that is not given away is the code rate , Rc. Three parities on seven bits leave Rc = 4/7; six leave only 1/7. Fewer parities keep more key — but make the decoder's job harder, and sometimes impossible.

Real blocks hold thousands to millions of bits, and each parity covers only a handful of them: a low-density parity-check (LDPC) code . Nobody solves those by eye. A decoder program passes "beliefs" back and forth between bits and parities, again and again, until every parity agrees. Each full pass is a sweep (an iteration).

How many sweeps does a real decoder need, and what decides it?

Watch a real decoder work

Here is Bob's block of 1,024 sifted bits. Coral squares are typos. In each sweep the decoder visits every parity in turn — the serial schedule the paper analyses — and updates its belief about each bit it touches (the amber shimmer). Watch the typos dissolve.

Predict first. If Alice reveals fewer parities (a higher code rate), will the decoder need more sweeps or fewer?

0.21 below the Shannon limit (0.81)

Sweeps needed vs code rate

Each dot averages blocks decoded at that setting; hollow coral dots mean the decoder often gave up (60 sweeps). The hatched zone lies beyond the Shannon limit.

There is a hard wall. Information theory says that at a given QBER no code can work if it reveals less than a share h(QBER) of the block, where h is the binary entropy — a measure of how unpredictable the typos are. So the code rate can never exceed 1 − h(QBER) , the Shannon limit (the "capacity" of the channel). Near that wall decoding slows dramatically; beyond it, it fails.

Every sweep costs arithmetic. Counting the decoder's steps, the paper finds about 7 floating-point operations per connection between a bit and a parity, per sweep. Fewer sweeps means more bits corrected per operation — the decoding rate C , in bits per arithmetic operation.

Simulated liveA 1,024-bit code with every bit in three parities, built by progressive edge growth (the construction the paper assumes) and decoded by belief propagation in your browser. It shows the trend; it is not the paper's optimised codes, which get much closer to the Shannon limit than this small one.

So why not always stay far from the wall? Because every extra parity is key you must throw away. How much can you afford to lose?

The secrecy budget

Follow one block of N sifted bits to the end. Part of it was announced as parities. Part must be sacrificed because Eve might have learned it from the disturbance she caused — a noise tax set by the QBER, removed by a last step called privacy amplification. And because a finite block is only a finite sample, the protocol adds a safety margin so its promises hold except with a tiny failure probability ε (for example 10−10, one in ten billion). Whatever is left is secret key.

Short blocks pay extra. With few bits, Alice and Bob can't be sure the QBER they measured is the true one, so the tax is charged at a pessimistic QBER plus a fluctuation allowance μ . Longer blocks shrink μ and the margin.

In this protocol (A-QKD) both ends choose the key setting 75 % of the time, so only 0.75 × 0.75 ≈ 56 % of pulses feed the key. The key rate in bits per pulse is 0.5625 × the secret share of the block.

–

–

Shortest block that meets the target

The curve is the minimum N from Eq. (1) at each code rate; the white dot is your setting. Left of the curve's end, no block is long enough. Right of the dashed line, no decoder can work.

What to notice. Lower the code rate and the secret share shrinks — but a longer block wins some of it back. So you can keep meeting a fixed target while backing away from the Shannon wall, right up to the point where no block is long enough.

That leaves a window of code rates that all meet the target. The decoder lab showed that inside this window, the ones farther from the wall decode in fewer sweeps.

CalculatedFrom the paper's Eq. (1), with its settings: px = 0.75, a tolerated QBER 0.01 above the true QBER, and ε split as εcor = 9×10−11, εsec = 10−11 (or 9×10−15 and 10−15). Like the paper, we treat this upper bound as exact.

f(Qtol, N) = px2 · [ 1 − h(Qtol + μ) − Nleak/N − log2(2 / (εcor εsec2)) / N ] μ = √( (N+K)(K+1) / (N K2) · ln(2/εsec) ), K = N (1 − 1/px)2 Nleak = (1 − Rc) N, h(x) = −x log2x − (1−x) log2(1−x)

K is the number of bits spent estimating the QBER; Qtol is the QBER the protocol tolerates. The paper writes this for its A-QKD protocol, following the finite-key analysis of Tomamichel and colleagues (2012).

Inside that window, which code should you pick? That is the question the paper answers.

Strategy-I: hit the target, then decode fastest

The usual goal is the most key per pulse — codes squeezed against the wall, and a slow decoder. Ai, Malaney and Ng turn the question around. Fix the key rate you need, ft, and the failure probability you'll accept, ε. Then search for the code that decodes fastest while still meeting both. Their loop (redrawn from the paper's Fig. 1):

Press Run Strategy-I to climb down the ladder of code rates.

Each rung shows: shortest block N (bits) · average sweeps · decoding rate C (bits per operation) · time to decode one block.

Step 1 calculatedSteps 2–3 simulatedA miniature of the paper's procedure: Step 1 uses the paper's Eq. (1); Steps 2–3 run the small live decoder from Chapter 3 on 24 test blocks per rung, instead of the paper's optimised codes, density-evolution analysis and girth bounds. Speeds are therefore illustrative. Ties within 3 % go to the shorter block. The time per block uses the paper's 8×10−8 s per operation; the paper notes, for example, about 40 s to decode one 108-bit block.

One code, one QBER. But a satellite's QBER never sits still.

A sky that keeps changing

During a pass the satellite climbs from the horizon to nearly overhead and sinks again. Low in the sky its photons cross far more air, so fewer arrive and more are flipped. In satellite QKD the QBER is, in the paper's words, "very much a time-dependent quantity" — a code tuned for one minute is wrong for the next.

The paper's answer: the satellite-to-ground channel stays steady for roughly 10–100 milliseconds at a time, far longer than it takes to load a new code from memory. So build a look-up table in advance — for each QBER from 0 to 10 %, the code that Strategy-I picks — then, during the pass, estimate the QBER and slot in the matching code.

The paper calls a system viable when (i) the decoder's speed — C divided by the time per arithmetic operation, tp — is at least the incoming sifted-key rate at every QBER that still gives key, and (ii) each block decodes within a set time limit.

Below, the opening scene's numbers are laid out over a whole pass. Drag across the chart to scrub through it. Raise the photon rate until even the strategy's decoder falls behind, then give it faster hardware.

–

Illustrative passSame invented pass, photon rate and buffers as the opening scene; decoder speeds from the paper's Fig. 2 values. A uses the rate-adaptive scheme's curve, B the paper's strategy (A-QKD, ε = 10−10, ft = 0.01). This checks condition (i) only.

So how much does the strategy actually gain, and where does it run out? Here are the paper's own results.

What the authors found

The paper applies Strategy-I to two protocols. A-QKD is an asymmetric version of the classic BB84 protocol that assumes perfect equipment. LT-QKD ("loss-tolerant") also guards against imperfect photon sources, at the cost of a more demanding security analysis. For QBERs from 1 to 10 %, they calculated the decoding rate C of the codes their strategy picks and compared it with a widely used rate-adaptive scheme (RRP) that minimises the parities revealed.

Tap any point to read its value.

From the paperRe-drawn from the paper's Fig. 2; values read by eye (about ±0.01). For LT-QKD the horizontal axis is the estimated QBER, Q̂. Mbps conversions use tp = 8×10−8 s.

The strategy beats the rate-adaptive scheme. For both protocols its decoding rate is higher than RRP's — at a QBER of 1 % about 0.58 versus 0.09 bits per operation for A-QKD (ε = 10−10, ft = 0.01).

Speed falls as the QBER rises. At low QBER the chosen code sits far below the Shannon limit and needs few sweeps while still meeting ft. At high QBER the code must sit close to the limit to find any finite block length, so it is slower.

Stricter security costs speed. A smaller ε or a higher target ft pushes the code nearer the limit and lowers C. The block length N grows too, but N itself does not change C, because the operations also grow in proportion to N.

Handling imperfect sources is harder. LT-QKD follows the same trend at lower speeds, and above an estimated QBER of about 0.04 (0.03 for ε = 10−14) no finite block meets the target at all, so C drops to zero.

Decoding speed at QBER 1 % on an HP Z8 G4 workstation (8×10−8 s per operation); 0.97 Mbps at 5 %.

In a channel with the range of QBER reported by Micius (ε = 10−10, ft = 0.01), the incoming quantum signal rate would have to exceed this before the A-QKD decoder became the bottleneck — 7.5c Mbps for LT-QKD. c = 8×10−8/tp: faster hardware raises it.

Time to decode one block of 108 bits on that workstation — why real-time systems also need a cap on decoding time per block.

Typical block lengths

The block length N (bits) found by the strategy, from the paper's Table I. "–" means no finite block meets the target.

How solid is this?

These results are calculations and simulations, not measurements on a satellite link. The sweep counts come from density evolution — a standard way to predict how a decoder's errors shrink sweep by sweep — switching to a bound based on the shortest loops in a progressive-edge-growth code when loops start to matter. The key-rate formula is treated as exact, and turning C into bits per second depends on the hardware's time per operation.

The authors stress that the recipe is general: it could be applied to other QKD protocols, other decoding algorithms, and other design targets — for example, setting only the total ε and optimising how it is split.

Every photon counts

Micius showed that the physics works across 1,200 km. Turning that into a service that makes keys while the satellite is still overhead means the ordinary computing on the ground must never become the bottleneck. This letter offers a design rule for exactly that: meet the key-rate and security targets you need, then make the decoder as fast as possible — and keep a table of such codes ready for a sky whose error rate changes by the minute.

Because the decoder runs as fast as the targets allow, the chance that a buffer overflows and quantum signals are thrown away is as small as it can be. The authors expect their strategies to "point the way to the real-world deployment of practical quantum key distribution systems where all quantum signals can be utilised in the key growth."

The paper

Xiaoyu Ai, Robert Malaney and Soon Xin Ng. "A Reconciliation Strategy for Real-Time Satellite-Based QKD." IEEE Communications Letters 24(5): 1062–1066, May 2020. DOI: 10.1109/LCOMM.2020.2977914

Read from the author-hosted copy of the published version: southampton.ac.uk/~sxn/paper/comms_letter2020_qkd.pdf. Original article © 2020 IEEE. Figures on this page are our own re-drawings of the paper's data and diagrams, not reproductions.

What is what on this page

From the paperFig. 2 decoding rates (read by eye), Table I block lengths, the workstation speeds, the Micius-range statement, the Strategy-I loop and Eq. (1).

Calculated hereThe secrecy budget and minimum block lengths, computed from Eq. (1) with the paper's parameters.

Simulated hereThe 1,024-bit decoder and the Strategy-I miniature: real belief propagation on a small code, illustrating trends rather than the paper's numbers.

IllustrativeThe satellite pass: its QBER profile, photon rates and buffer sizes are invented; only the decoder speeds come from the paper.

Topics in this iPaper

Engineering
For real-time deployment of QKD in space we would like to consider the generation of key rates in real time

Section I, page 1062

Computer science
(ii) design a rate-Rc LDPC code; (iii) calculate C; (iv) reduce Rc and return to (i) until the maximum of C is found

Section III-A, page 1063

Physics
classical processing should occur at a rate faster than the incoming quantum signalling

Section I, page 1062

quantum key distribution
we would like to design QKD solutions that provide for a target QKD key rate, in bits/pulse, at a specified upper-limit on the failure probability

Abstract, page 1062

low density parity check codes
Although our new design strategy detailed here is for LDPC codes and applied to two specific QKD protocols

Abstract, page 1062

information reconciliation
In the classical processing phase of QKD, the Key Reconciliation (KR) is the slowest part of the process

Section I, page 1062

satellite communications
In satellite-based QKD, the QBER is very much a time-dependent quantity

Section V-C, page 1066

finite key analysis
We adopt the finite-length security analysis of A-QKD in [6]

Section III-B, page 1063

belief propagation
we adopt the DEA for the serial-schedule Belief Propagation (BP) decoder

Section IV-A, page 1064

A Reconciliation Strategy for Real-Time Satellite-Based QKD — Interactive explanation | iPaper.ai