[笔记]绝对安全的加密

1. Perfectly-Secret Encryption

另一种“极端”，绝对完美的密码

In this chapter, we look at the other extreme and study encryption schemes that are provably secure even against an adversary who has unbounded computational power.Such schemes are called perfectly secret.

定义：
$\mathcal{K}$： 密钥空间
$\mathcal{M}$： 明文空间
$\mathcal{C}$： 密文空间
$\mathsf{Gen}\ \mathsf{Enc}\ \mathsf{Dec}$ ：三个算法
$\Pr[K=k]$： 生成的密钥为 $k$ 的概率
$\Pr[M=m]$： 需要发送的明文为 $m$ 的概率
$\Pr[C=c]$： 密文为 $c$ 的概率
假设：$\mathcal{K}$ 和 $\mathcal{M}$ 的分布是相互独立的

那么，什么叫做perfectly secret呢？想象这样的场景，如果有一个窃密者知道了所发送的明文的分布情况，但是他只能窃听到明文加密后的密文，那么他是否有可能根据密文的分布来推断明文呢？
所谓的perfectly secret就是要保证窃密者对于所获取的密文中分析不出明文的任何信息，即使他有无穷大的算力。

This means that a ciphertext reveals nothing about the underlying plaintext, and thus an adversary who intercepts a ciphertext learns absolutely nothing about the plaintext that was encrypted.

用数学公式来表达的话，就是：
对于任何一个明文$m\in\mathcal{M}$，任何一个密文$c\in\mathcal{C}$，在 $\Pr[C=c]>0$ 时，有：

$\Pr[M=m|C=c]=\Pr[M=m]$

这等价于：

$\Pr[C=c|M=m]=\Pr[C=c]$

---

2. Perfect indistinguishability

由perfect secret引申而来

We refer to this formulation as perfect indistinguishability because it implies that it is impossible to distinguish an encryption of $m_0$ from an encryption of $m_1$.

用数学公式表示如下：

$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$

Adversarial indistinguishability

换另外一种角度，假如我们做这样一个实验，在定义了 $\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}$ 算法和给定了 $\mathcal{K},\mathcal{M},\mathcal{C}$ 的前提下，窃听者知道我们需要发送的密文不是 $m_0$ 就是 $m_1$，$m_0,m_1\in\mathcal{M}$，对于我们发送方，先随机生成密钥，然后随机选择一个 $b\in\{0,1\}$,生成密文 $c\leftarrow \mathsf{Enc}_k(m_b)$.

窃听者看到这个密文，尝试解密得到 $b'$，如果 $b'=b$ 的话，说明 $\mathcal{A}$ 攻击成功，记这次实验的输出为1,否则设置为0。
方便起见，记 $\mathsf{Priv}_{\mathcal{A},\Pi}^{eav}$ 为实验结果，则有在 Perfectly indistinguishable 情况下，

$\Pr[\mathsf{Priv}_{\mathcal{A},\Pi}^{eav}=1]=1/2$

---

3. One-Time pad

1917年，Vernam 提出了一种叫做一次一密One-Time Pad的加密法，大约25年之后，Shannon证明了One-Time Pad是perfectly-secret。
对于一次一密，其加密机制如下：

Fix an ineger $\mathcal{\ell}>0$. The message space $\mathcal{M}$, key space $\mathcal{K}$, and cipertext space $\mathcal{C}$ are all euqal to $\{0,1\}^\mathcal{\ell}$.

• $\mathsf{Gen}$: the key-generation algorithm chooses a key from $\mathcal{K}=\{0,1\}^\mathcal{\ell}$ according to the uniform distribution.
• $\mathsf{Enc}$: given a key $k\in \{0,1\}^\mathcal{\ell}$ and a message $m\in \{0,1\}^\mathcal{\ell}$, the encryption algorithm outputs the ciphertext $c:= k\oplus m$
• $\mathsf{Dec}$: given a key $k\in \{0,1\}^\mathcal{\ell}$ and a ciphertext $c\in \{0,1\}^\mathcal{\ell}$, the decryption alogrithm outpus the message $m:= k\oplus c$

构造非常简单，证明过程暂且不表。
单就这个加密机制而言是有很大问题的。首先是密钥只能用一次，如果使用同一个密钥来加密两个不同的明文，攻击者通过两个密文是可以获取两个明文之间的信息的。如

$c\oplus c' = (m\oplus k)\oplus (m' \oplus k)=m \oplus m'$

其次，密钥的长度是至少大于等于明文的长度的，也就是说密钥都能秘密进行传输了，还要加密什么消息…
所以在实践中是不可行的。因此，我们需要建立一种密钥长度小于明文长度的机制，那么这就要建立一种全新的关于安全的定义了，即在现实中可行的Computational Security.