Perfect Secrecy and Computational Security

04-23

這個專欄的主要目的是為了介紹一下格密碼——一種公鑰加密演算法。為了能夠使這個專欄中包含的知識比較系統化，我會首先介紹一些密碼學中的相關概念。在這第一篇文章中，我將介紹現代密碼學中的兩個基本概念：perfect secrecy和computational security。

首先，我們需要解釋一下什麼叫加密演算法：一個加密演算法 $Pi$ 是由三個演算法 $(Gen, Enc, Dec)$ 組成的。其中， $Gen$ 是用來來生成密鑰 $k$ 的演算法， $Enc$ 是用來通過密鑰 $k$ 來加密明文 $m$ 以得到密文 $c$ 的演算法， $Dec$ 用來通過密鑰 $k$ 來解密密文的演算法，即

$k leftarrow Gen \ c leftarrow Enc(k, m) \ m := Dec(k, c)$

顯然，為了保證正確性，我們需要有 $m == Dec(k, Enc(k, m))$ 。有一點需要指出的是，無論是密鑰 $k$ 還是明文 $m$ 都是有其全集的，分別為 $mathcal{K}$ 和 $mathcal{M}$ ，那麼密文 $c$ 也自然地有了全集 $mathcal{C}$ ，這一點會在之後perfect secrecy的定義中用到。

基於以上對於加密演算法的定義，我們可以給出perfect secrecy的定義：

Definition 1(Perfect Secrecy)：
The condition of perfect scecrecy for an encryption scheme $Pi = (Gen, Enc, Dec)$ is that

$Pr(M = m | C = c) = Pr(M = m)$ for all $m in mathcal{M}$ and $c in mathcal{C}$ .

這個定義的含義就是密文與明文互相獨立，即獲得了某個明文對應的密文後，對明文依舊一無所知。這個定義是由資訊理論的鼻祖級人物Shannon給出的，不得不說大師們對事物本質的直覺和認識是非常準確且精鍊的，基本上可以說這個定義開啟了近代密碼學的大門。

在給出這個定義的同時，shannon教授還給出了如下定理

Theorem 1:
If an encryption scheme with message space $mathcal{M}$ and key space $mathcal{K}$ satisfies perfect secrecy, then $|mathcal{K}| geqslant |mathcal{M}|$
Proof：

$Pr(M = m|C = c) cdot Pr(C = c) = Pr(C=c|M=m) cdot Pr(M = m) \ ightarrow Pr(C = c) = Pr(C = c|M = m) \ ightarrow Pr(Enc(K, M) = c) = Pr(Enc(K, M) = c | M = m) \ ightarrow Pr(Enc(K, M) = c) = Pr(Enc(K, m) = c)$
由於 $mathcal{C}$ 是由 $mathcal{M}$ 和 $mathcal{K}$ 導出的，所以上述等式左邊 $geqslant 0$ ,即 $forall m in mathcal{M}, c in mathcal{C},Pr(Enc(K, m) = c) geqslant 0$
若想將同一 $m$ 加密為不同 $c$ ，則必須使用不同密鑰 $k$ ，所以 $|mathcal{K}| geqslant |mathcal{C}|$
另一方面，對於一個固定的密鑰 $k$ ，它會將不同的明文 $m$ 加密到不同哦對密文 $c$ ，所以 $|mathcal{C}| geqslant |mathcal{M}|$
綜上所述 $|mathcal{K}| geqslant |mathcal{M}|$

由這個定理可以看出，對於一個滿足了perfect secrecy的加密演算法，保存密鑰所需的成本甚至要大於保存信息本身所需的成本，雖然設計滿足perfect secrecy的加密演算法難度不是很大(shannon教授就提出了一個滿足perfect secrecy的加密演算法one-time-pad)，但這種加密演算法在實際應用中幾乎沒有什麼意義。

不過我們發現，在應用中我們不需要perfect secrecy這麼強的安全性，我們可以稍微降低一點我們的要求來使我們的加密演算法可以應用到實踐上，因此我們提出了computational security的概念。