ECE 6605 - Information Theory

Prof. Matthieu Bloch

Tuesday, November 28, 2023

Announcements

Project
- Send me an email to confirm your choices (the sooner the better)
- I'll hold project office hours to help you
Exam options
- Oral: list of problems published, scheduling options coming
- Written: Thursday, December 14 11:20 am - 2:10 pm
Last time
- Wiretap channel
Today
- Secret key generation
- Covert communications

Review: Shannon Cipher System

Historical paper: Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, (1948)

Secrecy metric: $I (M; C) = 0$ - message and ciphertext should be statisticall independent
- If true, the best attack is to guess the message
How is this possible? Secret key is required
- One-time pad, see assignments
- How much key do we need? $H (K) \geq H (M)$

Review: Wiretap channel

Historical paper: A. D. Wyner, The Wire-Tap Channel, Bell System Technical Journal, (1975)
- Physically degraded channel (can be relaxed, more complicated)
Secrecy metric: $lim_{n \to \infty} I (M; Z^{n}) = 0$ (asymptotic independence)

A $(n, M_{n})$ code $C$ for a wiretap channel consists of an encoding function $f_{n} : {1, \dots, M_{n}} \to X^{n}$ and a decoding function $g_{n} : Y^{n} \to {1, \dots, M_{n}}$

The performance of an $(n, M_{n})$ code is measured in terms of
1. The rate of the code $R ≜ \frac{\log_{2} M_{n}}{n}$ (bits/source symbol)
2. Reliability and secrecy $P_{e}^{(n)} ≜ P_{} (\hat{M} \neq M)$ and $S^{(n)} ≜ I (M; Z^{n})$

Review: Wiretap channel

Define $C_{s} ≜ sup {R : \exists {(f_{n}, g_{n})}_{n \geq 1} with lim_{n \to \infty} \frac{\log M_{n}}{n} \geq R and lim_{n \to \infty} P_{e}^{(n)} = lim_{n \to \infty} S^{(n)} = 0}$

For a physically degraded discrete memoryless channel characterized by $P_{Y | X}$ and $P_{Z | X}$ , $C_{s} = max_{P_{X}} (I (X; Y) - I (X; Z)) = max_{P_{X}} I (X; Y | Z)$

Challenges
- How do we operationalize secrecy?
- Can we leverage the coding mechanisms studied earlier? (channel coding + soft covering)

Secret key generation

Public authenticated channel of unlimited capacity available for reocnciliation

A $(n, K_{n})$ code $C$ for secret-key generation consists of an encoding function $f_{n} : X^{n} \to {1, \dots, K_{n}} \times F$ and a decoding function $g_{n} : Y^{n} \times F \to {1, \dots, K_{n}}$

The performance of an $(n, M_{n})$ code is measured in terms of
1. The rate of the code $R ≜ \frac{\log_{2} K_{n}}{n}$ (bits/source symbol)
2. Reliability and secrecy $P_{e}^{(n)} ≜ P_{} (\hat{K} \neq K)$ and $S^{(n)} ≜ I (M; (K, Z^{n}))$

Secret key generation

Define $C_{sk} ≜ sup {R : \exists {(f_{n}, g_{n})}_{n \geq 1} with lim_{n \to \infty} \frac{\log K_{n}}{n} \geq R and lim_{n \to \infty} P_{e}^{(n)} = lim_{n \to \infty} S^{(n)} = 0}$

For a physically degraded discrete memoryless channel characterized by $P_{Y | X}$ and $P_{Z | X}$ , $C_{sk} = H (X | Z) - H (X | Y) = I (X; Y | Z)$

Not different from secrecy capacity, but this is an artefact of physically degraded channels
- In general, secret key generation rates are higher than wiretap coding rates.
Challenges
- How do we operationalize secrecy?
- Can we leverage the coding mechanisms studied earlier?

Covert communications

Pioneering work paper: B.A Bash et al., Limits of Reliable Communication with Low Probability of Detection on AWGN Channels, IEEE Journal on Selected Areas in Communications, (2013)

Covertness metric: $lim_{n \to \infty} D ({\hat{Q}}^{n} ‖ Q_{0}^{\otimes n}) = 0$ (asymptotic independence)

A $(n, M_{n})$ code $C$ for a wiretap channel consists of an encoding function $f_{n} : {1, \dots, M_{n}} \to X^{n}$ and a decoding function $g_{n} : Y^{n} \to {1, \dots, M_{n}}$

The performance of an $(n, M_{n})$ code is measured in terms of
1. The rate of the code $R ≜ \frac{\log_{2} M_{n}}{n}$ (bits/source symbol)
2. Reliability and covertness $P_{e}^{(n)} ≜ P_{} (\hat{M} \neq M)$ and $D^{(n)} ≜ D ({\hat{Q}}^{n} ‖ Q_{0}^{\otimes n})$