語意安全

語意安全(英語: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.