CDH、HDH、IDH、DDH、BDH、DBDH假设的概念

Computational Diffie-Hellman AssumptionG: finite cyclic group of order nComp. DH (CDH) assumption holds in G if: g, ga, gb ⇏ gabfor all efficient algs. A: Pr[ A(g, ga, gb)=gab ] < negligiblewher

Famidlistimo

18203人浏览 · 2020-12-18 20:42:23

Famidlistimo · 2020-12-18 20:42:23 发布

Computational Diffie-Hellman Assumption
$G$ : finite cyclic group of order n
Comp. DH (CDH) assumption holds in $G$ if: $g, g^a, g^b ⇏ g^{ab}$

for all efficient algs. A:
$Pr[ A(g, g^a, g^b)=g^{ab} ] < negligible$ where $g$ ← {generators of $G$ }, $a, b ← Z_{n}$

实际上CDH对于分析ElGamal系统的安全性并不理想，接着引入一个稍微更强一点的假设：Hash Diffie-Hellman假设。

Hash Diffie-Hellman Assumption
G: finite cyclic group of order n,
H: G²→ K a hash function
Def: Hash-DH (HDH) assumption holds for (G, H) if:

$g, g^a, g^b, H(g^b, g^{ab})) ≈_{p} (g, g^a, g^b, R)$
where $g$ ← {generators of $G$ }, $a, b ← Z_{n}$ ， $R \leftarrow K$

$g, g^a, g^b, H(g^b, g^{ab}))$ 和 $g, g^a, g^b, R)$ 这两个分布是不可区分的。那么这个假设是说，在ElGamal系统中，对称加密时推出的密钥，本质上与一个真随机密钥不可区分，这个真随机密钥是根据系统中余下的参数推出的，是一个独立的真随机密钥看起来和我们使用的密钥几乎一样。我们使用的密钥是根据 $g^a$ 和 $g^b$ 推出的。

这个哈希Diffie-Hellman假设实际上比CDH假设要强，证明的方法是看逆否命题，即假设CDH假设在群G上容易解决，那么我宣布，哈希Diffie-Hellman假设也是容易解决的。事实上，对于G和H，这是成立的，事实上，对于所有的哈希函数，若哈希函数的像含有两个元素，如果所有的哈希函数把一切都映射到一个点，这对于哈希Diffie-Hellman假设是容易的，对于所有哈希函数都成立。

CDH is easy ⇒ HDH is easy in $\quad ∀H, |Im(H)|≥2.$

这意味着，有了 $g^a$ , $g^b$ ，我可以计算 $g^{ab}$ 。因为我知道哈希函数H，我完全可以计算这里的值。那么如果你给我一组左边的样本，或是右边的样本，我都可以轻松地分辨其来源。如果它取自左边，那么我一旦自己计算 $g^{ab}$ ，我就可以测试组里的最后一个元素是否就是 $g^b$ 和 $g^{ab}$ 的哈希值。如果是，我就知道了这个样本是取自左边的；如果不是，我就知道是取自右边的。那么这给了我很高的优势来区分这两个分布，所以CDH容易的话，非常容易就能看出这些分布是可区分的。这就是说，如果哈希Diffie-Hellman实际上很难解决，那么CDH也将是很难的，因此哈希Diffie-Hellman假设是一个更强的假设。可能会有CDH，但HDH不困难。

事实上哈希Diffie-Hellman假设，足以证明EIGamal系统的语义安全了。

Interactive Diffie-Hellman assumption
为了证明选择的密文安全性需要更强的
Interactive Diffie-Hellman (IDH) in group G：
在这里插入图片描述

但是在IDH假设中，会赋予攻击者稍微多一点的能力，那么因为攻击者能力更强更难满足这个假设，这也是为什么我们说这个假设比计算Diffie-Hellman还强。那赋予的能力是什么? 进行询问的能力。特别地，攻击者可以提交中的两个元素，那么u₁，v₁是群G中的一对元素，然后他被告知(u₁)^a是否等于v1。如果(u₁)^a等于v1，他会得到1，否则他会得到0。是个有点怪异的询问攻击者呢?但实际上我们可以给攻击者回答这类请求，为了能够证明选择密文安全性。事实上攻击者可以一次次地进行这类询问，那么他可以进行提交尽可能多的像这样的询问，然后这个假设是说，尽管有所有这些询问，攻击者依然无法解出Diffie-Hellman密钥，就是说尽管做出了这么多的询问，攻击者正确输出Diffie-Hellman密钥的概率依然是可忽略的。那么很明显如果这个假设成立，则CDH假设也成立。

Decisional Diffie-Hellman assumption
DDH假设指的是区分元组 $g, g^a, g^b, g^{ab})$ 和 $g, g^a, g^b, g^z)$ 是困难的，其中 $g$ 是生成元， $x ， y ， z$ 是随机的。

设G是阶为大素数 $q$ 的群， $g$ 为 $G$ 的生成元， $x，y，z ← _{R}Z_{q}$ ，则以下两个分布是计算上不可区分的：

随机四元组 $R=(g, g^x, g^y, g^z)∈G_{4}$ ；
DDH四元组 $D=(g, g^x, g^y, g^{xy})∈G_{4}$

是计算上不可区分的，称为DDH假设。

具体地说一个敌手A，A区分R和D的优势：
$AdvADDH(κ)=∣Pr[A(R)=1]−Pr[A(D)=1]∣<negligibleAdv_{A}^{DDH}(\kappa)=|Pr[A(R)=1]-Pr[A(D)=1]|<negligible$

其中 $κ\kappa$ 是安全参数。

在密码学中，安全性参数是测量计算问题的输入大小的变量，用来确定加密方案密钥的长度。加密算法，协议的资源要求或对手破坏安全性的概率都以安全参数表示。

Bilinear Diffie-Hellman
BF方案的安全性是基于CDH问题的一种变形，称为计算性双线性DH假设。
Bilinear Diffie-Hellman简称BDH，计算性双线性问题：
指给定 $P、aP、bP、cP)((a, b, c)∈Z_{q}^*)$ ，计算 $w=e^(P,P)abc∈G2w=\hat e(P, P)^{abc}∈G_2$ ，其中 $e^\hat e$ 是一个双线性映射， $P$ 是 $G_1$ 的生成元， $G_1$ 、 $G_2$ 是阶为素数q的两个群。设算法A用来解决BDH问题，其优势定义为 $τ\tau$ ，如果 $Pr∣A(P、aP、bP、cP)=e^(P,P)abc∣≥τPr|A(P、aP、bP、cP)=\hat e(P, P)^{abc}|≥\tau$ 目前还没有有效的算法解决BDH问题，因此可假设BDH问题是一个困难问题，这就是BDH假设。

Decisional Bilinear Diffie-Hellman
DBDH 假设:

给定阶为素数 $p$ 的乘法群 $G_{1}$ 和 $G_{2}$
随机选择生成元 $g∈G_{1}$ 和随机数 $c_{1}，c_{2}，c_{3}∈Z_{p}$
将 $g, g^{c_{1}}, g^{c_{2}}, g^{c_{3}}, e(g, g)^{c_{1}c_{2}c_{3}}$ 和 $T∈G_{2}$ 发给 $A\mathcal{A}$ 。
由 $e(g, g)^{c_{1}c_{2}c_{3}}$ 判定 $T$ 是否等于 $e(g, g)^{c_{1}c_{2}c_{3}}$ ，若相等， $A\mathcal{A}$ 输出1；否则输出0。

定义算法 $A\mathcal{A}$ 解决上述问题的优势是：
$AdvDBDH=∣Pr[A(g,gc1,gc2,gc3,e(g,g)c1c2c3)=1]−Pr[A(g,gc1,gc2,gc3,T)=1]∣Adv^{DBDH}=|Pr[\mathcal{A}(g, g^{c_{1}}, g^{c_{2}}, g^{c_{3}}, e(g, g)^{c_{1}c_{2}c_{3}})=1]-Pr[\mathcal{A}(g, g^{c_{1}}, g^{c_{2}}, g^{c_{3}}, T)=1]|$
如果没有多项式时间算法以不可忽略的优势解决DBDH假设，则我们就称DBDH假设在群 $G_{1}，G_{2}$ 中是成立的。