对安全性证明中DH BDH等相关假设的理解
前言
密码学的安全本质上依赖于数学问题中的未解“难题”。注意，这些“难题”到目前为止还未找到一种多项式的解决算法，至于这种算法是否存在，未来能否被找到则是无法证明的。既然目前不存在一种多项式算法来解决某一难题，那我们就可以假设这个问题很难，在多项式时间内无法被解决。实际上，CDH DDH等假设正是基于这种考虑，就是在假设所对应的CDH DDH问题很难不能在多项式时间内解决。如果你不同意我的假设，你就需要提供存在一种多项式解法（很难的啦）。
为什么要强调多项式时间？因为任何“难题”都只是说没有快速的解法，而非不可解。毕竟在不考虑时间成本时，暴力法是所有问题的通用解法。当然，运气法也可以。
在安全性分析中，当我们想通过某一假设来证明方案的安全性时，我们首先需要将方案的安全性问题归约为对应的问题上。之后，我们可以得出结论：如果假设A成立（引用别人的假设文献作为定理），那么任何攻击者都无法在多项式时间内破解我们的方案，因为任何攻击者都无法在多项式时间内解决问题A。结论是基于假设的，而假设是具有时效性的。例如，如果某一天某个天才破解了问题A，那么上述的推断就不成立了。因此，在未来的某一天，我们现在提出的假设都可能被推翻。
定义
DH假设
DH问题来自于1976年提出的Diffie-Hellman密钥交换协议，其数学定义可以描述为：
给定
< g , p , g a ( m o d p ) , g b ( m o d p ) > <g,p,g^a\ (mod\ p),g^b\ (mod\ p)> <g,p,ga (mod p),gb (mod p)>，攻击者能否在多项式时间内计算出 g a b ( m o d p ) g^{ab}\ (mod\ p) gab (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 g，给定 < G , g , g a , g b > <G,g,g^a,g^b> <G,g,ga,gb>，攻击者能否在多项式时间**计算**出 g a b g^{ab} gab?
Decisional Diffie-Hellman Problem（DDHP）：
对于循环群G G G和生成元 g g g，给定 < G , g , g a , g b , g c > <G,g,g^a,g^b,g^c> <G,g,ga,gb,gc>，攻击者能否在多项式时间**判断**出 g c = ? g a b g^c\overset{\text{?}}{=}g^{ab} gc=?gab?
类似的，CDH假设就是认为CDHP无多项式时间解，而DDH假设是认为DDHP无多项式时间解。
问题1，CDHP和DDHP的差异在哪？哪个更难解决？从上面的问题定义中可以看出，两者主要差异是对攻击者的要求，前者要求攻击者计算出结果，而后者要求攻击者判断一个结果对不对。那么哪个更难呢？答案是CDHP难于DDHP，因为如果你能解决CDHP，那你就能解决DDHP。试想，你都能算出
g
a
b
g^{ab}
gab了，还能不知道
g
c
=
?
g
a
b
g^c\overset{\text{?}}{=}g^{ab}
gc=?gab。但是反过来不行啊，你不能说我知道了
g
c
≠
g
a
b
g^c\ne g^{ab}
gc=gab我就知道了
g
a
b
g^{ab}
gab。DDHP可以看作是CDHP的放松版，简单点说就是，你算不出来不要紧，我给你个数，你验证一下是不是正确解就完事了。所以，我们得出：在问题难度方面，
C
D
H
P
≥
D
D
H
P
CDHP\ge DDHP
CDHP≥DDHP。我们再把DLP也算上。同样的道理，解决了DLP就能解决CDHP，但是解决了CDHP不一定能解决DLP，因此我们可以得出结论：在问题难度方面，
D
L
P
≥
C
D
H
P
≥
D
D
H
P
DLP\ge CDHP\ge DDHP
DLP≥CDHP≥DDHP。
问题2，是否问题越难，所对应的假设越强？答案是否。假设的强度与问题的难度相反，问题越难，假设越弱。注意，这里的强弱是指安全等级，因为假设是用在安全分析上的，不是说假设越弱越容易被推翻，因为所有的假设都是基于离散问题的，都是成立的，都是难解的“难题”，切勿误解。试想一下，如果我们的系统A在数学上满足DDH假设，也就是说没有人能够在多项式时间内解决DDHP。你连最简单的DDHP都解决不了，就更不可能解决CDHP了。就好比你连加法都不会，还想学高等数学？反过来，如果我们的系统B在数学上只满足CDH假设，也就意味着攻击者能够解决DDHP。对比而言，攻击者在B上能做的计算更多，所以我们说A系统强于B系统。因为A系统依赖于DDH假设，B系统依赖于CDH假设，所以，我们说在安全强弱方面：
D
D
H
≥
C
D
H
DDH\ge CDH
DDH≥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
l
l-DCBDH（Decisional
l
l
l-Combined Bilinear Diffie-Hellman）的变体。只能说具体场景具体分析。
同样，我们给出两个假设对应的问题
Computational Bilinear Diffie-Hellman Problem（CBDHP）：
对于循环群G 1 , G 2 G_1,G_2 G1,G2，生成元 g g g和映射函数 e e e，给定 < G 1 , G 2 , e , g , g a , g b , g c > <G_1,G_2,e,g,g^a,g^b,g^c> <G1,G2,e,g,ga,gb,gc>，攻击者能否在多项式时间**计算**出 e ( g , g ) a b c e(g,g)^{abc} e(g,g)abc?
Decisional Bilinear Diffie-Hellman Problem（DBDHP）：
对于循环群G 1 , G 2 G_1,G_2 G1,G2，生成元 g g g和映射函数 e e e，给定 < G 1 , G 2 , e , g , g a , g b , g c , e ( g , g ) d > <G_1,G_2,e,g,g^a,g^b,g^c,e(g,g)^d> <G1,G2,e,g,ga,gb,gc,e(g,g)d>，攻击者能否在多项式时间**判断**出 e ( g , g ) d = ? e ( g , g ) a b c e(g,g)^d\overset{\text{?}}{=}e(g,g)^{abc} e(g,g)d=?e(g,g)abc?
同样，CBDH假设认为CBDHP无多项式解，DBDH假设认为DBDHP无多项式解。Computational版本和Decisional版本的差异和上面是一样的，此处就不再重复。也是同样的道理，在安全性分析中我们常用的是DBDH假设。
版权归原作者 java大战c++ 所有， 如有侵权，请联系我们删除。