群上的离散对数问题

群上的离散对数问题：给定群$G$的生成元$g$和$G$中的随即元素$h$，计算$\log _gh$。这个问题在许多群中都被认为是困难的，称其为离散对数假设。

令GroupGen是一个多项式时间算法，其输入为安全参数$\mathcal{K}$，输出为一个阶等于$q$的循环群$G$的描述，以及一个生成元$g\in G$，它的离散对数假设定义如下：

GroupGen的离散对数问题是困难的，如果对于所有的PPT算法$A$，下式是可忽略的

$Pr[(G,g)\larr GroupGen(\mathcal{K});h\larr _RG;x\larr \mathcal{A}(G,g,h)],st\ g^x=h$

如果GroupGen的离散对数是困难的，且G是一个有GroupGen输出的群，则称离散对数问题在G中是困难的。

ElGamal加密算法是IND-CPA安全的，

密钥产生过程：

$KenGen(\mathcal{K}):\\ (G,g)\larr GroupGen(\mathcal{K});\\ x \larr_R Z_q,y=g^x\\ pk=(G,g,y),sk=x$

加密过程

$\varepsilon_{pk}(M):\\ r\larr _RZ_q\\ output\ (g^x,y^rM)$

解密过程

$D_{sk}(A,B)$

离散对数问题意味着给定公开钥，没有敌手能确定秘密钥。然而，这不足以保证方案是IND-CPA安全的。实际上，可以找到一个特殊的群，其上的离散对数假设成立，但建立在其上的ElGamal加密方案却不是IND-CPA的。

例如$Z_p^*$上的离散对数假定是成立的，但在多项式时间内可判定$Z_P^{*}$是否为二次剩余。而且$Z_P^*$中的生成元g不可能是二次剩余，否则其元素都是二次剩余。这就导致一种针对ElGamal的直接攻击：敌手产生两个等长的消息$(M_0,M_1)$使得$M_0$是二次剩余，$M_1$是二次非剩余。给定密文（A,B）则存在r使得$A=g^x,B=y^rM_{\beta}$，可以在多项式时间内判定$y^r$是否为二次剩余。

例如A是二次剩余，则存在一个a使得$a^2=A$，将a写成生成元g的幂$g^a$，那么$A=g^{2a},r \equiv 2\alpha\mod (p-1)$。

如果A或y是二次剩余，则x，r至少有一个是偶数，所以$y^r=g^{xr}$也是一个二次剩余。通过观察B，就能判断$M_{\beta}$是否为二次剩余。进而可以判断出加密的是哪个消息。

因此，为了证明ElGamal加密方案的语义安全性，我们需要一个更强的假设。

判断性Diffie-Hellman(DDH)假设

判断性Diffie-Hellman(Decisional Diffie-Hellman)假设（DDH假设）指的是区分元组$(g,g^x,g^y,g^{xy})$和$(g,g^x,g^y,g^z)$是困难的，其中g是生成元，x,y,z是随机的

设G是阶为大元素q的群，g为G的生成元，$x,y,z\larr _RZ_q$，则以下两个分布：

• 随机四元组$R=(g,g^x,g^y,g^z)\in G^A$
• 四元组$D=(g,g^x,g^y,g^{xy})\in G^A$在计算上是不可区分的。

对任一敌手$\mathcal{A}$，$\mathcal{A}$区分R和D的优势$Adv_{\mathcal{A}}^{DDH}(\mathcal{K})=|Pr[\mathcal{A}(R)=1]-Pr[\mathcal{A}(D)=1]|$是可忽略的。

在DDH假设下，ElGamal加密方案是IND-CPA安全的。