对安全性证明中DH BDH等相关假设的理解（安全）-Toy模板网

这篇具有很好参考价值的文章主要介绍了对安全性证明中DH BDH等相关假设的理解（安全）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

密码学的安全本质上依赖于数学问题中的未解“难题”。注意，这些“难题”到目前为止还未找到一种多项式的解决算法，至于这种算法是否存在，未来能否被找到则是无法证明的。既然目前不存在一种多项式算法来解决某一难题，那我们就可以假设这个问题很难，在多项式时间内无法被解决。实际上，CDH DDH等假设正是基于这种考虑，就是在假设所对应的CDH DDH问题很难不能在多项式时间内解决。如果你不同意我的假设，你就需要提供存在一种多项式解法（很难的啦）。

为什么要强调多项式时间？因为任何“难题”都只是说没有快速的解法，而非不可解。毕竟在不考虑时间成本时，暴力法是所有问题的通用解法。当然，运气法也可以。

在安全性分析中，当我们想通过某一假设来证明方案的安全性时，我们首先需要将方案的安全性问题归约为对应的问题上。之后，我们可以得出结论：如果假设A成立（引用别人的假设文献作为定理），那么任何攻击者都无法在多项式时间内破解我们的方案，因为任何攻击者都无法在多项式时间内解决问题A。结论是基于假设的，而假设是具有时效性的。例如，如果某一天某个天才破解了问题A，那么上述的推断就不成立了。因此，在未来的某一天，我们现在提出的假设都可能被推翻。

定义

DH假设

DH问题来自于1976年提出的Diffie-Hellman密钥交换协议，其数学定义可以描述为：

给定 $g,p,g^a\ (mod\ p),g^b\ (mod\ p)>$ ，攻击者能否在多项式时间内计算出 $g^{ab}\ (mod\ p)$ ？

该问题依赖的数学难题是离散对数问题（Discrete Logarithm Problem，DLP）。DH假设的就是在说DLP问题很难，因此DH问题也很难。很明显，这是成立的，因为离散对数问题至今仍未被解决。想要推翻这个假设你就得解决DLP问题，总不能拿不出证据又不承认。

CDH假设和DDH假设

CDH假设（Computational Diffie-Hellman Assumption）和DDH假设（Decisional Diffie-Hellman Assumption）是DH假设的变体，将线性离散问题转移到群论离散问题。我们说过，假设都是对应问题的，两者所对应的问题分别为：

Computational Diffie-Hellman Problem（CDHP）：
对于循环群 $G$ 和生成元 $g$ ，给定 $G,g,g^a,g^b>$ ，攻击者能否在多项式时间计算出 $g^{ab}$ ?

Decisional Diffie-Hellman Problem（DDHP）：
对于循环群 $G$ 和生成元 $g$ ，给定 $G,g,g^a,g^b,g^c>$ ，攻击者能否在多项式时间判断出 $g^c\overset{\text{?}}{=}g^{ab}$ ?

类似的，CDH假设就是认为CDHP无多项式时间解，而DDH假设是认为DDHP无多项式时间解。

问题1，CDHP和DDHP的差异在哪？哪个更难解决？从上面的问题定义中可以看出，两者主要差异是对攻击者的要求，前者要求攻击者计算出结果，而后者要求攻击者判断一个结果对不对。那么哪个更难呢？答案是CDHP难于DDHP，因为如果你能解决CDHP，那你就能解决DDHP。试想，你都能算出 $g^{ab}$ 了，还能不知道 $g^c\overset{\text{?}}{=}g^{ab}$ 。但是反过来不行啊，你不能说我知道了 $g^c\ne g^{ab}$ 我就知道了 $g^{ab}$ 。DDHP可以看作是CDHP的放松版，简单点说就是，你算不出来不要紧，我给你个数，你验证一下是不是正确解就完事了。所以，我们得出：在问题难度方面， $CDHP\ge DDHP$ 。我们再把DLP也算上。同样的道理，解决了DLP就能解决CDHP，但是解决了CDHP不一定能解决DLP，因此我们可以得出结论：在问题难度方面， $DLP\ge CDHP\ge DDHP$ 。

问题2，是否问题越难，所对应的假设越强？答案是否。假设的强度与问题的难度相反，问题越难，假设越弱。注意，这里的强弱是指安全等级，因为假设是用在安全分析上的，不是说假设越弱越容易被推翻，因为所有的假设都是基于离散问题的，都是成立的，都是难解的“难题”，切勿误解。试想一下，如果我们的系统A在数学上满足DDH假设，也就是说没有人能够在多项式时间内解决DDHP。你连最简单的DDHP都解决不了，就更不可能解决CDHP了。就好比你连加法都不会，还想学高等数学？反过来，如果我们的系统B在数学上只满足CDH假设，也就意味着攻击者能够解决DDHP。对比而言，攻击者在B上能做的计算更多，所以我们说A系统强于B系统。因为A系统依赖于DDH假设，B系统依赖于CDH假设，所以，我们说在安全强弱方面： $DDH\ge CDH$ 。在一般的论文分析中，为了体现设计的方案足够安全，普遍采用的是Decisonal版本的假设，即DDH假设，下面的BDH系列也是。

CBDH假设和DBDH假设

CBDH假设（Computational Bilinear Diffie-Hellman Assumption）和DBDH假设（Decisional Bilinear Diffie-Hellman Assumption）是CDH的变体。前面提CDH假设和DDH假设时说的是将DH中的线性离散问题转移到群论离散问题，那么CBDH假设和DBDH假设就是将CDH和DDH中的群论离散问题转移到双线性映射中的椭圆曲线离散问题。

双线性映射操作的也是循环群，但是是满足特定属性的循环群，通常会使用椭圆曲线理论来得到这样的循环群。有趣的是，椭圆曲线理论最早用于椭圆曲线加密法（ECC）中，而双线性映射是在破解ECC的过程中发现的，之后人们发现这个性质太适合用于加密了。数学上计算出满足这种性质的循环群是比较难的，目前主流的库包括python的pypbc（这玩意儿依赖于PBC库，这个库只支持Linux系统）和Java里面的jpbc（听过没用过）。

都是群论离散问题，为什么有CDH和DDH不用又要提出还要提出新的假设呢？因为循环群的属性增加了，之前的假设无法保证新增的属性不会带来安全问题。实际上，现存的假设远不止这些，比如，我还在其他论文中看到过一种名为 $l$ -DCBDH（Decisional $l$ -Combined Bilinear Diffie-Hellman）的变体。只能说具体场景具体分析。

同样，我们给出两个假设对应的问题

Computational Bilinear Diffie-Hellman Problem（CBDHP）：
对于循环群 $G_1,G_2$ ，生成元 $g$ 和映射函数 $e$ ，给定 $G_1,G_2,e,g,g^a,g^b,g^c>$ ，攻击者能否在多项式时间计算出 $e(g,g)^{abc}$ ?

Decisional Bilinear Diffie-Hellman Problem（DBDHP）：
对于循环群 $G_1,G_2$ ，生成元 $g$ 和映射函数 $e$ ，给定 $G_1,G_2,e,g,g^a,g^b,g^c,e(g,g)^d>$ ，攻击者能否在多项式时间判断出 $e(g,g)^d\overset{\text{?}}{=}e(g,g)^{abc}$ ?

同样，CBDH假设认为CBDHP无多项式解，DBDH假设认为DBDHP无多项式解。Computational版本和Decisional版本的差异和上面是一样的，此处就不再重复。也是同样的道理，在安全性分析中我们常用的是DBDH假设。文章来源地址https://www.toymoban.com/news/detail-454639.html

到了这里，关于对安全性证明中DH BDH等相关假设的理解（安全）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！