跳至內容

語義安全

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

語義安全(英語:Semantic Security)是密碼學中的術語。如果已知某段未知文段的密文不會泄露任何該文段的其餘信息,那麼則稱該密文是語義安全的。具體而言,給定某條消息(消息滿足任意概率分布)的密文和消息的長度,任何概率多項式時間算法(PPTA)都不能以不可忽略地高於任何僅輸入消息長度(而不含密文)的其他PPTA的概率獲得消息的部分信息。[1] 該概念相似於香農完善保密性定義。完善保密性意味密文不會泄露任何明文的信息,而語義安全側重表示被揭露的信息不會被實際竊取。[2][3]:378-381

歷史

語義安全的概念首先由戈德瓦塞爾(Goldwasser)和米卡里(Micali)在1982年提出[1],兩人後來證明了語義安全和另一性質密文不可辨別性英語Ciphertext indistinguishability是等價的。[4] 後者定義比語義安全更通用,因為它更能實施於檢驗實際加密方式的安全性。

對稱密鑰加密

在語義安全的對稱密鑰加密加密算法系統中,對抗者不可能從密文獲得明文。如交給兩段相同長度的明文與其中之一的密文,將不可分辨該密文所對應的明文。

公鑰加密

為了使非對稱密鑰加密算法密碼系統語義安全,當僅給定某密文和生成密文時所用的公鑰時,計算受限的對手應當無法獲得有關消息(明文)的重要信息。語義安全只考慮「被動」攻擊者的情況,即攻擊者可以選擇公鑰和明文,並觀察生成的密文。與其他安全定義不同,語義安全不考慮選擇密文攻擊(CCA)的情況,選擇密文攻擊指的是攻擊者能夠請求解密選定的密文。許多語義安全的加密方案對於選擇密文攻擊顯然是不安全的。因此,語義安全現在被認為是構建通用加密方案的一個不充分條件。

語義安全的加密算法包括Goldwasser-Micali英語Goldwasser–Micali cryptosystemElGamalPaillier英語Paillier cryptosystem。這些方案被認為是可證明安全英語Provable security的,因為它們的語義安全性可以簡化為解決一些困難的數學問題(例如,Decisional Diffie-Hellman二次剩餘問題英語Quadratic Residuosity Problem)的複雜性。其他語義不安全的算法,如RSA,可以通過使用最優非對稱加密填充(OAEP)等隨機加密填充方案實現(在更強的假設下的)語義安全。

參考文獻

  1. ^ 1.0 1.1 莎菲·戈德瓦塞爾Silvio MicaliProbabilistic 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.