動機
公鑰加密規則必須讓任何人都能構造密文,卻不能讓每個人都能解密。確定性加密立刻帶來一個問題:觀察者可以對兩個猜測的明文分別加密,再與挑戰密文比較。隨機性可以防止這種直接比較,但僅僅說密文「看起來是隨機的」並不是證明。我們需要一個明確規定的實驗,以及一個把該實驗與某個困難數學問題聯繫起來的明確假設。
ElGamal 提供了一個清晰的例子。它的解密等式來自循環群中指數的交換律。它的保密性論證則使用一個更強且獨立的斷言:某個特定的共享群元素在計算上應與一個獨立的均勻群元素不可區分。把這個共享元素換成隨機遮罩之後,挑戰明文就從其分佈中消失了。
我們證明這一條件性陳述,其中包括用固定的有界個公平位元來實現隨機指數。這裏的明文是群元素。我們不構造任意字串的編碼、帶認證的系統,也不構造已部署的參數集;這些都需要進一步的定義與構造。
定義
對每個正的安全參數 ,假設給定一個質數階 的循環群 。它的描述以及定長的群元素規範編碼的長度都是 的多項式。乘法、求逆、成員判定以及用二進制整數作指數的冪運算都在多項式時間內完成。 的位元長度受多項式限制。這些是明確的群族假設;本章既不構造這樣的群族,也不證明其困難性。
定義 4.2.1
(判定性 Diffie–Hellman 假設)
離散對數問題是由 求 。計算性 Diffie–Hellman 問題是由 求 。判定性 Diffie–Hellman 假設(DDH)是指:沒有任何有界概率多項式時間算法能以不可忽略的優勢區分分佈
其中 在 中獨立均勻取值。優勢定義為輸出為一的兩個概率之差的絕對值。若對每個正整數 ,函數最終都至多為 ,則稱該函數是可忽略的。這裏的理想分佈是數學實驗;我們並不聲稱用有界的公平位元帶可以從奇數大小的集合中精確取樣。
定義 4.2.2
(ElGamal 加密)
理想的加密規則是
其中 。對於正確性,任何 都是允許的。有界位元實現則用下面所證明的程序來取樣秘密 和每個新的隨機數 。
概念視角結構
Diffie–Hellman 交換之後接一個群上的一次一密
ElGamal 是一次臨時的 Diffie–Hellman 交換,再接一個乘法遮罩。新鮮的 與公開的 決定共享元素 :發送者把它算成 ,接收者把它算成 。訊息被遮罩為 ,這是群 上的一次一密,再乘以 便去掉遮罩。安全性證明把共享元素換成一個獨立的均勻元素;到了那一步,這個遮罩就完美地隱藏了 。
定義 4.2.3
(選擇明文不可區分性實驗)
在選擇明文不可區分性實驗中,敵手收到 ,選擇兩個合法的群明文 ,並保留任意多項式大小的狀態。挑戰者選取一個新的公平位元 ,用新的隨機數加密 ,再讓敵手猜測 。其優勢為 。敵手可以自己進行任意多項式次數的公開加密;在這一公鑰實驗中不需要秘密的加密預言機。不提供解密預言機。
定理/命題
定理 4.2.4
(正確性與有界位元指數取樣)
ElGamal 能把其加密規則產生的每個合法密文解密為原來的群明文。此外,若 ,則把一個 位元均勻整數模 約化,得到的分佈在全變差距離下與 上的均勻分佈相差不超過 ,且運行時間有固定的多項式上界。
定理 4.2.5
(選擇明文保密性由 DDH 推出)
對每個有界概率多項式時間的選擇明文敵手 ,存在這樣的 DDH 區分器 ,使得
對上述有界位元實現成立。因此 DDH 蘊含可忽略的選擇明文優勢。該定理斷言的是在所指定實驗中的機密性;它並不斷言選擇密文安全性或密文完整性。
證明思路或證明
正確性是一個代數恆等式
證明
(指數恆等式)
對於合法密文,。因此 。解密時不需要計算任何對數。秘密指數允許對收到的第一分量作冪運算;它並不是從任意群元素中提取指數的方法。當任一指數為零時該公式仍然正確,不過這些罕見的選擇可能暴露訊息,必須計入安全性實驗的概率核算之中。
用有界公平位元近似均勻指數
證明
(計算原像並比較實驗)
令 。模 的每個剩餘類在這 個整數中恰有 或 個原像。因此其概率與 之差小於 。按全變差距離定義為絕對差之和的一半,所得距離至多為 。在所述規模假設下,抽取 個公平位元並做整數除法的代價是有界的多項式。
我們還要用到全變差的兩個初等推論。對兩個分佈施加共同的確定性或隨機化後處理不會使它增大:對任一輸出事件,把其條件概率(介乎零與一之間的數)分別對兩個輸入分佈取平均即可。把兩次獨立抽樣(各自與其理想分佈相差不超過 )替換後,聯合分佈至多改變 ,做法是一次替換一個抽樣並使用三角不等式。即使後面的訊息依賴於較早的抽樣,這些陳述仍然成立。
把它們應用到密鑰指數與挑戰隨機數上。用同一個敵手代碼、它的隨機硬幣以及挑戰位元,對兩個完整實驗進行耦合或比較。轉錄與最終成功事件的概率至多相差 。敵手內部進行的公開加密只是同一個隨機化後處理的一部分,因此那裏不需要未經說明的精確非二進制取樣。
把敵手嵌入 DDH 檢驗
證明
(把敵手變成區分器的包裝)
先分析理想指數實驗。給 一個來自兩種 DDH 分佈之一的三元組 。它把 作為公鑰發給 ,獲得其兩條訊息和狀態,選取一個新的公平位元 ,並把密文 交給 。當 猜對 時,區分器恰好輸出一。所有包裝操作都是高效的,而且 從不計算未知指數。
對於真實的 Diffie–Hellman 三元組, 且 。於是模擬出的密文恰好具有理想的加密分佈, 以該實驗的成功概率輸出一。
對於獨立三元組, 在群中均勻分佈,並且獨立於公鑰、、所選訊息和敵手狀態。在這些數據以及 的任一取值的條件下,乘以 是群上的雙射。因此 是均勻的,且兩種選擇下具有相同的分佈。完整視圖不洩露關於新位元的任何資訊,每個猜測策略的成功概率恰為二分之一。所以,按我們的絕對值約定,兩個輸出為一的概率之差恰是理想選擇明文優勢。
最後,用前面的 界把有界位元實現與理想實驗進行比較。三角不等式即給出該定理。在假設下,加性的統計項是可忽略的,DDH 優勢也是可忽略的;它們之和是可忽略的。這裏證明的是對生成密鑰取平均的概率界,並不是保證每一個可能的密鑰都具有同樣的保密性。
證明透視
歸約並沒有解決 Diffie–Hellman 問題
挑戰三元組的每個分量各有一個用途。 成為公鑰, 成為密文第一分量,所以敵手看到的密鑰與隨機數恰好具有理想分佈。第三分量 只用作訊息遮罩;包裝程序從不需要 、 或 ,所以它能高效運行,也因此並沒有證明任何求解 Diffie–Hellman 的能力。
關鍵一步是隨機分支。 獨立於 、、所選訊息與敵手狀態,使 對 的兩個取值都均勻,所以該分支中的成功概率恰為二分之一;僅有 的邊際均勻性並不足夠。論證以相減收結:區分器的優勢等於理想選擇明文優勢,而有界位元取樣經三角不等式再加上 。
例題詳解
例題 4.2.6
(一個完整的玩具加密與解密)
在模二十三下,取由二生成的子群。由於 且二不等於一,這個子群的質數階為十一。取秘密 ,公鑰 ,訊息 ,隨機數 。於是 ,,。密文為 。
解密計算 。它模二十三的逆元是十二,所以 ,即原來的訊息。對十一個指數的窮舉搜尋立即就能攻破這個玩具群。它只說明代數上的正確性,並不為漸近的 DDH 假設提供任何證據。
例題 4.2.7
(重複使用隨機數會洩露訊息之比)
用同樣的密鑰和隨機數加密訊息四和八。密文為 與 。它們第二分量之比 等於訊息之比 。一般地,重複使用 會給出 。若其中一條訊息已知,另一條通過乘法即可恢復。獨立的新隨機數是實驗的明確組成部分;解密的正確性不能彌補隨機性假設的失敗。
例題 4.2.8
(一次有意的密文修改)
把第二分量乘以二,將 改為 。它解密為八,即原訊息的兩倍。更一般地,對每個已知的 , 解密為 。
這給出一個選擇密文攻擊:收到挑戰 後,選取 ,向解密預言機詢問不同的密文 。把它的回答除以 即得到挑戰訊息,進而對不同的兩條訊息得知所選的位元。該詢問不同於被禁止的挑戰密文,所以僅僅禁止這個確切的詢問並不能阻止此攻擊。選擇明文定理仍然有效,因為它的遊戲中沒有提供這樣的預言機。
常見錯誤
反例模式
被遮蔽群以外的訊息
均勻遮罩論證使用的是乘法在確切的訊息群上的雙射性。設在上面的玩具例子中允許訊息來自環境群 ,其中 的階為十一。取 與 。由於 ,元素 不在 中。每個密文都有 ,其中 ,所以不論密鑰與隨機數為何, 時 , 時 。一次冪運算便確定地恢復 。修正正是定理的假設:兩條挑戰訊息都必須屬於 。任意位元串需要另行分析的編碼或混合構造。
常見錯誤
(DDH 是計算性的,不是統計性的)
DDH 是一個計算性不可區分假設,並不是說 Diffie–Hellman 三元組在統計上是均勻的:無界的觀察者可以恢復指數並加以檢驗。此外,離散對數求解器可得到共享秘密求解器,後者又可得到判定檢驗;這些容易的方向並不能證明相反方向的等價性。最後,帶認證的通訊系統需要對修改提供進一步的保護,正如這個明確的攻擊所展示的那樣。
常見錯誤
(新的不等於永不重複)
「新的隨機性」指的是一個新的獨立樣本,而不是承諾某個值永遠不會再次出現。在理想的均勻取樣下,兩次隨機數抽樣相同的概率為 ;對 次抽樣取並集界,碰撞概率至多為 。有意重複使用已儲存的隨機數則是另一個過程,獨立性論證不再適用。
總結
加密等式對每個指數都證明了正確性。一個精確陳述的 DDH 假設,通過把共享值替換為均勻群遮罩的包裝器,證明了選擇明文機密性。有界位元的指數生成引入了一個明確可忽略的統計誤差。這些陳述都不能阻止乘法式的密文修改,也不能解決其餘的編碼與認證問題。
練習
快速檢查
(解釋為甚麼確定性的、公開可計算的、正確的加密在對不同明文的雙訊息挑戰實驗中會失敗。)
解答
對兩條所選訊息分別加密,並將挑戰與這兩個輸出比較。正確的解密蘊含這兩個密文不同:否則一個密文必須同時解密為兩條訊息。因此比較可以確定地恢復位元,按我們的約定優勢為二分之一。
快速檢查
(當秘密指數為零時,ElGamal 密文會發生甚麼?為甚麼這一觀察本身並不能反駁取平均密鑰的定理?)
解答
此時公鑰為一,第二分量等於明文。在理想分佈下這個密鑰出現的概率為 ,是可忽略的。該定理是對生成的密鑰取平均的,可以允許一個可忽略的例外集合。它並不為被有意選取的零密鑰確立安全性。
快速檢查
(為甚麼證明必須要求替換遮罩獨立於公鑰和挑戰的第一分量,而不僅僅是邊緣分佈上均勻?)
解答
邊緣均勻性在取條件後不一定保持。例如,一個等於另一個公開均勻群元素的均勻遮罩,在觀察到那個元素之後就完全已知。隨機 DDH 實驗提供了條件均勻遮罩論證所需的更強的獨立性。
快速檢查
(若每個指數取樣器與均勻分佈相差不超過 ,則定理中的統計項 應換成甚麼?)
解答
一次一個地替換密鑰抽樣和挑戰隨機數抽樣。三角不等式以及在共同敵手計算下的收縮性給出成功概率的總變化至多為 。因此同一歸約給出 DDH 優勢加上 ;只有當這個統計項本身可忽略時,才能推出可忽略性。