Make your paper interactiveCreate

Text from the interactive explanation

Short Codes and Entanglement-based Quantum Key Distribution via Satellite

Xiaoyu Ai, Robert Malaney, Soon Xin Ng, Lajos Hanzo

Original paper

Quantum keys from space · short error-correcting codes

A satellite beams pairs of linked photons to two ground stations about 1,000 km apart. Pairs that both stations happen to measure the same way add one bit each to a random string that only those two stations share — the raw material of a secret key. But from orbit the bits trickle in at only a few per second, and before they become a key they must be checked and corrected in fixed-size blocks. How big should a block be?

Illustration Time-lapsed ×200 while the satellite is in view; each gold pair stands for about 140 bits. Block fill times are exact arithmetic for the chosen rate.

Predict

At 3 bits per second, how long does it take to fill a single million-bit block?

01

Twin photons, almost-matching bits

The satellite carries a source of entangled photon pairs. Measure both members of a pair the same way and their results are linked — even when one photon lands at one station and its twin lands 1,000 km away. Each station picks its measurement setting at random for every photon. Afterwards they announce their settings in public (never their results) and keep only the pairs where the settings matched. In the protocol the paper uses, that is 1 pair in 6 .

Perfect entanglement would make the kept bits match exactly. Real entanglement is imperfect. The paper describes the pair state with one quality number, m (m = 1 is perfect), and treats this as the only source of error. The weaker the entanglement, the more often Bob’s bit comes out flipped. That flip probability, p, is the noise every later step has to beat.

p = 1.22% — about 1 bit in 82 disagrees

Mismatches so far: 0 of 0 bits

How do they know the photons were really entangled?

Before trusting any of this, the stations sacrifice a share k of their pairs to a test — the CHSH game . Each round, both get a random question (a measurement setting) and must give answers that obey a simple rule. Perfectly entangled photons win about 85.4% of rounds (cos² π/8); no strategy without entanglement can win more than 75% . If the win rate falls below a preset tolerance, they abort. Because the test only looks at questions and answers, the stations need not trust how their equipment works inside. That is what device-independent quantum key distribution means — the robust flavour this paper studies.

With m = 0.80, the test sample should win ≈ 84.5% of rounds.

The real Micius satellite (launched August 2016) sent entangled pairs to two stations with the photons travelling 1,600–2,400 km in total, and measured a Bell value of 2.37 ± 0.09 — above the limit of 2 for any non-entangled explanation (equivalent to winning about 80% of CHSH rounds).

Your sky’s noise: p = 1.22% . The next chapters carry it forward.

Note The 75% limit and the win-rate formula (½ + (√2/4)(1 − 2p) for this idealised state and the paper’s measurement settings) are standard background, not results of the paper.

02

Fix the differences in public — without saying the bits

Alice and Bob now hold strings that match except for a few flipped bits. They can only talk over a public line that anyone can hear, so Alice never reads her bits out. Instead she announces parities : for small groups of positions, whether her bits there add up to even or odd. That list is her syndrome . Bob computes the same parities on his bits. Wherever a parity disagrees, an error is hiding in that group.

Every announced parity leaks a little information to a listener, so at the very end the stations shrink their key to squeeze that leak out — privacy amplification .

12 bits, 6 parity checks. Each bit belongs to its own pair of checks, so one wrong bit lights exactly two lamps. Tap a bit to flip Bob’s copy until every lamp agrees.

2 checks disagree — find the flipped bit.

The lesson: a code can fix only so many errors per block. With one error, the lamps point straight at it. With two or three, several different fixes can make every lamp agree — and Bob, who cannot see Alice’s bits, may pick the wrong one. A wrongly “fixed” block is useless and must be thrown away. Real codes use the same local voting, but with thousands of bits and checks.

03

The cliff: why longer blocks fix more

Real reconciliation scales the parity game up. The paper’s code has 2,400 bits and 1,200 checks (code rate ½: one check for every two bits). Each bit sits in 3 checks and each check covers 6 bits. The decoder passes votes back and forth along the connections: each check tells each bit what the other bits imply, and a bit changes its mind when the checks outvote what it received. The paper uses this simple scheme, called Gallager A , to find its thresholds.

Below, every block is really decoded in your browser, with codes built the same way as the paper’s. One block plays in slow motion on the grid; many more are decoded in the background to count failures. Watch closely: in the first iterations the guesses can get worse before the votes settle.

Predict

At noise p = 3.5%, which block length fails least often?

N = 2,400 · p = 3.50%: 0 of 0 blocks failed

Decoding…

At 3 bits/s this block takes 13 min 20 s of detection time to fill.

Live Simulated in your browser with codes built like the paper’s (Progressive Edge Growth, rate ½, every bit in 3 checks, Gallager A decoder, up to 60 iterations). These are not the authors’ codes, and their failure rates need not match the paper’s exactly.

What to look for. Longer blocks hold out to higher noise and then fall off a steeper cliff: nearly every block decodes below it, nearly every block fails above it. As blocks grow, the cliff closes in on a single noise level — the code’s threshold , ≈ 0.039 for this rate-½ design. The catch is in the last readout: a longer block takes longer to fill.

The paper’s comparison codes are a million bits long and use a more elaborate “irregular” design (bits in different numbers of checks). Their rate-½ threshold is ≈ 0.107, close to the ultimate limit of about 0.11 for any rate-½ code (where the binary entropy of p reaches ½ — textbook information theory).

Imagine an infinitely long code with no short loops. Then every message in the decoder is wrong with the same probability, and one line of algebra — the paper’s Eq. 5 — tracks how that probability changes from one iteration to the next. If it shrinks to zero, the code decodes; if it gets stuck, it fails. The largest starting noise that still shrinks to zero (below 10⁻⁴) is the threshold.

Real codes are finite and do contain loops. The Progressive Edge Growth (PEG) method builds the graph one connection at a time, always linking a bit to the check that is farthest away in the graph so far. That keeps the shortest loop as long as possible: in our 2,400-bit code the shortest loop has 8 connections. The paper’s Eq. 4 estimates that for N = 2,400 the decoder can run about 2Lc ≈ 7 iterations before any message could return to where it started (Lc ≈ 3.5).

04

Turn the dial: puncturing to match the weather

A rate-½ code announces one parity for every two bits: robust, but a lot of public chatter and decoding work. When the noise is low, the stations can afford fewer checks. They puncture the rate-½ “mother code” — hiding some of its bits and checks — to get a higher-rate code that reconciles faster. The price: a higher-rate code tolerates less noise. The paper’s Fig. 1 shows how much less.

Read it like a weather dial. Lower noise lets the stations use a higher rate — fewer checks, faster reconciliation. As the paper puts it: “when the estimation of bit-flip probability becomes lower, LDPC codes with a higher code rate can be used for faster reconciliation.” But across every rate, the 2,400-bit code’s threshold is over a factor of two smaller than that of the capacity-approaching million-bit benchmark. That is the price of a short block.

05

From photons to key: what the paper found

Put the whole protocol together and count what survives, per detected photon pair. A share k of pairs goes to testing and is then discarded. Sifting keeps 1 in 6 of the rest — the raw key. Reconciliation fixes it block by block. Privacy amplification then shrinks it to a fraction 1 − H₂(p) (H₂ is the binary entropy), leaving the final secret key.

Using your sky’s noise p = 1.22%.

The ceiling (1 − k)/6 · (1 − H₂(p)) assumes every block decodes. Lowering k raises it, but the paper notes the trade-off: a smaller test sample estimates the CHSH score and the noise less accurately, making an eavesdropper harder to spot — and the decoder itself needs a good noise estimate.

The findings, in plain words

Up to p ≈ 0.03 the short code costs almost nothing. The decoder corrects essentially all errors in a block, so the 2,400-bit LDPC curve sits on the ideal ceiling (the rate-½ threshold is ≈ 0.039).

Between 0.04 and 0.06 the key rate drops drastically for the LDPC code, because decoding failures rise steeply past the threshold.

LDPC is slightly better at low noise; the turbo code is better at high noise. The turbo code (two 8-state convolutional codes, 4 decoding iterations) degrades more gently. For turbo reconciliation Alice sends parity bits and Bob decodes using his own raw key as side information.

Verdict: “short-block length PEG LDPC codes are viable candidates” for satellite links, and the authors report similar key rates for LDPC codes between 1,000 and 10,000 bits (not shown in the paper).

Paper These are the authors’ computer simulations of the full protocol, not satellite measurements. The theoretical curve is a standard entanglement-based rate without a testing fraction, shown by the paper for comparison.

06

Back to the sky: key in minutes, not days

Return to the opening question with everything you now know. Pick a reconciliation plan, set the data rate and the noise, and watch when secret key actually becomes usable.

Assumptions Times are detection time, counting only while the satellite is overhead. In calendar time the wait is longer, because each pass overhead is brief. Short-code success = the paper’s Fig. 2 key rate ÷ the ideal-decoder ceiling. The benchmark block is assumed to always decode below its ≈ 0.107 threshold (illustrative).

The trade-off the paper highlights is throughput against latency. In its key-rate model a short code costs key only through blocks that fail to decode — negligible at low noise, severe past the threshold. What it buys is time: a usable key after minutes of detection instead of days. The authors give one reason that matters: situations where “urgent command and control requirements cannot wait for the accumulation of a one-time pad acquired via multiple satellite passes.”

07

What comes next, and where this comes from

The authors’ own outlook

Their analysis puts an upper limit on the secret key rate; it does not show that secure keys at these rates are achievable.

No formal finite-size, composable security parameter has been applied to these short codes. A block length below which device-independent security cannot be reached is expected, and worth identifying.

Formal security at these lengths may need extra assumptions, for example relaxing to one-sided device-independent QKD. Loophole-free testing issues are not covered.

The codes were not further optimised for satellite links beyond state-of-the-art construction; that is left to future work.

The picture the paper leaves is of a satellite key that need not wait for days of photons: blocks of a few thousand bits fill after minutes of detection rather than days, and still give useful key. In the authors’ words, “the prospects for implementation of satellite-based DI-QKD (or some variants thereof) appears hopeful.”

Source

Xiaoyu Ai, Robert Malaney (School of Electrical Engineering and Telecommunications, UNSW Sydney), Soon Xin Ng and Lajos Hanzo (School of Electronics and Computer Science, University of Southampton). “Short Codes and Entanglement-based Quantum Key Distribution via Satellite.” Author-hosted manuscript: southampton.ac.uk/~sxn/paper/ShortLengthLDPC-Final.pdf. No venue, year or DOI is printed on this version.

Credits

Charts in chapters 4 and 5 are redrawn from data read off the paper’s Figs. 1–2 (approximate). All animations are original illustrations. The decoder lab and the reference curves in chapter 3 are our own simulation of codes built the paper’s way, not the authors’ code. Micius figures are as described in the paper.

Glossary

Topics in this iPaper

Physics
A satellite, used to generate and distribute entangled pairs of photons, is considered to be approximately overhead the two geographically distant ground stations.

Section II.A System Settings, page 2

Engineering
this robust form of QKD via space will require a renewed focus on short-block length error-correcting codes in order to facilitate the reconciliation phase of the key distribution.

Abstract, page 1

Computer science
Alice and Bob use a Toeplitz matrix as a 2-universal hash function

Section II.B Privacy Amplification, page 3

quantum key distribution
Quantum key distribution (QKD) provides the opportunity to deliver unconditional communication security.

Abstract, page 1

device independent quantum key distribution
a feature that supports the most robust form of QKD, namely device independent (DI)-QKD.

Section I Introduction, page 1

low density parity check codes
we explore, for the first time, the use of short state-of-the-art low density parity check (LDPC) codes for the reconciliation phase of DI-QKD

Section I Introduction, page 1

information reconciliation
useful rate-adaptive reconciliation by puncturing or shortening from a Mother code is possible

Section II.C, page 3

turbo codes
For additional comparison purposes, we have also considered the performance of a turbo code

Section II.C, page 3

satellite quantum communication
as verified by quantum entanglement distribution from a low Earth orbit satellite.

Abstract, page 1

Short Codes and Entanglement-based Quantum Key Distribution via Satellite — Interactive explanation | iPaper.ai