ElGamal的安全性
ElGamal密码体制基于离散对数问题。
离散对数问题
离散对数问题(DLP)
已知一个乘法群\((G,\cdot)\)，一个\(n\)阶元素\(\alpha \in G\)和元素\(\beta \in G\)，计算\(a=\log_{\alpha}\beta\)
计算Diffie-Hellman问题(CDH)
已知一个乘法群\((G,\cdot)\)，一个\(n\)阶元素\(g\in G\)和两个元素\(g^a,g^b\in G\)，其中\(a,b\)未知，计算\(g^{ab}\in G\)
-
在一个公共信道上，Alice和Bob确定了一个公用的循环群\(G\)和生成器
-
Alice选择一个随机数\(a\)，Bob选择一个随机数\(b\)
-
Alice计算\(g^a\)在公共信道上传输给Bob，同时Bob计算\(g^b\)在公共信道上传输给Alice
-
Alice分别计算\((g^a)^b\)和\((g^b)^a\)，得到他们协商的密钥
如果有敌手窃听了他们交换使用的\(G,g,g^a,g^b\)，需要计算出\(a\)或\(b\)即能解决DLP问题，才能获得\(g^{ab}\)，也就是说CDH问题基于DLP问题。
判定Diffie-Hellman问题(DDH)
已知一个乘法群\((G,\cdot)\)，一个\(n\)阶元素\(g\in G\)和元素\(g^a,g^b,g^c\in G\)，其中\(a,b,c\)未知，判定\(g^{ab}=g^c\)是否成立。
在Diffie-Hellman问题中，\(G,g,g^a,g^b\)是公开的，\(g^{ab}\)是私钥，DDH问题用于证明难以区分的属性，也就是敌手不能从\(G\)中区分出密钥\(g^{ab}\)。
给定\(G,g,g^a,g^b,T_b\)，设\(T_0\)是\(G\)中随机的一个元素，\(T_1=g^{ab}\)，\(b\leftarrow \{0,1\}\)，如果敌手以大于\(\frac{1}{2}\)的概率得到正确的\(b\)，也就是说敌手能够解决CDH问题，也就是说DDH问题基于CDH问题
综上，困难性：DLP>CDH>DDH
ElGamal的安全性规约证明
设敌手攻击ElGamal加密方案成功的概率为\(\frac{1}{2} + \sigma\)，当\(z\)取随机数时，\(\tilde{\Pi}\)不是一个加密方案，不能解密，敌手有\(\frac{1}{2}\)的概率猜中。
\[\begin{aligned} &Pr[D(G,g,g^x,g^y,g^{xy})=1] = Pr[PubK^{eav}_{A,\Pi}=1] = \dfrac{1}{2} + \sigma\\ &Pr[D(G,g,g^x,g^y,g^z)=1] = Pr[PubK^{eav}_{A,\tilde{\Pi}}=1] = \dfrac{1}{2}\\ &Pr[D(G,g,g^x,g^y,g^{xy})=1] - Pr[D(G,g,g^x,g^y,g^z)=1] = \sigma\\ \end{aligned} \]因此，ElGamal加密方案安全等价于DDH问题。
标签：Pr,ab,ElGamal,CDH,Alice,DDH,安全性 From： https://www.cnblogs.com/euler0525/p/16921585.html