1.5 Cramer-Shoup公鑰加密方案

1998年，Cramer和Shoup提出了一個實用且滿足自適應性選擇密文安全的公鑰加密方案。本節簡要回顧Cramer-Shoup加密方案的構造和安全性分析。

1.5.1 方案描述

1.5.2 安全性分析

Cramer-Shoup加密方案的安全性基于一個DDH問題的變體，我們首先給出DDH問題的變體。

DDH問題的變體：設（G，p，g）是一個循環群，其中p為群G的階，g為群G的生成元。已知群元素（g，ga，gb，gac，Z）∈G，判斷Z是否等于gbc，其中a，b，c是未知的。

定理1.3 如果DDH問題的變體是難解的，那么Cramer-Shoup加密方案是IND-CCA安全的。

證明：假設在IND-CCA安全模型中，存在一個攻擊算法A，能以不可忽略的優勢ε攻破Cramer-Shoup加密方案，那么我們可以構造一個模擬算法B通過與A交互，以不可忽略的優勢解決DDH問題的變體。設B以循環群（G，p，g）上DDH問題的變體的實例（g₁，g₂，，）作為輸入。

系統建立：令系統參數SP=（G，g，p，H），其中H：{0,1}*→Z_p為密碼哈希函數，B隨機選取α₁，α₂，β₁，β₂，γ₁，γ₂∈Z_p作為私鑰，設公鑰為

公鑰可以從問題實例和給定的參數計算得到。

詢問1：在該階段，敵手允許詢問密文解密。設詢問的密文為CT，由于B知道私鑰，它運行解密算法并將解密結果返回給敵手。

挑戰：A輸出兩個不同的挑戰消息m₀，m₁∈G。B隨機選取c∈{0,1}，計算挑戰密文，其中由問題實例給出。令r=a₁，如果a₁=a₂，有

因此，CT*為正確的挑戰密文，其加密的消息為m_c。

詢問2：敵手在該階段可繼續向挑戰者發出解密詢問，但不能詢問CT*的解密，挑戰者的響應方式與詢問1相同。

猜測：A輸出對挑戰密文中消息的猜測c′，若c=c′，B輸出True，表示給定實例是正確的DDH元組，否則輸出False，表示不是正確的DDH元組。

根據證明的設置，模擬者B知道私鑰，因此能執行和真實攻擊環境不可區分的解密模擬。在生成私鑰和挑戰密文中，所有的數都是隨機選取的，所以模擬和真實攻擊是不可區分的。在證明中，模擬沒有出現失敗的情況，故模擬成功的概率為1。接下來分析B解決困難問題的概率。

若問題實例中的Z是正確的，該方案的模擬與真實的方案攻擊不可區分，因此敵手有1/2+ε/2的概率猜到正確的加密消息。若Z是錯誤的，敵手最多以的概率正確地猜測到加密消息，分析如下：

令，其中z∈Z_p，則敵手可以從公鑰中得到z，α₁+zα₂，β₁+zβ₂，γ₁+zγ₂，可以從挑戰密文中獲得a₁，a₂，a₁（α₁+w*β₁）+za₂（α₂+w*β₂），a₁γ₁+a₂γ₂+。如果γ₁，γ₂對于敵手是未知的，且沒有發起解密詢問，那么γ₁+zγ₂和a₁γ₁+a₂zλ₂是隨機且獨立的，因為以下系數矩陣的行列式為非零：

在該情況下，從敵手的視角看，挑戰密文可以看作對消息m_c的一次一密加密得到，因此敵手沒有任何的優勢猜到正確的c。下面證明解密詢問不能幫助敵手以不可忽略的優勢攻破挑戰密文。

設）的解密詢問通過驗證，解密結果將返回給敵手C₃·，敵手通過計算得到r₁γ₁+r₂zγ₂。如果r₁=r₂，則敵手所知道的相當于γ₁+zγ₂，因此，敵手無法獲取額外的信息來破解一次一密加密。否則，敵手可以通過γ₁+zγ₂和r₁γ₁+r₂zγ₂計算出γ₁，γ₂來破解密文，從而攻破一次一密加密算法。下面證明B能夠以不可忽略的概率拒絕所有與挑戰密文不同的無效密文。敵手提交的無效密文分以下兩種情況討論：

1）且，此時B拒絕該形式的密文，因為只有才會通過驗證。

2），由于哈希函數是安全的，因此有。如果以下等式成立，則密文可以通過驗證：

也就是說如果敵手能計算出r₁(α₁+wβ₁)+r₂z(α₂+wβ₂)，即可通過驗證。

根據證明，包括r₁(α₁+wβ₁)+r₂z(α₂+wβ₂)在內的所有與α₁,α₂,β₁,β₂相關的參數為：

α₁+zα₂

β₁+zβ₂

a₁(α₁+w*β₁)+za₂(α₂+w*β₂)

r₁(α₁+wβ₁)+r₂z(α₂+wβ₂)

(α₁,α₂,β₁,β₂)相應的系數矩陣為

矩陣行列式的值為z(r₂-r₁)(a₂-a₁)(w*-w)≠0，因此，r₁(α₁+wβ₁)+r₂z(α₂+wβ₂)是隨機的且與其他給定參數無關。所以，除了以1/p的概率產生C₄通過驗證，敵手沒有任何優勢。

當敵手產生一個錯誤的密文提交給解密詢問時，第一次自適應選擇C₄成功的概率為1/p，第二次自適應選擇C₄成功的概率為1/(p-1)。因此，對于q_d次解密詢問，成功生成一個可以通過驗證的不正確密文的概率最多為。此外，敵手有1/2的概率從密文中猜對c。綜上所述，敵手最多有的概率正確地猜到加密消息。因此，B解決DDH問題的變體的優勢為