ECE 6605 - Information Theory

Prof. Matthieu Bloch

Tuesday, November 21, 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
- Soft covering channel resolvability
- (skipped converse proof)
Today
- Secrecy

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?

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})$

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} = I (X; Y) - I (X; Z) = I (X; Y | Z)$

Challenges
- How do we operationalize secrecy?
- Can we leverage the coding mechanisms studied earlier?

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?