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

Image
Shannon Cipher system
  • Historical paper: Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, (1948)
  • Secrecy metric: \(\mathbb{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

Image
Wyner's 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} \mathbb{I}(M;Z^n)=0\) (asymptotic independence)

A \((n,M_n)\) code \(\calC\) for a wiretap channel consists of an encoding function \(f_n:\{1,\cdots,M_n\}\to\calX^n\) and a decoding function \(g_n:\calY^n\to\{1,\cdots,M_n\}\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)
    2. Reliability and secrecy \(P_e^{(n)}\eqdef \P{\widehat{M}\neq M}\) and \(S^{(n)}\eqdef \mathbb{I}(M;Z^n)\)

Wiretap channel

  • Define \[ C_{\textsf{s}}\eqdef \sup\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\geq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=\lim_{n\to\infty}S^{(n)}=0\right\} \]

For a physically degraded discrete memoryless channel characterized by \(P_{Y|X}\) and \(P_{Z|X}\), \[C_{\textsf{s}} = \mathbb{I}(X;Y)-\mathbb{I}(X;Z) = \mathbb{I}(X;Y|Z)\]

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

Secret key generation

Image
Secret key generation from correlated observations
  • Public authenticated channel of unlimited capacity available for reocnciliation

A \((n,K_n)\) code \(\calC\) for secret-key generation consists of an encoding function \(f_n:\calX^n\to \{1,\cdots,K_n\}\times\calF\) and a decoding function \(g_n:\calY^n\times\calF\to\{1,\cdots,K_n\}\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 K_n}{n}\) (bits/source symbol)
    2. Reliability and secrecy \(P_e^{(n)}\eqdef \P{\widehat{K}\neq K}\) and \(S^{(n)}\eqdef \mathbb{I}(M;(K,Z^n))\)

Secret key generation

  • Define \[ C_{\textsf{sk}}\eqdef \sup\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log K_n}{n}\geq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=\lim_{n\to\infty}S^{(n)}=0\right\} \]

For a physically degraded discrete memoryless channel characterized by \(P_{Y|X}\) and \(P_{Z|X}\), \[C_{\textsf{sk}} = \mathbb{H}(X|Z)-\mathbb{H}(X|Y) = \mathbb{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?