Perfect Secrecy and its Relaxation
If an encryption scheme is perfectly secure, the ciphertext reveals NO additional information to the adversary about the underlying plaintext, even if the adversary has unbounded computational power.
Perfect secrecy is the strongest definition of security.
Probability Definition
- $\Pr[M=m|C=c]=\Pr[M=m]$ for all $m, c$
- (perfect indistinguishability) $\Pr[M=m_0|C=c]=\Pr[M=m_1|C=c]$ for all $m_0,m_1,c$
Adversarial Indistinguishability Experiment
Encryption scheme $\Pi=\langle Gen, Enc, Dec \rangle$, $Enc$ takes $k, m$ as input (in currying style $Enc_k$), $Dec$ takes $k, c$ as input (in currying style $Dec_k$).
Threat model: adversary $\mathscr{A}$ with unbounded computational power
- $\mathscr{A}$ selects 2 plaintexts $m_0, m_1$.
- Challenger $\mathscr{C}$ generates a random bit $b\in{0,1}$, and runs $Enc_k(m_b)\to c$. $c$ is called the challenge ciphertext and is given back to $\mathscr{A}$.
- $\mathscr{A}$ finally outputs a bit $b’$, indicating that $c$ corresponds to the plaintext $m_{b’}$.
- $\mathscr{A}$ successes if $b’=b$.
Perfect secrecy of $\Pi$ indicates that NO adversary could success in the above experiment with probability greater than $\frac{1}{2}$. $\Pr[\mathtt{PrivK}^{eav}_{\mathscr{A}, \Pi}(n)=1]=\frac{1}{2}$.
This means that adversary has NO better choice than simply outputting a random guess.
Shannon’s Theorem
Shannon points out that an encryption scheme could be perfectly secure only when $|\mathscr{K}|\geq |\mathscr{M}|$ ($\mathscr{K}$ is key space, $\mathscr{M}$ is message space).
One-time pad is a typical perfectly secure scheme: adversary can never derive $m$ from a given $c$ if he does not know the secret key $k$. In OTP, $|\mathscr{K}|=|\mathscr{M}|=2^n$.
In real life, perfectly secure encryption scheme has little application value: If 2 parties have the ability to safely transmit a key of the same length as the plaintext, then obviously it is better to transmit the plaintext directly.
Relaxation: Computational Secrecy
The relaxed definition of perfect secrecy is more frequently used in reality:
- Polynomial probabilisitic time (PPT) adversary (deprived of unbounded computational power)
- adversary is allowed to success with negligible advantage
It is called asymptotic computational secrecy.
(Non-)Negligible advantage is an asymptotic concept.
$\varepsilon(n)$ denotes the negligible probability for a fixed security parameter $1^n$. For example, the probablistic $\Pr[\mathtt{PrivK}^{eav}_{\mathscr{A}, \Pi}(n)=1]\geq\frac{1}{2}+\varepsilon(n)$ indicates that adversary successes in the EAV experiment with non-negligible advantage: $\Pi$ is EAV-secure.
相信学习过密码学的同学所接触的第一个加密方法都是一次性密码本 One-time pad，这也是最令我惊叹的加密方法之一：其操作是那样的简单优美，只需要将明文和密钥异或起来即可生成密文。
然而，就是这么简单的算法，居然满足完美安全的定义：也就是说，按照 OTP 算法生成的密文 $c$，只要我将密钥 $k$ 彻底销毁，那么全宇宙就没人能够得到其对应的明文 $m$. 即使是拥有无穷算力的超高级文明，也无法获取关于 $m$ 的任何信息，哪怕 $1$ bit 都不行！
这不禁让我的中二之魂熊熊燃烧……
P.S. 事后我想了想，如果 $m$ 是有意义的一段文字，那么超高级文明得到 $m$ 并不会很难。所以超高级文明永远无法得到我随便乱想的一段乱码 $m$ ! (骄傲)