ElGamal密码、DDH、CDH简介及ElGamal在DDH下的IND-CPA 的安全性证明

ElGamal 在 DDH下的 IND-CPA 安全性

有关DDH和ElGamal

Diffie-Hellman Protocol

有限循环群 $\mathbb{G}$G $\left(e.g\quad G=\left(Z_{p}\right)^{*}\right)$(e.gG=(Zp​)∗)，其阶数为$n$n

在$G$G中取生成元$g$g: $<g>=\left\{1, \mathrm{g}, \mathrm{g}^{2}, \mathrm{g}^{3}, \ldots, \mathrm{g}^{\mathrm{n}-1}\right\}$<g>={1,g,g2,g3,…,gn−1},那么Diffie-Hellman Protocol如下图所示：

通过图述方式，Alice和Bob可以共享**$k_{AB}$kAB​。

ElGamal*

ElGamal是基于Diffie-Hellman Protocal的公钥加密方案。其同样基于有限循环群$\mathbb{G}$G和群中一固定的生成元$g$g，那么ElGamal可由下图描述：

（个人认为这个图比我在很多地方看到的文字叙述更容易理解。）

其中Enc，Dec是认证加密系统的加密和解密算法（比如对称加密方法），Gen是**生成算法。在实际应用时，Gen一般为一个Hashing Function(哈希函数)，即$k←Hash(g^b,g^{ab})$k←Hash(gb,gab)

Compute Diffie-Hellman Assumption

在上图，pk为我们选择的公钥，而其实你会发现$g^a$ga.$g^b$gb都是明文形式给出的。基于$g, g^a，g^b$g,ga，gb，得到$g^{ab}$gab是计算困难的, 这就是Compute Diffie-Hellman Assumption(CDH)。

Decision Diffie-Hellman Assumption

考虑阶数为$q$q的有限循环群$\mathbb{G}$G和群中一固定的生成元$g$g，已知$g^a$ga,$g^b$gb（$a, b \in \mathbb{Z}_{q}$a,b∈Zq​, 独立随机选取），若DDH Assumption成立，那么$g^{ab}$gab应与$\mathbb{G}$G中的随机元素不可区分。

如果DDH在群$\mathbb{G}$G中是困难的，那么对于所有概率多项式时间算法$\mathcal{A}$A都应存在可忽略的函数$negl$negl，其满足：
$\left|\operatorname{Pr}\left[\mathcal{A}\left(\mathbb{G}, q, g, g^{a}, g^{b}, g^{c}\right)=1\right]-\operatorname{Pr}\left[\mathcal{A}\left(\mathbb{G}, q, g, g^{a}, g^{b}, g^{ab}\right)=1\right]\right| \leq \operatorname{negl}(n)$∣∣​Pr[A(G,q,g,ga,gb,gc)=1]−Pr[A(G,q,g,ga,gb,gab)=1]∣∣​≤negl(n)
其中$a,b,c$a,b,c是在$\mathbb{Z}_{q}$Zq​中随机选取的。可以看出，DDH是强于CDH的假设。

ElGamal在DDH下的CPA安全性证明

由于ElGamal是一种公共**加密方案，因此，如果它对单个查询是安全的，则它对$q$q个查询也是安全的。因此，我们可以假设对手A恰好进行了一次查询。

我们假设攻击者攻击ElGamal时具有优势$Adv\mathcal{A}$AdvA。

构建攻击实验D如下：

Require：$\mathbb{G}, q, g, g^{a}, g^{b}, g^{z}$G,q,g,ga,gb,gz，Challenger， Adversary $\mathcal{A}$A，El Gamal scheme $\Pi$Π

1. 挑战者生成公钥$p k=\left\langle\mathbb{G}, q, g,g^{a}\right\rangle$pk=⟨G,q,g,ga⟩，发送给攻击者$\mathcal{A}$A
2. 攻击者选择希望被加密的明文$m_{0}, m_{1} \in \mathbb{G}$m0​,m1​∈G
3. 挑战者随机生成$b$b，向攻击者$\mathcal{A}$A发送$g^{b}$gb以及挑战密文$Enc(m_b, g^{z})\quad(b=0或b=1)$Enc(mb​,gz)(b=0或b=1)
4. 攻击者$\mathcal{A}$A判断密文是由哪条明文加密的，如果攻击者认为$b'=b$b′=b则输出$b'=1$b′=1，反之输出0。

当$z=rand$z=rand时，由于其是均匀随机选择的，所以$\mathcal{A}$A以1/2的概率输出1，即：
$\operatorname{Pr}\left[D\left(\mathbb{G}, q, g, g^{a}, g^{b}, g^{z}\right)=1\right]=\operatorname{Pr}\left[\operatorname{Pub} K_{\mathcal{A}, \Pi}^{\operatorname{eav}}(n)=1\right]=\frac{1}{2}$Pr[D(G,q,g,ga,gb,gz)=1]=Pr[PubKA,Πeav​(n)=1]=21​
当$z=ab$z=ab时，此时为IND-CPA实验，由于$x,y$x,y是随机选择的，那么攻击者在实验中具有优势$Adv\mathcal{A}$AdvA（假设）：
$\operatorname{Pr}\left[D\left(\mathbb{G}, q, g, g^{a}, g^{b}, g^{ab}\right)=1\right]=\operatorname{Pr}\left[\operatorname{Pub} K_{\mathcal{A}, \Pi}^{\operatorname{eav}}(n)=1\right]=\frac{1}{2}+Adv\mathcal{A}$Pr[D(G,q,g,ga,gb,gab)=1]=Pr[PubKA,Πeav​(n)=1]=21​+AdvA
由于DDH在群$\mathbb{G}$G中是困难的，因此有：
$\left|\operatorname{Pr}\left[\mathcal{A}\left(\mathbb{G}, q, g, g^{a}, g^{b}, g^{z}\right)=1\right]-\operatorname{Pr}\left[\mathcal{A}\left(\mathbb{G}, q, g, g^{a}, g^{b}, g^{ab}\right)=1\right]\right| \leq \operatorname{negl}(n)$∣∣​Pr[A(G,q,g,ga,gb,gz)=1]−Pr[A(G,q,g,ga,gb,gab)=1]∣∣​≤negl(n)
也即
$Adv\mathcal{A} \leq \operatorname{negl}(n)$AdvA≤negl(n)
从而我们证明了：如果 DDH 问题是困难的, ElGamal加密方案在IND-CPA 安全模型下是安全的。

关于ElGamal、CDH、DDH

对于ElGamal的安全性分析有两种：一种是基于Random Oracle模型，使用了CDH假设；另一种，没有Random Oracle模型，但是使用更强的DDH假设。

Random Oracle

由此：如果DDH假设在G中为假，则假设CDH在G中成立，该方案仍然是安全的，但限制在在较弱的Random Oracle语义安全(Semantic Secure)模型中。事实上，我们拥有其它避开RandomOracle的方法：可以通过强于CDH，但弱于DDH的hash Diffie-Hellman (HDH)假设，来实现IND-CPA安全。

有关HDH及其安全性证明，有时间再写吧，先复习期末了~