语义安全

语义安全（英語：Semantic Security）是密码学中的术语。如果已知某段未知文段的密文不会泄露任何该文段的其余信息，那么则称该密文是语义安全的。具体而言，给定某条消息${\displaystyle m}$（消息满足任意概率分布）的密文和消息的长度，任何概率多项式时间算法（PPTA）都不能以不可忽略地高于任何仅输入消息长度（而不含密文）的其他PPTA的概率获得消息的部分信息。^[1] 该概念相似于香农的完善保密性定义。完善保密性意味密文不会泄露任何明文的信息，而语义安全侧重表示被揭露的信息不会被实际窃取。^{[2][3]:378-381}

历史

语义安全的概念首先由戈德瓦塞尔（Goldwasser）和米卡里（Micali）在1982年提出^[1]，两人后来证明了语义安全和另一性质密文不可辨别性（英语：Ciphertext indistinguishability）是等价的。^[4] 后者定义比语义安全更通用，因为它更能实施于检验实际加密方式的安全性。

对称密钥加密

主条目：對稱密鑰加密

在语义安全的對稱密鑰加密加密算法系统中，对抗者不可能从密文获得明文。如交给两段相同长度的明文与其中之一的密文，将不可分辨该密文所对应的明文。

公钥加密

主条目：公钥加密

为了使非对称密钥加密算法密码系统语义安全，当仅给定某密文和生成密文时所用的公钥时，计算受限的对手应当无法获得有关消息（明文）的重要信息。语义安全只考虑“被动”攻击者的情况，即攻击者可以选择公钥和明文，并观察生成的密文。与其他安全定义不同，语义安全不考虑选择密文攻击（CCA）的情况，选择密文攻击指的是攻击者能够请求解密选定的密文。许多语义安全的加密方案对于选择密文攻击显然是不安全的。因此，语义安全现在被认为是构建通用加密方案的一个不充分条件。

语义安全的加密算法包括Goldwasser-Micali（英语：Goldwasser–Micali cryptosystem）、ElGamal和Paillier（英语：Paillier cryptosystem）。这些方案被认为是可证明安全（英语：Provable security）的，因为它们的语义安全性可以简化为解决一些困难的数学问题（例如，Decisional Diffie-Hellman或二次剩余问题（英语：Quadratic Residuosity Problem））的复杂性。其他语义不安全的算法，如RSA，可以通过使用最优非对称加密填充（OAEP）等随机加密填充方案实现（在更强的假设下的）语义安全。

参考文献

1. 莎菲·戈德瓦塞尔和Silvio Micali，Probabilistic encryption & how to play mental poker keeping secret all partial information （页面存档备份，存于互联网档案馆）, Annual ACM Symposium on Theory of Computing, 1982.
2. Shannon, Claude. Communication Theory of Secrecy Systems. Bell System Technical Journal. 1949, 28 (4): 656–715. 
3. Goldreich, Oded. Foundations of Cryptography: Volume 2, Basic Applications. Vol. 2. Cambridge university press, 2004.
4. Probabilistic encryption. Journal of Computer and System Sciences, 28:270-299, 1984.