到目前为止，我们已经抽象地讨论了公钥加密，但还没有看到任何公钥加密方案（或KEMs）的具体示例。在这里，我们探讨了一些基于Diffie–Hellman问题的构造。（Diffie–Hellman问题在第8.3.2节中介绍。）

11.4.1 El Gamal加密 El Gamal Encryption

1985年，Taher El-Gamal观察到Diffie–Hellman密钥交换协议（参见第10.3节）可适用于提供公钥加密方案。回想一下，在Diffie–Hellman协议中，Alice向Bob发送一条消息，然后Bob向Alice回复一条消息；基于这些消息，Alice和Bob可以导出一个共享值k，该值对于窃听者来说是无法与某个组G的统一元素区分的。我们可以想象Bob使用该共享值来加密消息m∈ G只需将k·m发送给Alice；Alice可以利用她对k的了解很明显地恢复m，下面我们将讨论窃听者对m一无所知。

在El Gamal加密方案中，我们只需改变对上述交互的看法。我们将Alice的初始消息视为她的公钥，将Bob的回复（包括他的初始响应和k·m）视为密文。基于决策Diffie-Hellman（DDH）假设的CPA安全性相当容易遵循Diffie-Hellman密钥交换协议的安全性（定理10.3）。

在我们的正式处理中，我们首先陈述并证明一个简单的引理，它是El Gamal加密方案的基础。设G为有限群， 可以是任意元素。引理表明，m乘以均匀群元素k得到均匀分布的群元素k'。重要的是，k'的分布与m无关；这意味着k'不包含关于m的信息。

引理11.15

设G为有限群，设m∈ G是任意的。然后选择均匀k∈ G和设置k':=k·m给出了与选择均匀k'相同的k'分布∈ G.换言之，对于任何 我们有 ，其中概率取k∈ G的均匀选择。

上述引理提出了一种利用消息空间G构造完全秘密私钥加密方案的方法。发送方和接收方共享一个统一的元素k∈ G作为其密钥.加密消息m∈ G、 发送方计算密文k':=k·m。接收方可以通过计算m:=k'/k从密文k'中恢复消息。从上面的引理可以立即得到完美的保密性。事实上，我们已经以不同的形式看到了该方案一次性pad加密方案是该方法的一个实例，底层组是在按位异或操作下的某个固定长度的字符串集。

我们可以通过为各方提供一种通过公共渠道交互生成共享的“随机”值k的方法，使上述想法适应公钥设置。这听起来应该很熟悉，因为这正是Diffie–Hellman协议所提供的。我们继续讨论细节。

如第8.3.2节所述，设G为多项式时间算法，以 为输入，并（除概率可忽略外）输出循环群G、其阶数q（||q||=n）和生成器G的描述。El Gamal加密方案在结构11.16中描述。

结构 11.16 El Gamal加密方案 The El Gamal encryption scheme

设G如文中所示。定义公钥加密方案，如下所示：

• Gen：在输入 时，运行 以获得（G，q，g）。然后选择一个均匀的x∈ Zq和计算h:=gx。公钥是< G、q、g、h>，私钥是< G、q、g、X>。消息空间是G。
• Enc：输入公钥pk=< G、q、g、h>和消息m∈ G、 选择一个统一的 并输出密文 。
• DEC：输入私钥SK= <G，Q，g，x>和密文< C1，C2>，输出

Exercises

11.6

考虑下面的公钥加密方案。公钥为（G，q，g，h），私钥为x，生成方式与El Gamal加密方案完全相同。为了加密位b，发送方执行以下操作：

（a） 如果b=0，则选择一个统一的 和计算 和。密文是<c1,c2>。

（b） 如果b=1，则选择独立均匀 ，计算和 ，并将密文设置为等于<c1,c2>。

证明了在已知x的情况下，有效解密是可能的。

证明了当决策Diffie-Hellman问题相对于G是困难时，该加密方案是CPA安全的。

11.7

考虑下面的El Gamal 加密变体。设p=2q+1，设G是模p的平方群（因此G是q阶 的子群），设g是G的生成器。私钥为（G，g，q，x），公钥为（G，g，q，h），其中 和 是统一选择的。对消息 进行加密，选择一个统一的 ，计算 和 ，并将密文设为<c1，c2>。这个方案安全吗？证明你的答案。