ElGamal 加密

形式陈述 ​

设群生成算法 $\mathsf{GrpGen}(1^{\lambda })$ 输出素数阶循环群公理库循环群Cyclic group由单个元素的整数次幂生成的群。 $(G,q,g)$，群运算、逆元、元素采样与成员验证都相对安全参数 $\lambda$ 高效。Textbook ElGamal 的消息空间是 $G$；任意应用消息必须先通过明确且可逆的编码进入群，不能把任意 bit 串无条件代入群乘法。

方案由三个 PPT 算法组成：

$$\begin{array}{rl}\mathsf{KeyGen}(1^{\lambda }):& (G,q,g)\leftarrow \mathsf{GrpGen}(1^{\lambda }),x\leftarrow {\mathbb{Z}}_q,h=g^x,\\ & pk=(G,q,g,h),sk=x;\\ {\mathsf{Enc}}_{pk}(m;r):& r\leftarrow {\mathbb{Z}}_q,(c_1,c_2)=(g^r,m{h}^r);\\ {\mathsf{Dec}}_{sk}(c_1,c_2):& m^{\prime }=c_2/(c_1{)}^x.\end{array}$$

对合法密文，正确性由

$$\frac{m{h}^r}{(g^r{)}^x}=\frac{m{g}^{xr}}{g^{rx}}=m$$

直接得到。解密接口在实际方案中还应检查 $c_1,c_2\in G$，对非法编码返回 $\mathrm{\perp }$；基础代数式本身不处理无效点、小子群或解析错误。

标准 IND-CPA 游戏把 $pk$ 交给 PPT 对手 $A$。由于加密密钥公开，$A$ 可自行执行任意多次加密；它提交两条合法群元素消息 $m_0,m_1$，挑战者均匀采样 $b\leftarrow \{0,1\}$ 与新鲜 $r\leftarrow {\mathbb{Z}}_q$，返回

$$c^{\ast }=(g^r,m_b{h}^r).$$

对手输出 $b^{\prime }$。本页采用归一化优势

$${\mathrm{Adv}}_{\mathsf{EG},A}^{\mathsf{ind}\mathsf{\text{-}}\mathsf{cpa}}(\lambda )=|2\text{Pr}[b^{\prime }=b]-1|;$$

若文献采用 $|\text{Pr}[b^{\prime }=b]-1/2|$，其数值小一半。概率包含参数生成、密钥、挑战 bit、临时指数和对手随机币；安全性要求该优势对每个 PPT 对手均随 $\lambda$ 可忽略。

证明通过一个游戏替换完成：把 $h^r=g^{xr}$ 换成独立均匀 $u\leftarrow G$。真实游戏与替换游戏的区分优势受DDH 优势公理库判定 Diffie–Hellman 假设Decisional Diffie–Hellman assumption · DDH assumption随机 Diffie–Hellman 三元组与以独立随机群元素结尾的三元组对高效判别器不可区分。界定；替换后 $m_{b}u$ 对任意固定 $m_b\in G$ 都是均匀群元素，与 $b$ 独立。这里需要 DH tuple 与随机 tuple 的判定不可区分性，只有“攻击者算不出 $g^{xr}$”的 CDH 假设不足以证明这个分布替换。

直觉 ​

每个密文都携带一个临时公开值 $g^r$。接收者用私钥 $x$ 从它重建 $g^{rx}$，发送者则用公钥 $h=g^x$ 与临时指数 $r$ 算出同一元素 $h^r$；这个一次性群元素像乘法掩码，把消息移到群中的另一个位置。DDH 保证旁观者无法判断掩码是这个共享值还是独立随机元素。

随机指数不是装饰。同一消息在不同 $r$ 下产生不同密文，才阻止攻击者把候选消息的确定加密与挑战直接比较。随机性提供的是每次加密的新共享值；长期私钥 $x$ 可以保持不变，但临时 $r$ 必须按方案要求独立、均匀并保密。

例子与边界 ​

若同一公钥下分别加密 $m_1,m_2$，得到

$$(g^{r_1},m_1{h}^{r_1}),(g^{r_2},m_2{h}^{r_2}),$$

逐分量相乘产生

$$(g^{r_1+r_2},m_1{m}_2{h}^{r_1+r_2}),$$

它正是消息 $m_1{m}_2$、随机数 $r_1+r_2$ 的合法密文。这项乘法同态可服务于聚合，却也表明密文能被有结构地修改；同态性是代数性质，不是主动攻击安全。

攻击者可以把挑战密文 $(c_1,c_2)$ 改成 $(c_1,c_{2}t)$，其中 $t\in G$ 且 $t\ne 1$。解密结果随之从 $m$ 变成 $mt$，而攻击者无需知道 $m$。因此 textbook ElGamal 可塑，不满足 IND-CCA；若解密 oracle 接受相关密文，它可能把这种关系转成明文信息。CCA 安全需要额外认证或经过证明的变换，不能由 DDH 和同态性自动获得。

复用 $r$ 会复用第一分量和掩码。若 $(g^r,m_1{h}^r)$ 与 $(g^r,m_2{h}^r)$ 使用同一临时指数，任何人都能计算第二分量之比 $m_1/m_2$；已知其中一条消息时可恢复另一条。偏置、可预测或泄漏部分信息的随机数也可能破坏证明中的均匀指数分布。

群编码是另一条边界。把任意字符串直接解释成整数，可能得到不在 $G$ 中的元素或产生多种编码；实现必须使用规定的群元素映射、混合加密或 KEM。收到的群元素还要验证成员资格，否则标准 DDH 游戏没有覆盖的小子群与无效曲线攻击可能泄漏 $x$。

推论与应用 ​

ElGamal 是公钥加密公理库公钥加密Public-key encryption加密密钥公开而解密密钥保密的加密体系。中连接代数构造与安全游戏的基础实例：正确性来自指数律，IND-CPA 来自 DDH 归约，CCA 失败则来自可塑性。它也说明安全结论必须连同消息空间、群族、随机数分布和攻击接口一起陈述。

其乘法同态结构用于重随机化、电子投票和阈值解密等协议；这些系统通常还要加入有效密文证明、认证、域分离和针对恶意参与者的验证。工程中的大消息加密更常把 DH 类公钥运算用于建立短会话密钥，再由认证对称加密处理正文，而不是把每段数据直接编码为群元素。

参考资料

• Taher ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory 31(4), 1985。
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，public-key encryption and ElGamal。
• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，Diffie–Hellman systems and game-based proofs。