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问题的变体的优势为