From Raw Bits to a Usable Key

4.1 Reconciliation and verification

4.1.1 Account for the transcript

Alice and Bob usually have correlated rather than identical raw strings. A reconciliation protocol reveals information, such as parity checks, so Bob can correct his errors. Every public bit can also help Eve. A conservative leakage budget counts the information revealed during reconciliation, and verification messages must be included in the security accounting as well. Verification then checks whether the corrected strings agree, often using a randomly chosen universal hash. For a suitable t-bit hash family, the chance that unequal strings collide is bounded by 2⁻ᵗ. The hash seed can be public, but the transcript must be authenticated. Reconciliation success is only correctness: two identical strings can still be entirely known to Eve. Privacy amplification addresses that separate question after the leakage is bounded.

4.1.2 Correct a string using a syndrome

Work over the binary field: addition is XOR and multiplication is ordinary bit multiplication. Alice has a column vector x and Bob has \(y=x\oplus e\). For a parity-check matrix H, Alice announces \(s_A=Hx\), Bob computes \(s_B=Hy\), and their difference is \(s_A\oplus s_B=He\). The syndrome depends only on the error pattern, so a decoder can search for a likely e without learning x from scratch.

The seven columns are the nonzero three-bit representations of positions 1 through 7. Under a promise of at most one error, a nonzero syndrome directly identifies its position. Let \(x=1011001\), and suppose Bob's fifth bit is flipped, so \(y=1011101\). Alice's syndrome is 010, Bob's is 111, and their XOR is 101: binary five. Bob flips position five to recover x.

The promise is crucial. Errors in positions one and two produce syndrome \(001\oplus010=011\), which imitates a single error in position three. Blindly applying the one-error decoder then leaves three wrong bits. Reconciliation must be followed by verification; a decoder returning a string is not evidence that the string equals Alice's.

4.1.3 Count rank, communication, and verification separately

For a uniform n-bit x and a rank-r matrix H, each possible syndrome leaves \(2^{n-r}\) candidates. Thus the syndrome leaks exactly r bits in this special uniform example. Repeating a row does not add an independent linear constraint, but a general entropy bound can conservatively charge the full transcript length. Adaptive protocols must also account for messages that select branches, lengths, and positions when these depend on the data.

Verification uses a newly selected hash from a two-universal family: for any unequal x and y, \(P_F[F(x)=F(y)]\le2^{-t}\) for a t-bit output. The probability is over the independent choice of F after the strings are fixed. A fixed short checksum has no such guarantee against arbitrary chosen differences. The verification hash and seed join the public transcript; the t-bit value can cost up to t additional entropy bits. Authentication protects the messages from substitution and has a different purpose.

4.2 Min-entropy and hashing

4.2.1 Compress uncertainty into uniformity

Conditional min-entropy captures Eve's optimal guessing probability for a classical string X with quantum side information E: Hmin(X|E)=−log₂ pguess(X|E). A quantum-proof strong extractor converts a source with certified entropy into a shorter key close to uniform even when its independent seed is published. Universal hashing supplies one such construction. For an unsmoothed entropy lower bound k after accounting for the transcript, a conservative leftover-hash choice is ℓ≤k−2 log₂(1/εPA), giving trace-distance error at most εPA. Smoothing can improve the entropy bound but adds its own error contribution. The seed must be independent of the source and adversary before extraction. A deterministic truncation has no comparable general guarantee: Eve might already know exactly the prefix being retained.

4.2.2 Distinguish min-entropy from average uncertainty

For a classical distribution with no side information, the most likely string is Eve's best guess, so \(H_{\min}(X)=-\log_2\max_x P(X=x)\). Let a two-bit variable have probabilities \((1/2,1/4,1/8,1/8)\). Its Shannon entropy is 1.75 bits, but its min-entropy is only one bit. The different answers reflect different operational questions: average description length versus the probability of one successful guess.

For quantum side information, Eve can choose a measurement adapted to the states she holds. If \(\rho_{XE}=\sum_xp_x|x\rangle\langle x|\otimes\rho_E^x\), then

Define \(H_{\min}(X|E)=-\log_2p_{\rm guess}(X|E)\). Perfectly distinguishable records make the guessing probability one even if X is uniform. Identical records leave only the prior distribution. Privacy amplification must use the conditional quantity; an entropy estimate from a random-looking raw string alone is insufficient.

4.2.3 Construct a hash and explain why its seed can be public

A binary \(\ell\times n\) Toeplitz matrix is constant along each diagonal and is specified by \(n+\ell-1\) random bits. Uniformly choosing those bits gives a two-universal family. For n=4 and ℓ=2, a particular member is

To see the collision property, set \(d=x\oplus y\ne0\). Hash collision means Td=0. Choose the first nonzero coordinate j of d. Each successive output row contains a new diagonal seed bit multiplying that coordinate. Conditional on the later diagonal bits, those ℓ equations determine ℓ distinct uniform seed bits in triangular order. Exactly a fraction \(2^{-\ell}\) of seeds satisfy all equations. This argument works for each fixed nonzero d, which is precisely the required pairwise collision bound.

The quantum leftover-hash lemma, used here as a stated theorem, turns that family into an extractor. If \(H_{\min}(X|E)\ge k\), F is independent of XE, and K=F(X), the unsmoothed trace-distance bound is

F appears on both sides: the output remains approximately independent even after the seed is published. Choose \(\ell\le k-2\log_2(1/\epsilon_{\rm PA})\) for a conservative bound no larger than \(\epsilon_{\rm PA}/2\), hence certainly below \(\epsilon_{\rm PA}\). The theorem tolerates arbitrary quantum E; the classroom collision proof alone does not prove that quantum statement. Smooth versions replace k by a smooth entropy and add a convention-dependent smoothing contribution.

One concrete matrix multiplication does not demonstrate extraction for a source. The guarantee averages over an independently chosen seed and depends on the certified entropy. Choosing a matrix after inspecting X, or reusing a data-dependent seed without a theorem, invalidates the independence step.

4.3 A finite-block ledger

4.3.1 Keep each deduction visible

A practical analysis begins with a proven entropy bound for the actual protocol and observed data. It then subtracts leakage and extraction costs, allocates failure probabilities, and records whether authentication consumes previously secret bits. Do not subtract a transcript twice: either condition the entropy on it already or apply a leakage bound explicitly. Keep raw block size, test sample size, retained key length, and emitted pulse count in separate columns. Their units are different. A finite-key calculation must identify a theorem covering the actual source, measurement, sampling, and attack model. The arithmetic below starts from an assumed certified entropy bound; it illustrates bookkeeping only and does not derive that bound from a measured QBER. This distinction prevents a plausible spreadsheet from masquerading as a device security certificate.

4.3.2 Build the length formula from its inputs

Suppose a valid analysis gives a lower bound \(k_{\rm pre}\) on the raw string's conditional min-entropy before reconciliation. Let \(\lambda_{\rm EC}\) bound reconciliation leakage, let t be the verification tag length, and use the conservative extraction penalty above. The length calculation is

If ℓ is nonpositive, output abort rather than an empty “successful” key. The expression presumes that the entropy theorem and transcript conditioning match. Net expansion additionally subtracts the pre-shared secret bits consumed by authentication, while the actual output key still has length ℓ. Verification correctness has error at most \(2^{-t}\); authentication and estimation have their own parameters.

For a numerical illustration, assume \(k_{\rm pre}=7500\), \(\lambda_{\rm EC}=1300\), \(t=40\), and \(\epsilon_{\rm PA}=2^{-40}\). Then ℓ=6080. If 128 secret bits are consumed for authentication, net expansion is 5952. This computation is an exact consequence of the assumed budget. It is not a derivation of 7500 entropy bits from a QBER measurement.

4.3.3 Make a failure budget without changing theorem conventions

List every event or distance bound that enters the proof. A union bound can add failure probabilities for authentication, parameter estimation, and correctness. A triangle inequality can add distances from smoothing and extraction. However, converting a parameter-estimation event probability into a smoothing parameter may introduce a square root or another theorem-specific factor. One cannot take arbitrary formulas from different papers, add their ε symbols, and assume they mean the same thing.

A reviewable ledger should therefore name the theorem supplying the pre-transcript entropy, the systems it conditions on, the smoothing convention, the acceptance conditioning, and each disclosed message. Our executable calculator deliberately takes a certified entropy bound as an input rather than fabricating one from its simulated sample. Its job is to make the arithmetic reproducible and reject impossible lengths; providing that input for a real experiment is the harder security task.

Laboratory task. In the supplied Python module, call key_budget(7500, 1300, 40, 40, 128). The fourth argument is the binary security exponent s, meaning \(\epsilon_{\rm PA}=2^{-s}\). Repeat with a larger leakage budget and explain why every additional disclosed bit removes one output bit under this bound.