密码学基础：前置知识

新学期选修密码学，第一节课记了这些笔记，于是退课。

离散随机变量

对于给定的有限集合 $Ω = {a_{1}, a_{2}, \dots, a_{n}}$ ，如果变量 $X$ 满足 $\forall a \in Ω, Pr [X = a] = p (a)$ ，其中 $p (x)$ 是映射 $p (x) : Ω \to [0, 1]$ ，且满足 $\sum_{a \in Ω} p (a) = 1$ ，那么称 $X$ 是 $Ω$ 上的一个服从概率分布（distribution） $p$ 的离散随机变量（random variable）。

对概率分布 $p$ ，可以定义其熵（entropy）： $H (p) = \sum_{a \in Ω} p (a) lo g \frac{1}{p ( a )}$ ，这也被称为随机变量 $X$ 的熵 $H (X)$ 。

根据函数 $f (x) = x lo g \frac{1}{x}$ 的凸性，可知当概率分布中各项的概率相等时，即 $p (a) = \frac{1}{∣Ω∣}$ ，熵达到最大值 $H (p) = lo g ∣Ω∣$ 。这样的分布称为均匀分布（uniform distribution）。

对于多个离散随机变量，可以定义联合分布（joint distribution）。如果 $p (x, y) : Ω_{1} \times Ω_{2} \to [0, 1]$ 满足 $\forall a \in Ω_{1}, b \in Ω_{2}, Pr [X = a, Y = b] = p (a, b)$ ，那么称 $X, Y$ 服从联合分布 $p$ ，记作 $(X, Y) \sim p$ 。

同样地，可以定义多个随机变量的联合熵（joint entropy）：若 $(X, Y) \sim p$ ，定义 $H (X, Y) = \sum_{a \in Ω_{1} b \in Ω_{2}} p (a, b) lo g \frac{1}{p ( a , b )}$ 。

给定联合分布后，可以重新计算每个变量单独的分布，称为这个变量的边缘分布（marginal distribution）： $p_{1} (a) = \sum_{b \in Ω_{2}} p (a, b)$ ， $p_{2} (b) = \sum_{a \in Ω_{1}} p (a, b)$ 。

如果联合分布可以表示为边缘分布的乘积，称这两个随机变量独立（independent）。

当两个变量 $X, Y$ 独立时，计算得

H (X, Y) = a \in Ω_{1} b \in Ω_{2} \sum p (a, b) lo g \frac{1}{p ( a , b )} = a \in Ω_{1} b \in Ω_{2} \sum p (a) p (b) (lo g \frac{1}{p ( a )} + lo g \frac{1}{p ( b )}) = b \in Ω_{2} \sum p (b) a \in Ω_{1} \sum p (a) lo g \frac{1}{p ( a )} + a \in Ω_{1} \sum p (a) b \in Ω_{2} \sum p (b) lo g \frac{1}{p ( b )} = H (X) + H (Y)

条件熵

通过条件概率，可以定义一个随机变量 $X$ 关于随机事件 $e$ 的条件熵（conditional entropy）： $H (X ∣ e) = \sum_{a \in Ω} Pr [X = a ∣ e] lo g \frac{1}{Pr [ X = a ∣ e ]}$ 。

随机变量 $X$ 相对于随机变量 $Y$ 的条件熵等于 $X$ 关于 $Y$ 的某一取值的条件熵在 $Y$ 的边缘分布下的期望： $H (X ∣ Y) = \sum_{b \in Ω_{2}} Pr [Y = b] H (X ∣ Y = b)$ 。

对上式变形，可以得出条件熵另外的两种表示：

H (X ∣ Y) = b \in Ω_{2} \sum Pr [Y = b] H (X ∣ Y = b) = b \in Ω_{2} \sum Pr [Y = b] a \in Ω_{1} \sum Pr [X = a ∣ Y = b] lo g \frac{1}{Pr [ X = a ∣ Y = b ]} = a \in Ω_{1} b \in Ω_{2} \sum Pr [X = a, Y = b] lo g \frac{Pr [ Y = b ]}{Pr [ X = a , Y = b ]}

H (X ∣ Y) = a \in Ω_{1} b \in Ω_{2} \sum Pr [X = a, Y = b] lo g \frac{Pr [ Y = b ]}{Pr [ X = a , Y = b ]} = a \in Ω_{1} b \in Ω_{2} \sum Pr [X = a, Y = b] lo g \frac{1}{Pr [ X = a , Y = b ]} - b \in Ω_{2} \sum (a \in Ω_{1} \sum Pr [X = a, Y = b]) lo g \frac{1}{Pr [ Y = b ]} = H (X, Y) - b \in Ω_{2} \sum Pr [Y = b] lo g \frac{1}{Pr [ Y = b ]} = H (X, Y) - H (Y)

互信息

**互信息（mutual information）**用于衡量两个随机变量的相关性。其定义为以一个随机变量为条件后，熵的减少值。

I (X; Y) = H (X) - H (X ∣ Y)

代入 $H (X ∣ Y) = H (X, Y) - H (X)$ ，得到

I (X; Y) = H (X) + H (Y) - H (X, Y)

从这里可以看出互信息是对称的。因此有

I (X; Y) = H (X) - H (X ∣ Y) = H (Y) - H (Y ∣ X) = H (X) + H (Y) - H (X, Y)

进一步变形，可以得到

I (X; Y) = a \in Ω_{1} \sum p_{1} (a) lo g \frac{1}{p _{1} ( a )} + b \in Ω_{2} \sum p_{2} (b) lo g \frac{1}{p _{2} ( b )} - a \in Ω_{1} b \in Ω_{2} \sum p (a, b) lo g \frac{1}{p ( a , b )} = a \in Ω_{1} \sum (b \in Ω_{2} \sum p (a, b)) lo g \frac{1}{p _{1} ( a )} + b \in Ω_{2} \sum (a \in Ω_{1} \sum p (a, b)) lo g \frac{1}{p _{2} ( b )} - a \in Ω_{1} b \in Ω_{2} \sum p (a, b) lo g \frac{1}{p ( a , b )} = a \in Ω_{1} b \in Ω_{2} \sum p (a, b) lo g \frac{p ( a , b )}{p ( a ) p ( b )}

于是可以证明互信息的非负性：

I (X; Y) = a \in Ω_{1} b \in Ω_{2} \sum p (a, b) lo g \frac{p ( a , b )}{p ( a ) p ( b )} = - a \in Ω_{1} b \in Ω_{2} \sum p (a, b) lo g \frac{p ( a ) p ( b )}{p ( a , b )} \geq - lo g a \in Ω_{1} b \in Ω_{2} \sum p (a, b) \frac{p ( a ) p ( b )}{p ( a , b )} = 0

由此可知 $H (X ∣ Y) \leq H (X)$ 。

当随机变量 $X$ 与 $Y$ 独立时，有 $H (X, Y) = H (X) + H (Y)$ ，可知 $H (X ∣ Y) = H (X), H (Y ∣ X) = H (Y), I (X; Y) = 0$ 。

反过来，当互信息 $I (X; Y) = 0$ 时，从上面不等式的取等条件可以看出， $\frac{p ( a ) p ( b )}{p ( a , b )}$ 不依赖于 $a, b$ 的选取，进而可知 $X$ 与 $Y$ 独立。

当随机变量 $Y$ 完全依赖于 $X$ 时，也即 $Pr [X = a, Y = b] = {1, 0, b = f (a) otherwise$ ，有

H (X, Y) = a \in Ω b \in f (Ω) \sum p (a, b) lo g \frac{1}{p ( a , b )} = a \in Ω \sum p (a, f (a)) lo g \frac{1}{p ( a , f ( a ))} = a \in Ω \sum p (a) lo g \frac{1}{p ( a )} = H (X)

因此， $I (X; Y) = H (Y)$ 。

多元互信息

对于多于两个的随机变量 $X_{1}, X_{2}, \dots, X_{n}$ ，记其概率分布为 $p : Ω_{1} \times Ω_{2} \times \dots \times Ω_{n} \to [0, 1]$ ，以及每个变量的边缘分布 $X_{i} \sim p_{i}$ ，于是可以定义多元联合熵

H (X_{1}, X_{2}, \dots, X_{n}) = x_{1} \in Ω_{1} \sum x_{2} \in Ω_{2} \sum \dots x_{n} \in Ω_{n} \sum p (x_{1}, x_{2} \dots, x_{n}) lo g \frac{1}{p ( x _{1} , x _{2} \dots , x _{n} )}

以及关于随机事件 $e$ 的多元条件熵

H (X_{1}, X_{2}, \dots, X_{n} ∣ e) = x_{1} \in Ω_{1} \sum x_{2} \in Ω_{2} \sum \dots x_{n} \in Ω_{n} \sum p (x_{1}, x_{2} \dots, x_{n} ∣ e) lo g \frac{1}{p ( x _{1} , x _{2} \dots , x _{n} ∣ e )}

考虑三个随机变量 $X, Y, Z$ 的条件熵，定义

H (X, Y ∣ Z) = z \sum Pr [Z = z] \cdot H (X, Y ∣ Z = z) = x \sum y \sum z \sum Pr [Z = z] \cdot Pr [X = x, Y = y ∣ Z = z] lo g \frac{1}{Pr [ X = x , Y = y ∣ Z = z ]} = x \sum y \sum z \sum Pr [X = x, Y = y, Z = z] (lo g \frac{1}{Pr [ X = x , Y = y , Z = z ]} - lo g \frac{1}{Pr [ Z = z ]}) = H (X, Y, Z) - z \sum (x \sum y \sum Pr [X = x, Y = y, Z = z]) lo g \frac{1}{Pr [ Z = z ]} = H (X, Y, Z) - z \sum Pr [Z = z] lo g \frac{1}{Pr [ Z = z ]} = H (X, Y, Z) - H (Z)

接下来定义关于随机事件 $e$ 的条件互信息

I (X; Y ∣ e) = H (X ∣ e) + H (Y ∣ e) - H (X, Y ∣ e)

以及关于随机变量的条件互信息

I (X; Y ∣ Z) = z \sum Pr [Z = z] \cdot I (X; Y ∣ Z = z) = z \sum Pr [Z = z] \cdot (H (X ∣ Z = z) + H (Y ∣ Z = z) - H (X, Y ∣ Z = z)) = H (X ∣ Z) + H (Y ∣ Z) - H (X, Y ∣ Z)

继续定义多元互信息

I (X_{1}; X_{2}; \dots; X_{n}) = i = 1 \sum n H (X_{i}) - 1 \leq i < j \leq n \sum H (X_{i}, H_{j}) + \dots + (- 1)^{n - 1} H (X_{1}, X_{2}, \dots, X_{n})

特别地，有三元互信息

I (X; Y; Z) = H (X) + H (Y) + H (Z) - H (X, Y) - H (X, Z) - H (Y, Z) + H (X, Y, Z) = H (X) + H (Y) - H (X, Y) + 2 H (Z) - H (X, Z) - H (Y, Z) + H (X, Y ∣ Z) = I (X; Y) - H (X ∣ Z) - H (Y ∣ Z) + H (X, Y ∣ Z) = I (X; Y) - I (X; Y ∣ Z)

仿照二元互信息，可知

I (X; Y ∣ e) = x \sum y \sum Pr [X = x, Y = y ∣ e] lo g \frac{Pr [ X = x , Y = y ∣ e ]}{Pr [ X = x ∣ e ] \cdot Pr [ Y = y ∣ e ]}

于是

I (X; Y ∣ Z) = x \sum y \sum z \sum Pr [Z = z] \cdot Pr [X = x, Y = y ∣ Z = z] \cdot lo g \frac{Pr [ X = x , Y = y ∣ Z = z ]}{Pr [ X = x ∣ Z = z ] \cdot Pr [ Y = y ∣ Z = z ]} = x \sum y \sum z \sum Pr [X = x, Y = y, Z = z] \cdot (lo g \frac{Pr [ X = x , Y = y , Z = z ]}{Pr [ X = x , Z = z ] \cdot Pr [ Y = y , Z = z ]} - lo g \frac{1}{Pr [ Z = z ]}) = - H (Z) - x \sum y \sum Pr [X = x, Y = y] z \sum \frac{Pr [ X = x , Y = y , Z = z ]}{Pr [ X = x , Y = y ]} \cdot lo g \frac{Pr [ X = x , Z = z ] \cdot Pr [ Y = y , Z = z ]}{Pr [ X = x , Y = y , Z = z ]} \leq - H (Z) - x \sum y \sum Pr [X = x, Y = y] \cdot lo g z \sum \frac{Pr [ X = x , Y = y , Z = z ]}{Pr [ X = x , Y = y ]} \cdot \frac{Pr [ X = x , Z = z ] \cdot Pr [ Y = y , Z = z ]}{Pr [ X = x , Y = y , Z = z ]} = - H (Z) - x \sum y \sum Pr [X = x, Y = y] \cdot (lo g \frac{1}{Pr [ X = x , Y = y ]} + lo g z \sum Pr [X = x, Z = z] \cdot Pr [Y = y, Z = z])

马尔可夫不等式

对实数域上的离散随机变量 $X$ ，记期望 $E (X) = \sum_{a \in Ω} a p (a)$ ，当 $X$ 恒非负时，有马尔可夫不等式（Markov inequality）：

Pr [X \geq a] = \frac{\sum _{b \in Ω b \geq a} a p ( b )}{a} \leq \frac{\sum _{b \in Ω b \geq a} b p ( b )}{a} \leq \frac{\sum _{b \in Ω} b p ( b )}{a} = \frac{E ( X )}{a}

如果 $X$ 是另一个随机变量 $Y$ 到其均值的距离的平方，则有切比雪夫不等式（Chebyshev inequality）：

Pr [∣ Y - E Y ∣ \geq c] = Pr [(Y - E Y)^{2} \geq c^{2}] \leq \frac{E (( Y - E Y ) ^{2} )}{c ^{2}} = \frac{D ( Y )}{c ^{2}}

切比雪夫不等式描述了方差与随机变量偏离均值的程度之间的关系。

对于一般的多个随机变量 $X_{1}, X_{2}, \dots, X_{n}$ ，记 $X = \sum_{i = 1}^{n} X_{i}$ ，代入切比雪夫不等式有

Pr [\frac{1}{n} i = 1 \sum n X_{i} - \frac{1}{n} i = 1 \sum n E X_{i} \geq c] = Pr [i = 1 \sum n X_{i} - i = 1 \sum n E X_{i} \geq n c] \leq \frac{D ( X )}{n ^{2} c ^{2}} = \frac{1}{n ^{2} c ^{2}} i = 1 \sum n D X_{i}

若 $X_{1}, X_{2}, \dots, X_{n}$ 是同分布的，记均值 $μ = E (X_{i})$ ，方差 $σ^{2} = D (X_{i})$ ，则

Pr [\frac{1}{n} i = 1 \sum n X_{i} - μ \geq c] \leq \frac{σ ^{2}}{n c ^{2}}

令 $n \to \infty$ ，则

n \to \infty lim Pr [\frac{1}{n} i = 1 \sum n X_{i} - μ \geq c] = 0

这就是弱大数定律（weak law of large numbers）。

切诺夫界

如果对 $X_{1}, X_{2}, \dots, X_{n}$ 有更多假设，可以给出比弱大数定律更强的估计。

若 $X_{1}, X_{2}, \dots, X_{n}$ 为独立泊松实验，即 $X_{i} \in {0, 1}$ ， $Pr [X_{i} = 1] = p_{i}$ ，记 $X = \sum_{i = 1}^{n} X_{i}$ ， $μ = E X = \sum_{i = 1}^{n} p_{i}$ ，那么

Pr [i = 1 \sum n X_{i} \geq (1 + δ) μ] = Pr [e^{tX} \geq e^{(1 + δ) t μ}] \leq \frac{E ( e ^{tX} )}{e ^{(1 + δ) t μ}} = \frac{1}{e ^{(1 + δ) t μ}} i = 1 \prod n E (e^{t X_{i}}) = \frac{1}{e ^{(1 + δ) t μ}} i = 1 \prod n (p_{i} e^{t} + 1 - p_{i}) \leq \frac{1}{e ^{(1 + δ) t μ}} i = 1 \prod n exp (p_{i} (e^{t} - 1)) = \frac{1}{e ^{(1 + δ) t μ}} exp (i = 1 \sum n p_{i} (e^{t} - 1)) = \frac{exp ( μ ( e ^{t} - 1 ))}{exp (( 1 + δ ) t μ )} = exp (μ (1 + δ) (e^{t - l n (1 + δ)} - \frac{1}{1 + δ} - t))

令 $t = ln (1 + δ)$ ，则

Pr [i = 1 \sum n X_{i} \geq (1 + δ) μ] \leq (\frac{e ^{δ}}{( 1 + δ ) ^{1 + δ}})^{μ}

同理，有

Pr [i = 1 \sum n X_{i} \leq (1 - δ) μ] \leq (\frac{e ^{- δ}}{( 1 - δ ) ^{1 - δ}})^{μ}

此二式称为切诺夫界（Chernoff bound）。

萱草的博客

探索

密码学基础：前置知识

离散随机变量

条件熵

互信息

多元互信息

马尔可夫不等式

切诺夫界

关系图谱

目录