如何理解"語義安全(semantic security)"?

看斯坦福大學的《密碼學》，在引入語義安全的時候，有幾個概念Adv(A,E), EXP(b),對這幾個概念不太理解。

能否介紹一下什麼是語義安全?

給出一下語義安全的定義,以及通俗解釋

---

謝邀。

看到越來越多的知乎er們開始關注信息安全與密碼學，並從Dan Boneh的公開課開始學習了，這太令我興奮了~ 最近正在醞釀第一個專欄，正是要從語義安全（Semantic Security）入手，結合Black Hat的一個視頻，來分析為何即使使用了正確的密碼學演算法，攻擊者還有可乘之機。

這個答案，我將按照Dan Boneh的講解思路，嘗試用淺顯易懂的話語描述語義安全性的定義，並對其進行解釋。所有插圖都是從Dan Boneh《密碼學》課的Week 1: 2 - 6 - Semantic Security截圖出來的。有興趣的同學可以查閱鏈接：Coursera - Free Online Courses From Top Universities。

=============================

0. 完美保密性（Perfect Secrecy）與實際保密性（Practical Secrecy）

我們都知道，加密演算法中有三個必備的東西：被加密的消息m，加密密鑰k，以及加密演算法對(E, D)。我們首先來定義一下什麼叫做加密演算法的保密性。

我們加密一個消息，最終的目的是什麼呢？最直觀地感覺就是，最終目的是不讓別人在沒有密鑰的條件下，從加密結果中恢復出原始的消息。這個定義本身沒問題，我們怎麼用數學方法描述呢？資訊理論的提出者Shannon給出了一個形式化的定義，這個定義就是我們所說的完美保密性：

這個定義的意思是，對於任意等長的消息m，只要這個m屬於消息空間（就是說用這個加密演算法可以加密m），那麼用加密密鑰k加密後，加密結果「看起來都一樣」，沒法看出來這是從m，還是從其他什麼消息加密得來的。

密碼學中證明了，唯一能達到這個安全條件的加密演算法叫做一次一密（One-time Pad），一次一密的問題在於加密時使用的密鑰長度至少要跟消息長度一樣才行。我們知道密鑰必須是秘密傳輸的。我靠，我都能秘密傳輸一個等長度的密鑰了，我為什麼還要用這個密鑰加密呢？我直接把消息秘密發送給對方不就完了… 所以說，一次一密在實踐中是沒有什麼應用價值的。

那怎麼辦呢？我們換種想法，上面那個定義說的是加密結果讓誰看，「看起來都一樣」。那乾脆，我們選一個迄今為止計算能力最強的人來看加密結果，要是他都覺得「看起來都一樣」，是不是就夠了？到現在為止，計算能力最強的就是計算機了，我們就讓一個計算機來看，如果他覺得「看起來都一樣」，那估計沒問題了。這就是我們所說的實際保密性：

與上面相比，就一個符號改變了，就是等號變成了約等於號。計算機計算能力最強能達到多少呢？按照圖靈機的定義，計算機最多能計算多項式時間內能解決的問題（Polynomial Time），並且計算機最多有多項式大的存儲空間（Polynomial Storage）。所以，只要計算機在多項式複雜度內看加密結果，覺得「看起來都一樣」，那我們就成功了。

=============================

1. 用計算機的計算能力描述實際保密性

現在的問題是，我們如何定義「對於任意等長的消息m」這個條件？我們要明確，隨著消息長度的增加，消息空間是指數級增長的！這個增長速度根本就是與計算機計算能力是衝突的。也就是說，我們定義裡面就要求計算機能解決指數級問題，這根本就行不通嘛。那怎麼辦呢？

密碼學家們用了一個巧妙的方法繞開了這個問題。我們用兩個計算機來定義好不好？一個計算機是來攻擊這個加密演算法的，叫攻擊者（Adversary，Adv.）；一個計算機是運行這個加密演算法的，接受攻擊者的攻擊挑戰，叫挑戰者（Challenger，Chal.），挑戰者拿著密鑰k，攻擊者的目的就是看看挑戰者運行加密演算法後，輸出的加密結果是不是「看起來一樣」。我們定義兩個實驗：實驗0（Experiment 0，EXP(0)），實驗1（Experiment 1，EXP(1)）。

實驗0：

1. 攻擊者自己任意選擇兩個消息m0、m1（注意，這個m0、m1是攻擊者自己選的）
2. 攻擊者把這兩個消息發送給挑戰者。

3. 挑戰者運行加密演算法，加密m0，把加密結果發送給攻擊者。

實驗1：

1. 攻擊者自己任意選擇兩個消息m0、m1（注意，這個m0、m1是攻擊者自己選的）
2. 攻擊者把這兩個消息發送給挑戰者。

3. 挑戰者運行加密演算法，加密m1，把加密結果發送給攻擊者。

攻擊者的目的呢？就是看到加密結果後，猜這個加密結果是由m0加密來的，還是由m1加密來的。這兩個實驗唯一的區別就是，挑戰者是返回m0的加密結果，還是返回m1的加密結果。而且，執行哪個實驗是挑戰者說了算！好啦，現在我們把這兩個實驗合起來：

實驗b：

1. 攻擊者自己任意選擇兩個消息m0、m1（注意，這個m0、m1是攻擊者自己選的）
2. 攻擊者把這兩個消息發送給挑戰者。

3. 挑戰者運行加密演算法，加密mb，把加密結果發送給攻擊者。

如果挑戰者以1/2的概率執行實驗0，以1/2的概率執行實驗1。那麼，如果加密結果真的沒辦法反映出原始消息的一點點信息，那麼攻擊者判斷正確的概率是多少呢？也應該是1/2嘛，因為加密結果沒法幫助到他，所以他也只能隨便猜，猜對了就撞大運了。也就是說，我們有：

這時候，我們引入攻擊者成功優勢（Advantage，Adv.）的概念。成功的優勢就是，如果挑戰者以1/2的概率執行實驗0，以1/2的概率執行實驗1，那麼攻擊者是否能有比1/2更大的概率猜測正確。如果有，這個增加的概率只能是從加密結果中得來的，因為攻擊者能利用的東西只有加密結果。我們定義：

如果攻擊者一點優勢都沒有，那麼這個優勢就是0，根據上面的定義，我們有：

但是，如果加密結果能反映出哪怕有關原始消息的一點點信息，攻擊者的成功概率就會增大對嗎？他就能以更大的概率判斷正確加密結果是從m0來的還是從m1來的。這個時候，就會有：

其中後面那個epsilon就是增加的概率。這個時候，攻擊者的攻擊優勢為：

=============================

2. 優勢的取值條件

我們要清楚的一個問題是，因為攻擊者拿到了加密結果，所以一定會增加成功的優勢。不過，這個優勢最大不能超過多大呢？密碼學中定義，這個優勢在多項式複雜度下是可忽略的（Negligible）就可以。什麼叫可忽略的呢？就是這個優勢很小，小到沒法用一個以位數為基本單位的多項式來描述，就可以了。舉例來說，對於一個128位安全常數的加密演算法來說，安全常數一般能達到1 / 2^128：位數是128位，優勢是2^{-128}，根本不是一個有關位數的多項式，而是一個指數式，這就可以了。

=============================

3. 總結

以上就是語義安全的定義，這種定義的方式叫做基於遊戲的安全定義（Game-Based Security Definition）。後續很多其他基於遊戲的安全定義，基本思想都是從語義安全來的，只不過增加了攻擊者的能力，比如：攻擊者可以找挑戰者要別的密文啦，攻擊者可以找挑戰者對另外給定的消息加密啦，等等。

---

我去翻我的微信公眾號，發現自己以前推了一篇可證明安全的筆記文章，裡面有一些語義安全的筆記。當然這是筆記，不是科普，所以可能會燒腦，畢竟是2010年寫的嘛=-=

[112]扯點密碼學：可證明安全隨筆

語義安全，在公鑰密碼體制中應用廣泛。一個語義安全的密碼系統要求計算能力有限的攻擊者無法僅僅從密文和公鑰中得到明文的重要信息。

語義安全實際考慮的是被動意義下的安全，即攻擊者只能根據自己設計的明文通過公鑰得到密文，並且考察密文的特性。文獻[1]中給出的語義安全的定義：即使攻擊者可以得到除y外任意密文對應的明文，但也無法得知m(y的明文)除長度外的任何信息。

語義安全沒有考慮選擇密文攻擊的情況，在選擇密文攻擊的情況下，攻擊者可以得到所選擇密文對應的明文，許多語義安全的體制在選擇密文攻擊的模型下是不安全的。所以，對於通用的加密體制而言，語義安全的標準已經不夠了。

Goldwasser/Micali於1982年提出語義安全，後面又證明了語義安全與密文不可區分性的等價性。文獻[1]表示，不可區分性指即使攻擊者可以得到除y外任意密文對應的明文，但是無法以遠大於1/2的概率確定y來源於哪一個mb的密文。

由於對手也擁有公鑰，因為加密演算法必須引入隨機性，否則攻擊者可以直接加密m0以及m1,直接和輸出進行對比，成功猜測oracle的選擇。

語義安全的加密演算法有Goldwasser-Micali,El Gamal，Paillier，它們都是可證明安全的，同時它們的語義安全可以歸約到一些數學難題上，例如DDH，二次剩餘等。

其他一些非語義安全的演算法如RSA可以在某些增強的假設下語義安全，例如OptimalAsymmetric Encryption Padding(OAEP).

References:

[1]. Koblitz, N. and A.J. Menezes, Another Lookat" Provable Security". Journal of Cryptology, 2007. 20(1): p. 3-37.

---

推薦閱讀：