Ferkans — Interactive Telecom Tutor

From Secrecy Capacity to Secret Keys

In the wiretap channel, secrecy is achieved "for free" — the noise protects the message without any pre-shared secret. But what if Alice and Bob want to generate a shared secret key that they can later use for encryption? It turns out that correlated observations — such as those provided by a common communication channel — can be distilled into a secret key, even when Eve has partial information.

This is the secret key agreement problem, and its solution connects information theory to cryptography in a fundamental way.

Definition:
Secret Key Generation Model

Alice observes $X^n$ , Bob observes $Y^n$ , and Eve observes $Z^n$ , where $(X_i, Y_i, Z_i)$ are drawn i.i.d. from a joint distribution $P_{XYZ}$ . Alice and Bob can communicate over a public, noiseless, authenticated channel that Eve can observe but not modify.

A secret key agreement protocol consists of:

Alice's key function: $K_A = f_A(X^n, F)$ where $F$ is the public communication
Bob's key function: $K_B = f_B(Y^n, F)$
Public communication: $F = \phi(X^n)$ (or interactive: multiple rounds between Alice and Bob)

The protocol must satisfy:

Agreement: $\Pr[K_A \neq K_B] \to 0$
Uniformity: $\frac{1}{n}H(K_A) \to R_K$ (the key rate)
Secrecy: $I(K_A; Z^n, F) \to 0$ (Eve learns nothing from her observations and the public discussion)

The secret key capacity $C_K$ is the supremum of achievable key rates $R_K$ .

Secret key capacity

The maximum rate at which Alice and Bob can generate a shared secret key from their correlated observations, using public discussion that Eve can overhear. Denoted $C_K$ .

Theorem: Secret Key Capacity (Maurer–Ahlswede–Csiszár)

When Alice observes $X$ , Bob observes $Y$ , and Eve observes $Z$ , drawn from $P_{XYZ}$ , the secret key capacity with one-way public communication from Alice to Bob is: $C_K^{\to} = I(X; Y) - I(X; Z)$ when $X \to Y \to Z$ forms a $X \multimap Y \multimap Z$ chain (degraded eavesdropper).

More generally, with unlimited interactive public discussion: $C_K = I(X; Y \| Z) \triangleq I(X; Y | Z) + \text{(correction terms)}$ where $I(X; Y \| Z)$ is the secret key rate (conditional mutual information in some models, but the general expression involves auxiliary random variables).

For the special case where Eve has no observations ( $Z = \text{const}$ ): $C_K = I(X; Y).$

The secret key capacity with one-way communication matches the wiretap channel secrecy capacity — this is not a coincidence. Secret key generation and wiretap coding are dual problems: in the wiretap channel, Alice uses her "channel advantage" to hide the message; in secret key generation, Alice and Bob use their "correlation advantage" to extract a key that Eve cannot reconstruct.

The public discussion is essential: it allows Alice and Bob to reconcile their observations (which differ due to noise) without giving Eve useful information. The discussion is public — Eve hears everything — but the key remains secret because Eve's observations $Z^n$ are insufficiently correlated with $(X^n, Y^n)$ .

Proof

Achievability (one-way, degraded)

Alice uses Slepian–Wolf compression to describe $X^n$ to Bob at rate $H(X|Y) + \epsilon$ , transmitted over the public channel. Bob, using his observation $Y^n$ as side information, decodes $X^n$ .

Now both Alice and Bob know $X^n$ . They apply a universal hash function $g: \mathcal{X}^n \to \{1, \ldots, 2^{nR_K}\}$ to extract the key: $K = g(X^n)$ .

The public communication $F$ (the Slepian–Wolf compressed message) leaks at most $n(H(X|Y) + \epsilon)$ bits to Eve. The total correlation between Eve's information $(Z^n, F)$ and $X^n$ is at most $n(I(X;Z) + H(X|Y) + \epsilon) = n(H(X) - I(X;Y) + I(X;Z) + \epsilon)$ .

The extractable key rate is $R_K = H(X) - (H(X) - I(X;Y) + I(X;Z) + \epsilon) = I(X;Y) - I(X;Z) - \epsilon$ .

Converse sketch

The key rate is bounded by the mutual information between Alice's and Bob's observations minus the information available to Eve. The converse uses the secrecy constraint and the public nature of $F$ to show that $R_K \leq I(X;Y) - I(X;Z)$ .

The key step is: $nR_K \leq I(K; Y^n, F) \leq I(X^n; Y^n, F) = I(X^n; Y^n) + I(X^n; F | Y^n) = nI(X;Y) + I(X^n; F | Y^n)$ .

And: $nR_K = H(K) = H(K | Z^n, F) + I(K; Z^n, F) \leq H(K | Z^n, F) + n\delta_n$ .

Combining these bounds with the degradedness yields $R_K \leq I(X;Y) - I(X;Z)$ . $\blacksquare$

,

Historical Note: The Birth of Information-Theoretic Key Agreement

1993

The problem of generating secret keys from correlated observations was independently formulated by Ueli Maurer (1993) and Rudolf Ahlswede and Imre Csiszár (1993). Maurer's approach was motivated by practical cryptographic applications: he showed that the physical layer of a communication system could be used to generate encryption keys without relying on computational hardness assumptions.

Ahlswede and Csiszár provided the complete information-theoretic characterization, establishing the secret key capacity as a function of the joint distribution of the parties' observations. Their work revealed a deep connection between secret key generation and the wiretap channel: the secret key capacity with one-way communication equals the wiretap secrecy capacity.

This result has had profound practical impact: modern key generation protocols in wireless systems (exploiting channel reciprocity in TDD systems) are direct descendants of Maurer's original proposal.

Example: Secret Key from Wireless Channel Reciprocity

In a TDD wireless system, Alice and Bob observe channel estimates $X = H + N_A$ and $Y = H + N_B$ where $H \sim \mathcal{CN}(0, \sigma_H^2)$ is the common channel (reciprocal in TDD) and $N_A, N_B$ are independent estimation noise with variance $\sigma^2$ . Eve observes $Z = H_E + N_E$ where $H_E$ is Eve's channel (independent of $H$ due to spatial decorrelation) and $N_E$ has variance $\sigma^2$ .

Compute the secret key capacity.

Solution

Key observation

Since $H_E$ is independent of $H$ , Eve's observation $Z$ is independent of $(X, Y)$ given the channel model. Therefore $I(X; Z) = 0$ and $C_K = I(X; Y) - I(X; Z) = I(X; Y).$

Compute $\ntn{mi}(X; Y)$

$(X, Y)$ is jointly Gaussian with $\text{Var}(X) = \text{Var}(Y) = \sigma_H^2 + \sigma^2$ and $\text{Cov}(X, Y) = \sigma_H^2$ .

The correlation coefficient is $\rho = \sigma_H^2 / (\sigma_H^2 + \sigma^2)$ .

$I(X; Y) = -\frac{1}{2}\log(1 - \rho^2) = -\frac{1}{2}\log\left(1 - \frac{\sigma_H^4}{(\sigma_H^2 + \sigma^2)^2}\right).$

At high channel SNR ( $\sigma_H^2 / \sigma^2 \gg 1$ ): $\rho \to 1$ and $C_K \to \frac{1}{2}\log(\sigma_H^2/\sigma^2)$ , which grows logarithmically with the estimation SNR.

Practical interpretation

In a TDD system with good channel estimation (high SNR), Alice and Bob can generate $\frac{1}{2}\log(\sigma_H^2/\sigma^2)$ secret bits per channel observation. With a channel coherence time of $T_c$ seconds and $B$ Hz of bandwidth, the key generation rate is approximately $\frac{B}{T_c B + 1} \cdot C_K$ bits per second.

For typical 5G parameters ( $B = 100$ MHz, $T_c = 1$ ms, $\text{SNR}_{\text{est}} = 20$ dB): the key rate is on the order of $10^5$ bits/second — sufficient for AES-256 key refresh every few milliseconds.

⚠️Engineering Note

Practical Key Generation in TDD Systems

Real-world key generation from channel reciprocity faces several practical challenges:

Imperfect reciprocity: Even in TDD, the RF front-ends at Alice and Bob are not identical, creating a mismatch that must be calibrated.
Eve's partial correlation: In practice, Eve is not perfectly decorrelated from Alice and Bob, especially in line-of-sight channels or with nearby eavesdroppers. The key rate must account for Eve's residual correlation.
Quantization mismatch: Both parties must independently quantize their continuous channel estimates to bits, and these bits may disagree at some positions. An information reconciliation step (using LDPC codes over the public channel) corrects mismatches at the cost of key rate.
Privacy amplification: Universal hashing compresses the reconciled bits to remove any information that may have leaked to Eve during reconciliation.

Reported experimental key rates: 10–100 kbps for indoor Wi-Fi, 1–10 kbps for outdoor cellular, up to 1 Mbps for mmWave systems with wide bandwidth.

Practical Constraints

•
TDD systems only — FDD lacks channel reciprocity
•
Key rate limited by channel coherence bandwidth and time
•
Requires authenticated public channel (prevents man-in-the-middle attacks)

Information reconciliation

The step in a key agreement protocol where Alice and Bob use public communication (e.g., syndrome-based error correction) to ensure they agree on the same bit string, correcting mismatches due to noise in their channel observations.

Related: Secret key capacity

Privacy amplification

The step in a key agreement protocol where Alice and Bob apply a universal hash function to their reconciled bit string to remove any information that Eve may have gained from the public reconciliation communication. The output is a shorter but fully secret key.

Quick Check

In secret key generation, Alice and Bob communicate over a public channel that Eve can overhear. How can they still generate a secret key?

The correlation between their observations exceeds Eve's correlation, and hashing extracts the secret part

The public channel is encrypted

Eve cannot hear the public channel

Correction:

The correlation between their observations exceeds Eve's correlation, and hashing extracts the secret part

Alice and Bob share more mutual information about their observations than Eve has about either. The public communication helps them reconcile their observations (agree on the same bits), and privacy amplification (hashing) removes any information Eve gained from the public discussion. The net key rate is the gap between the Alice–Bob correlation and Eve's information.

Key Takeaway

Secret key generation from common randomness is the dual of wiretap coding: instead of sending a secret message directly, Alice and Bob extract a shared key from their correlated observations. The secret key capacity with one-way communication is $C_K = I(X;Y) - I(X;Z)$ , matching the wiretap secrecy capacity. In wireless systems, channel reciprocity in TDD provides the common randomness, and the key rate scales with the estimation SNR and channel variability.

Secret Key Generation from Channel Reciprocity

Walks through the four steps of key generation from wireless channel reciprocity: channel probing, quantization, information reconciliation, and privacy amplification.

Secret Key Generation from Common Randomness

From Secrecy Capacity to Secret Keys

Definition: Secret Key Generation Model

Secret key capacity

Theorem: Secret Key Capacity (Maurer–Ahlswede–Csiszár)

Achievability (one-way, degraded)

Converse sketch

Historical Note: The Birth of Information-Theoretic Key Agreement

Example: Secret Key from Wireless Channel Reciprocity

Key observation

Compute $\ntn{mi}(X; Y)$

Practical interpretation

Practical Key Generation in TDD Systems

Information reconciliation

Privacy amplification

Quick Check

Key Takeaway

Secret Key Generation from Channel Reciprocity

Definition:
Secret Key Generation Model